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

[Andrew Wagner]

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>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
> > 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/haskell-cafe/attachments/20081201/95573ebe/attachment.htm