question about kinds

[Hal Daume III]

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

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

Re: question about kinds

[Ashley Yakeley]

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