Talk:Rose tree

This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing Low‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing Low This article has been rated as Low-importance on the project's importance scale.

Tip: Anchors are case-sensitive in most browsers. This article contains broken links to one or more target anchors: [[Tree (data structure)#Nested list|nested list]] The anchor (#Nested list) is no longer available because it was deleted by a user before. [[Tree (data structure)#nested-dictionary|nested dictionary]] The anchor (#nested-dictionary) is no longer available because it was deleted by a user before. [[Tree (data structure)#Nested data|nested data]] The anchor (#Nested data) is no longer available because it was deleted by a user before. [[Tree (data structure)#Encoding by sequences|Encoding by sequences]] The anchor (#Encoding by sequences) is no longer available because it was deleted by a user before. [[Tree (data structure)#nested-dictionary|Nested dictionary]] The anchor (#nested-dictionary) is no longer available because it was deleted by a user before. [[Tree (data structure)#Accessible pointed graph|unfolding]] The anchor (#Accessible pointed graph) is no longer available because it was deleted by a user before. [[Tree (data structure)#Ordered tree|ordered tree]] Anchor Tree (data structure)#Ordered tree links to a specific web page: Ordered tree. The anchor (#Ordered tree) is no longer available because it was deleted by a user before. The anchors may have been removed, renamed, or are no longer valid. Please fix them by following the link above, checking the page history of the target pages, or updating the links. Remove this template after the problem is fixed | Report an error

... is nothing else but a Tree (data structure). There is nothing special about "rose trees" as made up in the Haskell wiki; they are prototypes of abstract trees.

No need for an article on this made-up terminology. --138.246.2.177 (talk) 14:13, 30 September 2014 (UTC)Reply

Nope, tree is a more general concept since it also includes trees of fixed branching factor, and the term rose tree for trees with variable branching factor is established in, e.g., Parallel implementation of tree skeletons (J. Parallel and Distributed Computing, 1996). Reverted, but maybe we'll want to rename this page to multi-way tree (currently a redirect, which your bold move broke). QVVERTYVS (hm?) 14:54, 30 September 2014 (UTC)Reply

Thanks for the references. But even with those, I would consider this obscure - what do they have, 300 citations in total? If you search for "rose tree" on Google Scholar, you mostly get non-computer-science hits. Multiway tree seems to be much more common (e.g. used in the KDB-tree publication, which has 1189 citations), and apparently Knuth called them "Multiway tree", too. So why abuse the term of a "rose tree"? --138.246.2.177 (talk) 09:28, 6 October 2014 (UTC)Reply

I'd suggest to make multi-way tree a redirect on an appropriate subsection in Tree (data structure), and Rose tree either a redirect to the botanic use, or a disambiguation page. --138.246.2.177 (talk) 09:30, 6 October 2014 (UTC)Reply

The original definition of rose tree (in a computer science context) appears to be quite different from that of a multiway tree. I haven't been able to get a copy (yet) of the original paper "First steps towards the theory of rose trees", but a slightly later references (http://www.sciencedirect.com/science/article/pii/0167642390900237) that cites it says "Definition 2.13 (Rose trees). For each type A, define the type of rose trees over A by: ... The type of rose trees, then, has two constructors: the leaf constructor A -> Ap, and the node constructor Ap* -> Ap, which governs a list of subtrees." In other words, rose trees don't have labels on nodes, only on the leaves. The reference here (http://doc.utwente.nl/66626/1/db-utwente-0000003528.pdf) also uses this definition of rose tree. Further the reference cited above (http://ftp.qucis.queensu.ca/TechReports/Reports/1995-380.pdf) and on the page (http://www.gatsby.ucl.ac.uk/~heller/brt.pdf) also uses this definition.

I suggest that the article be rewritten to give the original definition in the lead, and have a section in the body where the (mis)use of the term rose tree in Haskell is mentioned. If there is no objection, I may give it a go. --Greentaratoo (talk) 12:06, 11 May 2015 (UTC)Reply