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
>