Programming Research Group Technical Report TR-31-92

Linear-time breadth-first tree algorithms:
an exercise in the arithmetic of folds and zips

Geraint Jones and Jeremy Gibbons

1992, 4pp.

This is a paper about an application of the mathematics of zip, fold (reduce) and accumulate (scan) operations on lists. It gives an account of the derivation of a linear-time breadth-first enumeration function, and of a subtle and efficient breadth-first tree labelling function.

This paper is available as a 36,365 byte compressed PostScript file.