| Linear-time breadth-first tree algorithms: An exercise in the arithmetic of folds and zips (1993) | |||||||||||||||||
Abstract | |||||||||||||||||
| . This paper is about an application of the mathematics of the zip, reduce (fold) and accumulate (scan) operations on lists. It gives an account of the derivation of a linear-time breadth-first tree traversal algorithm, and of a subtle and efficient breadth-first tree labelling algorithm. Keywords. Derivation, functional programming, breadth-first, traversal, labelling. 1 Introduction The algorithms which are developed in this paper relate trees to sequences in a way that respects the breadth-first ordering of the nodes of the tree: nodes nearer the root are earlier in the ordering, and nodes on the same level are ordered from left to right. We distinguish between finite and infinite sequences, which we call lists and streams respectively. Lists of elements of type ff are modelled as the least solution list.ff of the equation list.ff = [ ] j ff :: list.ff That is, the empty list [ ] has type list.ff , and if x has type ff and xs has type list.ff then x :: xs has type list.ff . We... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||