[Haskell-cafe] Multiway tree vs rose tree

[Tara Athan]

Perhaps I need to clarify my remark. I am not in way suggesting that the 
code in Data-Tree.html be changed. I am suggesting that the 
documentation of the source and wiki pages be changed so that the 
structure is referred to (correctly) as a multiway tree, but not 
(incorrectly) as a rose tree.

As to naming of trees, every published paper I have found so far that 
uses the term "rose tree" is consistent with the original definition 
from Meerten, who is the one who coined the name in the first place, to 
indicate a quite specialized tree that only has values at the tips, not 
the nodes. It is only in Haskell-related literature that it is stated 
that rose tree is the same as multiway tree. Since there is a perfectly 
good name for multiway tree, I don't see why there would be any need to 
have another name for it - why not let the name "rose tree" be used for 
what it was originally intended.

BTW, I have a stake in this, as I am working on a case where I need (a 
generalization of ) rose trees, not multiway trees, and I ran across 
this different usage of "rose tree" during the literature search.

(Generalized) rose trees are interesting in their own right because they 
are (or are isomorphic to, depending on your perspective) the free 
monad. When the functor used to generate the free monad is List, then it 
becomes a rose tree.

Tara

On 5/11/15 9:53 AM, Ivan Lazar Miljenovic wrote:
> On 11 May 2015 at 22:50, Tara Athan <taraathan at gmail.com> wrote:
>> Hi - I am new to this list, and the only archive I could find is the Mailman
>> archive, which is next to impossible to search. So this may be a topic that
>> has been previously discussed, I don't know...
>>
>> The documentation at
>> https://hackage.haskell.org/package/containers-0.3.0.0/docs/Data-Tree.html
>> says that a rose tree is another name for multiway tree. But this is not
>> true according to my understanding of the accepted definition in the CS
>> literature (see e.g.
>> http://doc.utwente.nl/66626/1/db-utwente-0000003528.pdf)
>> Rose trees do not have labels at the nodes, only at the leaves (aka tips).
> There are various different definitions of tree structures (I once
> started a literature review of this, but never finished it).  Note
> that if you allow values in all nodes, you can always represent a tree
> where only leaves have values of type `a' as an arbitrary tree with
> nodes of type `Maybe a' (but you can't statically enforce this, at
> least with the definition in Data.Tree: for that, you would have to
> generalise the tree structure even more to have a distinct type
> variable just for the leaf nodes with a new constructor, thus
> complicating usage of the data structure).
>
>