Algebras for tree algorithms

This thesis presents an investigation into the properties of various algebras of trees. In particular, we study the influence that the structure of a tree algebra has on the solution of algorithmic problems about trees in that algebra. The investigation is conducted within the framework provided by the Bird-Meertens formalism, a calculus for the construction of programs by equational reasoning from their specifications.We present three different tree algebras: two kinds of binary tree and a kind of general tree. One of the binary tree algebras, called "hip trees", is new. Instead of being built with a single ternary operator, hip trees are built with two binary operators which respectively add left and right children to trees which do not already have them; these operators enjoy a kind of associativity property.Each of these algebras brings with it with a class of "structure-respecting" functions called catamorphisms; the definition of a catamorphism and a number of its properties come for free from the definition of the algebra, because the algebra is chosen to be initial in a class of algebras induced by a (cocontinuous) functor. Each algebra also brings with it, but not for free, classes of "structure-preserving" functions called accumulations. An accumulation is a function that preserves the shape of a structured object such as a tree, but replaces each element of that object with some catamorphism applied to some of the other elements. The two classes of accumulation that we study are the "upwards" and "downwards" accumulations, which pass information from the leaves of a tree towards the root and from the root towards the leaves, respectively. Upwards and downwards accumulations turn out to be the key to the solution of many problems about trees. We derive accumulation-based algorithms for a number of problems; these include the parallel prefix algorithm for the prefix sums problem, algorithms for bracket matching and for drawing binary and general trees, and evaluators for decorating parse trees according to an attribute grammar.