In later literature, the 1+2b variant is usually introduced by the following definition: A rose tree [...] is either a leaf containing a value, or a node that can have an arbitrary list of subtrees.
[4] The most common definition used in functional programming (particularly in Haskell) combines 3+2b: An element of Rose α consists of a labelled node together with a list of subtrees.
Notes: General rose trees can be defined via bisimilarity of accessible pointed multidigraphs with appropriate labelling of nodes and arrows.
These structures are generalization of the notion of accessible pointed graph (abbreviated as apg) from non-well-founded set theory.
As a result of the above set-theoretic construction, the class ℛ of all rose trees is defined, depending on the sets V (ground values), Σ (arrow names) and L (node labels) as the definitory constituents.
∪ Σ) × ℛ), that is, arrows are either source-target couples or source-label-target triples according to the type of the source.
The additional symbols ⊥ and T respectively mean an indicator of a resolvable pathname and the set of type tags, T = {'1', '2b', '2c', '3b', '3c'}.
For "homogeneous" rose trees there is no need for type tagging, and their pathname map t can be defined as summarized below: In each case, there is a simple axiomatization in terms of pathnames: In particular, a rose tree in the most common "Haskell" sense is just a map from a non-empty prefix-closed and left-sibling-closed set of finite sequences of natural numbers to a set L. Such a definition is mostly used outside the branch of functional programming, see Tree (automata theory).
Notes: The diagrams below show two examples of rose trees together with the correspondent Haskell code.
The natural numbers (0,1,2 or 3) along the arrows indicate the zero-based position in which a tree appears in the subForest sequence of a particular "super-tree".
In each of the examples, the rose tree in question is labelled by 'a' and equals the value of the a variable in the code.
The second example presents a non-well-founded rose tree a built by a breadth-first constructor unfoldTree.
Its pathname map t : {0,1}⁎ → {'a','b','c'} is defined by t(p) be respectively equal to 'a' or 'b' or 'c' according to n mod 3 where n is the number of occurrences of 1 in p. The general definition provides a connection to tree data structures:
The "tree structures" are those apqs (labelled multidigraphs from the general definition) in which each node is accessible by a unique arrow path.
In the upper part of the diagram, a node-labelled ordered tree T is displayed, containing 23 nodes.
In the lower part, a rose tree R is shown that is the value of T. (In both T and R, sibling arrows are implicitly ordered from left to right.)
Notes: As it can be observed in the above text and diagrams, the term "rose tree" is controversial.
There is at least one adoption of the term "rose tree" in computer science in which "sharing of substructures" is precluded.