Skip to main content

Upwards and Downwards Accumulations on Trees

Jeremy Gibbons

Abstract

An \em accumulation\/ is a higher-order operation over structured objects of some type; it leaves the shape of an object unchanged, but replaces each element of that object with some accumulated information about the other elements. Upwards and downwards accumulations on trees are two instances of this scheme; they replace each element of a tree with some function—in fact, some homomorphism—of that element's descendants and of its ancestors, respectively. These two operations can be thought of as passing information up and down the tree. \par We introduce these two accumulations, and show how together they solve the so-called prefix sums problem.

Book Title
Mathematics of Program Construction
Editor
R. S. Bird and C. C. Morgan and J. C. P. Woodcock
Note
A revised version appears in the Proceedings of the Massey Functional Programming Workshop‚ 1992
Pages
122–138
Publisher
Springer−Verlag
Series
Lecture Notes in Computer Science
Volume
669
Year
1993