Module tree

Trees with boundary.

Trees are an ubiquitous data structure in computer science and computer algebra. This module implements trees with specified boundary, or open trees for short. This is the category theorist’s preferred notion of planar tree, since open trees are the morphisms of free multicategories.

To see the difference between (closed) trees and open trees, consider their use to represent symbolic expressions. A closed expression tree cannot, except by convention, distinguish between free variables and constants (nullary operations). However, when boundaries are admitted, the expression f(x, g(y)) with free variables x and y can be represented as an open tree of with arity 2, whereas the expression f(c, g(d)), shorthand for f(c(), g(d())), is represented as an open tree with arity 0.

A subtle but important feature of open trees is that they include identity trees, which carry a type but have no nodes. By contrast, the computer scientist’s tree is rooted, which implies that it has at least one node, namely its root.

The main use of open trees in this crate is to implement double trees.

References

Joachim Kock has proposed a combinatorial formalism for open trees (Kock 2011) and, in the same style, open graphs (Kock 2016). Kock’s trees are similar in spirit to ours but are nonplanar, i.e., are the morphisms of free symmetric multicategories.

Enums

OpenTree

An open tree, or tree with boundary.

Traits

OpenNodeRef

Extension trait for nodes in an open tree.