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