Data type representing an n-ary tree with node labels of type a Building such a tree is done with the empty, leaf and inner smart constructors. An example for a tree with three leafs and a root node:

tree = inner 1 [leaf 2, leaf 3, leaf 4]

This is just an alias for a list of trees, called a forest in the literature.

Construct an empty tree with no nodes.

Construct a tree with a single node from a value for the node's label.

tree : Tree Int
tree = leaf 42

Construct a new tree by inner label children, combining a number of subtrees children with a label for the new inner node which will be the root of the tree. Empty subtrees are filtered out. An example:

tree1 = inner 1 [leaf 2, leaf 3, leaf 4]
tree2 = inner 1 [leaf 2, leaf 3, leaf 4, empty]
tree1 == tree2

Construct a new tree with unfoldTree next seed, top to bottom. next will be called repeatedly with seeds, from which it should construct a label for the current tree node but also a list of seeds from which to unfold child nodes. This sort of works top to bottom compared to creating a tree bottom up by using the other primitives.

tree1 = inner 1 [leaf 2, leaf 3, leaf 4]
next seed = (seed, if seed == 1 then [2, 3, 4] else [])
tree2 = unfoldTree next 1
tree1 == tree2

Construct a new forest with unfoldForest next seeds by unfoldTree next seed for each seed in seeds. A simple specification would be

unfoldForest next seeds = List.map (unfoldTree next) seeds

isEmpty tree returns true if and only if tree is empty.

isEmpty empty == True
isEmpty (leaf 42) == False

root tree returns Nothing if tree is empty, otherwise it returns Just (label, childForest) of the root node.

tree = inner 1 [leaf 2, leaf 3, leaf 4]
root tree == Just (1, [leaf 2, leaf 3, leaf 4])
root empty == Nothing

The size of the tree, e.g. the number of nodes.

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
size tree == 7

Computes the height of the tree in O(n) time.

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
height tree == 3

levelOrder visit acc tree is a breadth-first fold over tree, visiting each node and accumulating results with visit. Nodes are visited in level-order, e.g. for a tree like

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]

nodes would be visited in order [0, 1, 4, 2, 3, 5, 6]. This is in fact the list produced by levelOrderList, but through levelOrder you also get access to the children of the current node via the second parameter of visit.

See the documentation on levelOrder. levelOrderList tree produces a list of the nodes of the tree visited in level-order, e.g. breadth-first. So:

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
levelOrderList tree == [0, 1, 4, 2, 3, 5, 6]

If you also need information on child trees instead of just the node labels, use levelOrder.

preOrder visit acc tree is a (depth-first) pre-order traversal (fold) over tree where visit is called with the label and the child sub-forest of the current node in addition to a supplied accumulator value.

Post-order traversals work top-down: When visit is called for some node, acc already contains the value of all ancestral nodes. See preOrderList for an example on the order in which nodes are visited.

See preOrder for an explanation of how post-order traversals work. Here is an example on visit order:

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
preOrderList tree == [0, 1, 2, 3, 4, 5, 6]

If you also need information on child trees instead of just the node labels, use preOrder.

postOrder visit acc tree is a (depth-first) post-order traversal (fold) over tree where visit is called with the label and the child sub-forest of the current node in addition to a supplied accumulator value.

When visit is called for some node, acc already contains the value of all sub-trees, so post-order traversal is a kind of bottom-up traversal, where all children are visited prior to their parent. See postOrderList for an example on the order in which nodes are visited.

See postOrder for an explanation of how post-order traversals work. Here is an example on visit order:

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
postOrderList tree == [2, 3, 1, 5, 6, 4, 0]

If you also need information on child trees instead of just the node labels, use postOrder.