While working through Richard Bird's *Thinking Functionally With Haskell*, I came across a demonstration of Haskell's type system that I find puzzling (p. 44):

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

To explain, let the main list have type `[b]`

. The first element is a list, so `b=[c]`

. The second element is a list of lists, so `c=[d]`

. The third element is a list of lists of lists, so `d=[a]`

Doesn't this type signature indicate that the first element of the main list has type `[[[a]]]`

? I don't see how that's possible.

# Best How To :

Let's rewrite this:

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

Now we assign type variables: ab initio

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

since they all have to have the same type, so `l`

has some type `[b]`

. Now, more specifically,

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

to justify the number of brackets. But these still have to be the same type `b`

, i.e. in fact

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

and

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

which as a whole has type `[[[[e]]]]`

. Or, if you prefer, `[[[[a]]]]`

.

Perhaps it all gets clearer if you consider more interesting specific examples. The following are `[Int]`

lists:

These are `[[Int]]`

lists:

`[ [1,2], [1,2,3] ]`

`[ [1], [2] ]`

`[ [1], [] ]`

`[ [] ]`

`[ ]`

And these are `[[[Int]]]`

lists:

`[ [[1]], [[2],[]], [[3],[],[]] ]`

`[ [[]], [[1]], [[2,3]] ]`

`[ [], [[]] ]`

`[ [[]] ]`

`[ ]`

Note that the empty list `[]`

is possible for all types. The list containing only an empty list, `[[]]`

is possible for `[[Int]]`

and `[[[Int]]]`

, and the list containing a list with only an empty list needs a doubly-nested list `[[[Int]]]`

.