Multi-traversal tree decoration in a functional setting: monads versus bindings

Abstract

In this paper we consider the problem of decorating trees. We examine the special case where multiple traversals over a tree are needed for full decoration. We compare three functional approaches that do not recompute any values in successive traversals: a circular program to short-circuit multiple passes, a program with bindings from one traversal to the next to explicitly pass values and nally a monadic program that records a suitable state. Given our criteria, avoiding lazy evaluation and the ability to memoize the traversals, bindings seem to have the most advantages.