[Haskell-cafe] Multiway tree vs rose tree

[Sean Leather]

On Mon, May 11, 2015 at 5:09 PM, Tara Athan wrote:

> 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.


I believe you mean Lambert Meertens here and are referring to the reference
“First steps towards the theory of rose trees” [1]. Unfortunately, this
article does not seem to be available online, but it does appear that
articles citing Meertens use your definition.

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.


I don't think there is a One True Definition for a rose tree. For example,
Ralf Hinze uses a definition like the Data.Tree one in “Polytypic Functions
Over Nested Datatypes” [2]. Also, Meertens himself uses the
value-at-the-tips definition in a later publication [3].

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.


I wouldn't worry about which definition is the “right” one. Both are
equally acceptable.

Regards,
Sean

[1] CWI, Amsterdam, 1988, Draft Rept. [SD-008].
[2] Discrete Mathematics and Theoretical Computer Science 3, 1999, 193–214.
http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/109
[3] Calculate Polytypically! Proceedings of the 8th International Symposium
on Programming Languages: Implementations, Logics, and Programs
Pages, 1996, 1-16.
http://www.kestrel.edu/home/people/meertens/publications/papers/Calculate_polytypically.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150512/9bfb9bbb/attachment.html>