Menu
Why is it possible to make such a list in Haskell:
slist = [ [], [[]], [[],[[]]] ]
As far I understand, every element has various types here (like in mathematics: Ø, {Ø} and so on). And ghci says:
> :t []
[] :: [t]
> :t [[]]
[[]] :: [[t]]
formally, I see different notes.
In other words, the first element is a simple empty list and the second one is a list of list (!) and so on.
What is wrong? Why does Haskell consider them to be the same type?
446
Get Programming with HaskellYou can't return an empty list, because an empty list is the same type as the elements of the list.
The list [1,2,3] in Haskell is actually shorthand for the list 1:(2:(3:[])), where [] is the empty list and : is the infix operator that adds its first argument to the front of its second argument (a list). (: and [] are like Lisp's cons and nil, respectively.)
In Haskell, lists are a homogenous data structure. It stores several elements of the same type. That means that we can have a list of integers or a list of characters but we can't have a list that has a few integers and then a few characters.
You are right, that in a Haskell list, all elements must be of the same type. And indeed, the type in your example is:
> :t slist
slist :: [[[[a]]]]
But the empty list [] can have any type, as long as it's of the form [b], but there are many possible bs. So there are many possible concrete types. One of them is for b to be of type [[[a]]], as in your slist.
165
Take a look at type of the first element of such a list:
> head [ [], [[]], [[],[[]]] ]
[]
it :: [[[t]]]
It's not t, but it's [[[t]]].
Why I can possibility to make in Haskell such list
Because the is nothing wrong with the type of this expression.
What is wrong? Why does Haskell consider them to be the same type?
t in the [[[[t]]]] is not a final type, it's type variable. That's why the type of the first element of this list could be a or [b] or [[c]] or [[[t]]].
25
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
