Skip to main content

Algebras for Tree Algorithms

Jeremy Gibbons

Abstract

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 1S 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 'structurerespecting' 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 Clod from the root towards the leaves, respectively.

Institution
OUCL
Month
September
Number
PRG94
Pages
171
Year
1991