[Haskell-cafe] Re: Binary Trees missing on hackage

[Christian Maeder]

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.html)
> <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 at gmail.com
> <mailto:wagner.andrew at 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 at dfki.de <mailto: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 <mailto:Libraries at haskell.org>
>         http://www.haskell.org/mailman/listinfo/libraries
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe