Programming Research Group Technical Monograph PRG-94

Jeremy Gibbons

DPhil thesis September 1991, 180 pages, ISBN 0-902928-72-4

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 a 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.

Each of these algebras brings with it a class of "structure-respecting" functions called catamorphisms. The algebras also bring with them, but not for free, classes of "structure-preserving" functions called accumulations. We study the "upwards" and "downwards" accumulations. These accumulations turn out to be the key to the solution of many problems about trees.