# question about kinds

**Hal Daume III
**
hdaume@ISI.EDU

*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 ...
*
or:
>* 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
--
Hal Daume III
"Computer science is no more about computers | hdaume@isi.edu
than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume