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.
Details
| 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 |
Links
Related pages
|
People |
|
|
Activities |