嵌套的列表

Question

的自動打字，通過理查德·伯德的功能思考哈斯克爾工作，我碰到Haskell的類型系統的演示，我覺得百思不得其解（第44頁）：

[ [], [[]], [[[]]] ] :: [[[[a]]]]

爲了解釋，讓主列表的類型爲[b]。第一個元素是 列表，所以b=[c]。第二個元素是列表的列表，所以c=[d]。該 第三個要素是列表的列表清單，所以d=[a]

不這種類型的簽名表明主力名單的第一個元素類型[[[a]]]？我不明白這是可能的。

Answer 1

讓我們改寫這個：

l = [l1, l2, l3] 
where l1 = [] 
     l2 = [[]] 
     l3 = [[[]]] 

現在我們指定類型的變量：從頭

 l1 :: b 
     l2 :: b 
     l3 :: b 

，因爲他們都具有相同的類型，所以l具有某種類型的[b]。現在，更具體地說，

 l1 :: [c] 
     l2 :: [[d]] 
     l3 :: [[[e]]] 

以證明括號的數量。但這些還是要同類型b，即實際上

 l1 :: [[[e]]] 
     l2 :: [[[e]]] 
     l3 :: [[[e]]] 

和

l = [ [] :: [[[e]]] 
    , [[]] :: [[[e]]] 
    , [[[]]] :: [[[e]]] ] 

其作爲一個整體具有類型[[[[e]]]]。或者，如果你願意，[[[[a]]]]。

---

也許這一切都變得更清晰，如果你考慮更有趣的具體例子。以下是[Int]列表：

• [1,2,3]
• [1]
• [0]
• []

這些[[Int]]列表：

• [ [1,2], [1,2,3] ]
• [ [1], [2] ]
• [ [1], [] ]
• [ [] ]
• [ ]

這些都是[[[Int]]]列表：

• [ [[1]], [[2],[]], [[3],[],[]] ]
• [ [[]], [[1]], [[2,3]] ]
• [ [], [[]] ]
• [ [[]] ]
• [ ]

注意空單[]能對所有類型。僅包含空列表的列表[[]]對於[[Int]]和[[[Int]]]是可能的，並且包含僅具有空列表的列表需要雙嵌套列表[[[Int]]]。