Forests as binary trees #
This file defines Knuth's natural correspondence between forests of rose trees and binary trees, and deduces that rose trees over an encodable type are encodable. The binary tree of a nonempty forest has the root of the first tree as its root, the binary tree of that tree's children as its left subtree and the binary tree of the remaining trees as its right subtree: this is the left-child right-sibling representation. A rose tree is its root value together with the forest of its children, hence a value together with a binary tree.
Main definitions #
BinaryTree.ofForest: the binary tree of a forest, with inverseBinaryTree.toForest, bundled asBinaryTree.equivForest.RoseTree.equivProdBinaryTree: a rose tree as a value together with a binary tree.RoseTree.encodable,RoseTree.countable: the instances transported along it.
Main results #
BinaryTree.numNodes_ofForest: the correspondence preserves the number of nodes.
References #
The binary tree of a forest under the natural correspondence: nil for the empty forest,
otherwise its first tree consed onto the binary tree of the rest.
Equations
- BinaryTree.ofForest [] = BinaryTree.nil
- BinaryTree.ofForest (t :: rest) = BinaryTree.cons t (BinaryTree.ofForest rest)
Instances For
cons t r is the binary tree of the forest t :: toForest r: a node with the root value of
t, the binary tree of the children of t on the left and r on the right.
Equations
- BinaryTree.cons (RoseTree.node a cs) x✝ = BinaryTree.node a (BinaryTree.ofForest cs) x✝
Instances For
The forest of a binary tree, inverse to BinaryTree.ofForest.
Equations
- BinaryTree.nil.toForest = []
- (BinaryTree.node a l r).toForest = RoseTree.node a l.toForest :: r.toForest
Instances For
The natural correspondence between binary trees and forests.
Equations
- BinaryTree.equivForest = { toFun := BinaryTree.toForest, invFun := BinaryTree.ofForest, left_inv := ⋯, right_inv := ⋯ }
Instances For
A rose tree is its root value together with the binary tree of the forest of its children.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- RoseTree.encodable = Encodable.ofEquiv (α × BinaryTree α) RoseTree.equivProdBinaryTree