views:

222

answers:

2

Why can't Haskell resolve the kind of [[]] (A list of lists)?
Why isn't it simply * -> *, as I can give it a type like Int, and get [[Int]], which is of kind *.

+8  A: 

I think it's the same as with Maybe Maybe, although in the latter case the reason is perhaps clearer: the "outer" type constructor expects to be passed a type of kind *, but sees a type constructor of type * -> * (the "inner" Maybe / []) and complains. If I'm correct, this is not really a problem with the :kind functionality of GHCi, but rather with finding the correct syntax to express the composition of higher-kinded type constructors.

As a workaround, something like

:kind forall a. [[a]]
:kind forall a. Maybe (Maybe a)

can be used (with the appropriate language extension turned on -- ExistentialQuantification, I think -- to enable the forall syntax).

Michał Marczyk
This thread from Haskell Café might be relevant: http://www.mail-archive.com/[email protected]/msg08530.html -- Composition of Type Constructors.
Michał Marczyk
I don't think existential type was intended (which is `*`). An easy way, but outside GHCi, is `type a = [[a]]` (which is `* -> *`).
sdcvvc
@sdcvvc that's a universally quantified polymorphic type (not an existential).
Don Stewart
@sdcvvc: The `forall` lines where meant as a means of making sure what the kind of the type constructors at hand is when there's a reasonable guess available -- if one suspects that `Foo` and `Bar` are both `* -> *`, checking whether the kind of `forall a. Foo (Bar a)` is `*` is one way of confirming that. I guess I haven't made it very clear. That's the best I can think of inside GHCi... In a regular source file, one can write `type Foo a = [[a]]` with the view to type `:k Foo` in GHCi to get back the missing `* ->` from the front, yeah.
Michał Marczyk
+2  A: 

If we desugar [[]] as [] [] then it's obvious that it is poorly kinded because [] :: * -> *.

If you actually wanted a "list of lists" you need to compose two type constructors of kind * -> *. You can't do that without a little boilerplate because Haskell doesn't have a type-level lambda. You can do this though:

newtype Comp f g a = Comp { unComp :: f (g a) }

Now you can write:

type ListList = Comp [] []

And write functions using it:

f :: ListList Int -> ListList Int
f = Comp . map (map (+1)) . unComp

Functor composition like this has applications in several areas, notably Swierstra's "Data types a la carte"

Max Bolingbroke