Factorising folds for faster functions

Abstract

Abstract The worker/wrapper transformation is a general technique for improving the performance of recursive programs by changing their types. The previous formalisation (A. Gill & G. Hutton, J. Funct. Program. , vol. 19, 2009, pp. 227–251) was based upon a simple fixed-point semantics of recursion. In this paper, we develop a more structured approach, based upon initial-algebra semantics. In particular, we show how the worker/wrapper transformation can be applied to programs defined using the structured pattern of recursion captured by fold operators, and illustrate our new technique with a number of examples.