Re: Binary Trees missing on hackage

I find classes for sequences, collections (edison) and graphs (fgl) and your proposed trees a bit awkward. I'ld like to see the actual data types first. Like for lists I can imagine a whole bunch of useful functions for BinTree (below) that are already implemented multiple times for user defined binary trees (in other libraries). Cheers Christian Andrew Wagner wrote:

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.h...) http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Tree.h...

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 mailto: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 mailto: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 mailto:Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

------------------------------------------------------------------------

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe