haskell - automatic typing of nested lists -

while working through richard bird's thinking functionally haskell, came across demonstration of haskell's type system find puzzling (p. 44):

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

to explain, let main list have type [b]. first element list, b=[c]. second element list of lists, c=[d]. third element list of lists of lists, d=[a]

doesn't type signature indicate first element of main list has type [[[a]]]? don't see how that's possible.

let's rewrite this:

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

now assign type variables: ab initio

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

since have have same type, l has type [b]. now, more specifically,

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

to justify number of brackets. these still have same type b, i.e. in fact

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

and

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

which whole has type [[[[e]]]]. or, if prefer, [[[[a]]]].

---

perhaps gets clearer if consider more interesting specific examples. following [int] lists:

• [1,2,3]
• [1]
• [0]
• []

these [[int]] lists:

• [ [1,2], [1,2,3] ]
• [ [1], [2] ]
• [ [1], [] ]
• [ [] ]
• [ ]

and these [[[int]]] lists:

• [ [[1]], [[2],[]], [[3],[],[]] ]
• [ [[]], [[1]], [[2,3]] ]
• [ [], [[]] ]
• [ [[]] ]
• [ ]

note empty list [] possible types. list containing empty list, [[]] possible [[int]] , [[[int]]], , list containing list empty list needs doubly-nested list [[[int]]].