[Haskell-cafe] Multiway tree vs rose tree
taraathan at gmail.com
Mon May 11 15:09:22 UTC 2015
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.
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
>> 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.
>> 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).
More information about the Haskell-Cafe