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 *.
views:
222answers:
2
+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
2010-06-08 05:00:00
This thread from Haskell Café might be relevant: http://www.mail-archive.com/[email protected]/msg08530.html -- Composition of Type Constructors.
Michał Marczyk
2010-06-08 05:05:23
I don't think existential type was intended (which is `*`). An easy way, but outside GHCi, is `type a = [[a]]` (which is `* -> *`).
sdcvvc
2010-06-08 06:59:32
@sdcvvc that's a universally quantified polymorphic type (not an existential).
Don Stewart
2010-06-08 07:07:01
@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
2010-06-08 17:39:15
+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
2010-08-13 09:03:38