CODEWITHSUNDEEP
haskelltypespolymorphismghc
Squidly
Squidly

Reputation: 2717

Why can't GHCi resolve the kind of [[]]?

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

Upvotes: 6

Views: 368

Answers (2)

Max Bolingbroke
Max Bolingbroke

Reputation: 2169

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"

Upvotes: 4

Michał Marczyk
Michał Marczyk

Reputation: 84341

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

Upvotes: 8

Related Questions