CODEWITHSUNDEEP
listhaskelltypes
Vladimir
Vladimir

Reputation: 541

list of nested empty lists in Haskell

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?

Upvotes: 12

Views: 1449

Answers (3)

mb21
mb21

Reputation: 39229

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.

Upvotes: 7

sepp2k
sepp2k

Reputation: 370162

An empty list can be a list of any type. It can be a list of numbers, a list of strings, or a list of lists. I mean, why wouldn't you be allowed to have an empty list of lists or even an empty list of lists of lists?

So in your list:

--a     b       c     d
[ [], [ [] ], [ [], [ [] ] ] ]

d is an empty list, c is an empty list of lists, b is an empty list of lists of lists and a is an empty list of lists of lists of lists.

Upvotes: 3

ДМИТРИЙ МАЛИКОВ
ДМИТРИЙ МАЛИКОВ

Reputation: 21972

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]]].

Upvotes: 6

Related Questions