# question about kinds

**Ashley Yakeley
**
ashley@semantic.org

*Fri, 18 Jan 2002 16:27:26 -0800*

At 2002-01-18 13:19, Hal Daume III wrote:
>*In theory, I could write:
*>*
*>*class Traversable d a where
*>* traverse :: d a -> (Maybe a, [d a])
*>*
*>*instance Traversable Tree a where
*>* traverse (Leaf a) = (Just a, [])
*>* traverse (Branch t1 t2) = (Nothing, [t1,t2])
*>*
*>*instance Traversable [] a where
*>* traverse [] = (Nothing, [])
*>* traverse (x:xs) = (Just x, [xs])
*>*
*>*instance (Traversable d (e a), Traversable e a) => Traversable d (e
*>*a) where
*>* traverse = ...
*>*
*>*but then both ghc and hugs complain about overlapping instances, even with
*>*-fallow-overlapping-instances/-fallow-undecidable-instances in ghc and +o
*>*in hugs.
*
Try this:
class Traversable t a where -- note no fundep
traverse :: t -> (Maybe a, [t])
instance Traversable (Tree a) a where
traverse (Leaf a) = (Just a, [])
traverse (Branch t1 t2) = (Nothing, [t1,t2])
instance Traversable [a] a where
traverse [] = (Nothing, [])
traverse (x:xs) = (Just x, [xs])
instance (Traversable (d (e a)) (e a), Traversable (e a) a) =>
Traversable (d (e a)) a where
traverse = ...
...or even, more generally...
instance (Traversable a b, Traversable b c) =>
Traversable a c where
traverse = ...
--
Ashley Yakeley, Seattle WA