Lennart Augustsson wrote:
> > But what can such a type be used for?
>
> This particular example is not very useful, but there are examples where
> higher kinds are used. Chris Okasaki have some for representing square
> matrices.
Here's a simpler example. Consider the type of non-empty, multiway trees
(often called "rose trees").
data Tree a = Node a [Tree a]
Now, let's generalize this to replace the list type constructor with a type
constructor for some arbitrary kind of collection.
data GTree coll a = Node a (coll (GTree coll a))
This type is useful for extending certain properties of the underlying
collection type. For example, if H is a type constructor for priority queues
that supports insert in O(1) time, then Maybe (GTree H a) gives priority
queues that support both insert and merge in O(1) time. Similarly,
if Q is a type constructor for FIFO queues that support "snoc" in
O(1) time, then Maybe (GTree Q a) gives FIFO queues that support
cons, snoc, and append in O(1) time.
These are both described in Section 10.2 of my book...
Chris
