question about kinds
Hal Daume III
Fri, 18 Jan 2002 13:10:39 -0800 (PST)
I have the following definition:
> class Traversable d where
> traverse :: d a -> (Maybe a, [d a])
And the standard binary tree data type:
> data Tree a = Branch (Tree a) (Tree a)
> | Leaf a
I can define both Tree and  to be instances of Traversable:
> instance Traversable Tree where
> traverse (Leaf a) = (Just a, )
> traverse (Branch t1 t2) = (Nothing, [t1,t2])
> instance Traversable  where
> traverse  = (Nothing, )
> traverse (x:xs) = (Just x, [xs])
Now, I want to say that if some data type 'd' is Traversable and another
data type 'e' is Traversable, then the "combined data type" is
Traversable. That is, for example, I want to say that a Tree of Lists is
traversable, or that a List of Trees, or a List of Lists is traversable.
But I can say neither:
> instance Traversable (Tree ) where ...
> instance (Traversable a, Traversable b) => Traversable (a b) where ..
Because of the obvious kind errors. What I suppose I need is some sort of
lambda expansion over kinds, so I could say:
> instance (Traversable a, Traversable b) => Traversable (\x -> a b x)
or something like that.
Obviously this doesn't exist.
How can I get around this?
Hal Daume III
"Computer science is no more about computers | firstname.lastname@example.org
than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume