Binary Trees missing on hackage

Christian Maeder Christian.Maeder at
Mon Dec 1 06:09:09 EST 2008


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

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

More information about the Libraries mailing list