question about kinds

[Hal Daume III]

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