question about kinds

Hal Daume III hdaume@ISI.EDU
Fri, 18 Jan 2002 13:22:08 -0800 (PST)


Oops, nevermind; that was dumb of me.  I spoke too quickly.  Of course
that would produce overlapping instances :)

--
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:

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