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

[Andrew Wagner]

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
<[EMAIL PROTECTED]>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
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/libraries
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[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)

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 <[EMAIL PROTECTED]>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 <[EMAIL PROTECTED]
> > 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
>> [EMAIL PROTECTED]
>> http://www.haskell.org/mailman/listinfo/libraries
>>
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[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)
> 
> 
> 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 <[EMAIL PROTECTED]
> > 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
> <[EMAIL PROTECTED] > 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
> [EMAIL PROTECTED] 
> http://www.haskell.org/mailman/listinfo/libraries
> 
> 
> 
> 
> 
> 
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[Brandon S. Allbery KF8NH]

On 2008 Dec 1, at 8:28, 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:


One can indeed --- but it turns out to be even more general than just  
trees.  Go look at the Foldable and Traversable classes.


--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED]
system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED]
electrical and computer engineering, carnegie mellon universityKF8NH


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