question about kinds

[Ashley Yakeley]

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