Rose tree

In computing, a multi-way tree or rose tree is a tree data structure with a variable and unbounded number of branches per node.[1] The name rose tree for this structure is prevalent in the functional programming community, e.g., in the context of the Bird–Meertens formalism.[2]

For the species of rhododendron, see Rhododendron maximum.

Naming

The name "rose tree" was coined by Lambert Meertens to evoke the similarly-named, and similarly-structured, common rhododendron.[3]

We shall call such trees rose trees, a literal translation of rhododendron (Greek ῥόδον = rose, δένδρον = tree), because of resemblance to the habitus of this shrub, except that the latter does not grow upside-down on the Northern hemisphere.

Definition

The following is definitions in Haskell:

data Tree a = Tree a [Tree a]
data Tree a = Cofree [] a

Sources
  1. Bird, Richard (1998). Introduction to Functional Programming using Haskell. Hemel Hempstead, Hertfordshire, UK: Prentice Hall Europe. p. 195. ISBN 0-13-484346-0.
  2. Malcolm, Grant (1990). "Data structures and program transformation". Science of Computer Programming. 14 (2): 255–279. doi:10.1016/0167-6423(90)90023-7.
  3. Meertens, Lambert. "First steps towards the Theory of Rose Trees" (PDF): 22. Cite journal requires |journal= (help)
  • Rose tree on the Haskell wiki
  • Bayesian Rose Trees
  • Data.Tree, an implementation of basic rose tree operations in the Haskell containers package
  • [Skillicorn, David B. (1995). "Parallel implementation of tree skeletons"]
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.