Hm, I've been thinking about this this morning as I've gone about my commute. I could indeed imagine a class like the following that had multiple implementations like you're talking about:

class Tree t where
  drawTree :: t String -> String
  flatten :: t a -> [a]
  etc. (see http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Tree.html)

I think that for this to be valuable, though, we would need to show that there are functions which can take a generic Tree t and do something useful with it. Still, I suspect there's something there. Maybe I'll take a stab at it this week sometime.

On Mon, Dec 1, 2008 at 6:24 AM, Andrew Wagner <wagner.andrew@gmail.com> wrote:
The reasons I've always heard for this is that 1.) It's so easy to define a tree and 2.) There are tons of different variations of trees and what you can do with them. Not that I 100% agree, just what I've always heard.

On Mon, Dec 1, 2008 at 6:09 AM, Christian Maeder <Christian.Maeder@dfki.de> wrote:
Hi,

I was surprised that I could not find a "classical" binary tree data
structure on hackage, mainly for teaching purposes, like:

 data BinTree a = Nil | Node (BinTree a) a (BinTree a)

with a couple of utility functions and instances (i.e. in-order traversal).

Surely, one may argue, that such a tree can always be defined on the fly
when needed, but nobody would argue so for lists or tuples. (Although
I've rarely seen someone redefining lists, it is quite common to
introduce user-defined products or enumerations.)

There are rose trees in Data.Tree and many other variants of trees are
conceivable, ie.

 data Boom a = Leaf a | Node (Boom a) (Boom a)

or a kind of combination:

 data BinLeafTree a b =
    Leaf b
  | Node (BinLeafTree a b) a (BinLeafTree a b)

I don't know, why I find the above BinTree most important. I'm not even
sure if such a tree could be re-used for Search- or AVL-trees that need
strict fields with redundant size or height counters for efficiency reasons.

In any case I would find such a data type at least as useful as
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/OneTuple

Who would supply and maintain such a package? Or did I simply not search
hard enough?

Cheers Christian

P.S. I took the (non-empty) "Boom" from the Boom-Hierarchy described in
"An Exploration of the Bird-Meertens Formalism" by Roland Backhouse
1988, Groningen

_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://www.haskell.org/mailman/listinfo/libraries