Typed combinators for generic traversal

Lacking support for generic traversal, functional programming languages suffer from a scalability problem when applied to large-scale program transformation problems. As a solution, we introduce emph{functional strategies: typeful generic functions that not only can be applied to terms of any type, but which also allow generic traversal into subterms. We show how strategies are modelled inside a functional language, and we present a combinator library including generic traversal combinators. We illustrate our technique of programming with functional strategies by an implementation of the emph{extract method refactoring for Java.