question about kinds
Hal Daume III
hdaume@ISI.EDU
Fri, 18 Jan 2002 13:19:14 -0800 (PST)
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
>