Functions and Traversals in Combination

In this paper we describe a new traversal organization inspired by ideas behind type-generic traversals that clearly separates traversal code and computation, implemented in an object-oriented setting. By delegating portions of the traversal and computation to sepa-rate functions we provide a library and methodology to develop succinct solutions to data-structure transformation problems. Be-cause we provide an implementation of these new traversals via reection in Java, all previous tools and libraries are still avail-able and functionality can be extended and composed to deal with data structure reorganization using inheritance and encapsulation. We demonstrate the use of these abstractions by solving a few pro-totypical language problems: calculation of de Bruijn indices and type-checking. Categories and Subject Descriptors D.3.3 [Programming Lan