# 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