Почему в Haskell можно сделать такой список:
slist = [ [], [[]], [[],[[]]] ]
Насколько я понимаю, каждый элемент имеет различные типы (например, в математике: Ø, {Ø} и т.д.). И ghci говорит:
> :t []
[] :: [t]
> :t [[]]
[[]] :: [[t]]
Формально я вижу разные заметки.
Другими словами, первый элемент представляет собой простой пустой список, а второй - список списка (!) И т.д.
Что случилось? Почему Haskell считает их одинаковыми?
Вы правы, что в списке Haskell все элементы должны быть одного типа. И действительно, тип в вашем примере:
> :t slist
slist :: [[[[a]]]]
Но пустой список [] может иметь любой тип, если он имеет форму [b], но есть много возможных b s. Таким образом, существует много возможных конкретных типов. Один из них - для b типа [[[a]]], как в вашем slist.
Взгляните на тип первого элемента такого списка:
> head [ [], [[]], [[],[[]]] ]
[]
it :: [[[t]]]
Это не t, но это [[[t]]].
Почему я могу сделать в Haskell такой список
Потому что нет ничего плохого в типе этого выражения.
Что случилось? Почему Haskell считает их одинаковыми?
t в [[[[t]]]] не является окончательным типом, он вводит переменную. Поэтому тип первого элемента этого списка может быть a или [b] или [[c]] или [[[t]]].
Пустым списком может быть список любого типа. Это может быть список чисел, список строк или список списков. Я имею в виду, почему бы вам не разрешить иметь пустой список списков или даже пустой список списков списков?
Итак, в вашем списке:
--a b c d
[ [], [ [] ], [ [], [ [] ] ] ]
d - пустой список, c - пустой список списков, b - пустой список списков списков, a - пустой список списков списков.