Re: question about kinds
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 ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: question about kinds
At 2002-01-18 13:10, Hal Daume III wrote: >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. If the Tree type constructor is Traversable, then it's Traversable no matter what it's applied to. You've provided a instance for traversing "Trees of anything", it's going to overlap with any instance for "Trees of Lists". -- Ashley Yakeley, Seattle WA ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: question about kinds
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| [EMAIL PROTECTED] 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| [EMAIL PROTECTED] > 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| [EMAIL PROTECTED] > > than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume > > > > > > ___ > > Glasgow-haskell-users mailing list > > [EMAIL PROTECTED] > > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users > > > > > ___ > Haskell mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell > ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: question about kinds
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| [EMAIL PROTECTED] 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| [EMAIL PROTECTED] > than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume > > > ___ > Glasgow-haskell-users mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users > ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
question about kinds
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| [EMAIL PROTECTED] than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
