автоматическое типирование вложенных списков

Question

При работе через Ричард Птичье Думая Функционально С Haskell, я наткнулся на демонстрацию системы типа 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]]].