question about kinds

[Hal Daume III]

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.

why would this be?

 - Hal

--
Hal Daume III

 "Computer science is no more about computers    | hdaume@isi.edu
  than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

On Fri, 18 Jan 2002, Hal Daume III wrote:

> 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
> 
> 
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users@haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>