Binary Trees missing on hackage

Andrew Wagner wagner.andrew at gmail.com
Mon Dec 1 06:24:11 EST 2008


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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20081201/8e976edb/attachment-0001.htm


More information about the Libraries mailing list