哈斯克爾 - 嵌套空列表

閱讀http://learnyouahaskell.com/當我的一個朋友想出了一個問題：

是否有可能在Haskell寫一個遞歸函數，提供真正的，如果所有的子-sub -_-子列表爲空。我的第一個猜想是 - 應該是 - 但是我寫了一個類型註釋的問題很大。

他試圖像

nullRec l = if null l 
       then True 
       else if [] `elem` l 
        then nullRec (head [l]) && nullRec (tail l) 
        else False

這是 - 不工作 - :-)

我想出了類似

與CONCAT摺疊 - 獲得AA單一長串
（給我執行問題）
或製作無限樹狀數據類型 - 並且使這個從列表
（尚未實施）

但後者聽起來有點像矯枉過正這個問題。什麼是你的想法 - 在這樣;-)

感謝晴朗的週日提前

爲所有評論的反應 - 這是不好的風格，我想補充這只是一個實驗！
不要在家裏試試！ ;-)

來源

2011-07-10 epsilonhalbe

想想這種函數的類型應該是什麼（如果您在普通列表上實現它）！ – yatima2975

我想到了 - 它應該是無限的[[... [a] ...]]，但這不可能在哈斯克爾寫下來 - 這就是爲什麼我想出了第二種方法。但有沒有更簡單的方法來做到這一點。另外我的大腦有點慢，因爲我今天生病了。 – epsilonhalbe

生病與否，你走在正確的軌道上！編寫一系列函數'nullRec2 :: [[a]] - > Bool'，'nullRec3 :: [[a]] - > Bool'等很簡單（嘗試一下！），但是你無法讓他們輕鬆適應單一類型簽名。您可能需要樹型數據，如'數據樹a =分支[樹a] |節點a'或者可能有類型類的東西（對此方法還沒有多少考慮）。 – yatima2975

一個typeclass怎麼樣？

{-# LANGUAGE FlexibleInstances, OverlappingInstances #-} 

class NullRec a where 
    nullRec :: a -> Bool 

instance NullRec a => NullRec [a] where 
    nullRec [] = True 
    nullRec ls = all nullRec ls 

instance NullRec a where 
    nullRec _ = False 

main = print . nullRec $ ([[[[()]]]] :: [[[[()]]]])

來源

2011-07-10 15:34:52 fuz

更確切地說，您不僅使用類型類別，而且還使用GHC擴展[OverlappingInstances]（http://www.haskell.org/ghc/docs/7.0.4/html/users_guide/type-class-extensions.html ＃實例重疊）。沒有這個擴展，即使使用類型類也無法達到問題中所要求的。這強烈表明，如果有人需要實施這個（除了作爲實驗），該計劃可能沒有以正確的方式設計。 –

這是不可能使用參數多態性，因爲以下原因。

考慮這些值：

x = [8] :: [Int] 
y = [3.0] :: [Double] 
z = [[]] :: [[Int]]

很顯然，你希望你的功能，既x和y工作，因此它的類型必須是null1 :: [a] -> Bool。（有人可以幫我做這個說法看起來正式了嗎？我怎麼能證明這是唯一的最具體的上下文較少型unifiable與[Int] -> Bool和[Double] -> Bool？有沒有類型之間的關係的名字嗎？）

現在，如果你有這種類型，那麼null1 z將等於null1 x，因爲它們只在列表元素的值不同，而這些元素從抽象出來。 （甚至還沒有接近再次形式化證明:(）

你想爲z什麼是null2 :: [[a]] -> Bool，這將在行爲上有所不同，從而使null1和null2相同的名稱將需要重載。（請參閱FUZxxl的答案）

來源

2011-07-10 16:03:25 Rotsor

我覺得這個觀點相當有說服力。 – luqui

我覺得'null1。（：[]）:: a - > Bool'使我們更接近形式證明，但我仍然不知道如何做出最後一步（顯示'a - > Bool'與'Bool'相同）。 – Rotsor

這是一種相反的自由定理，但是'Int'和'Double'的最大下界（在Haskell上下文無關類型的格子上，以替換爲關係）是'a'，因爲你不能在它們兩個中都替換類型變量（沒有任何！），並以相同的類型結束。還是我把我的上下方向混淆了？ – yatima2975

哈斯克爾 - 嵌套空列表

回答

相關問題