Factorising Folds for Faster Functions

Graham Hutton and Mauro Jaskelioff and Andy Gill, Submitted to the Journal of Functional Programming special issue on Generic Programming, Oct 2009

AbstractThe worker/wrapper transformation is a general technique for improving the performance of recursive programs by changing their types. The previous formalisation (Gill & Hutton, 2009) was based upon a simple fixed point semantics of recursion. In this article 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.
 
ResourcespdfExtended Version (pdf)
 
BibTeX
@unpublished{WWF52009,
  author = {Graham Hutton and Mauro Jaskelioff and Andy Gill},
  title = {Factorising Folds for Faster Functions},
  note = {Submitted to the Journal of Functional Programming special issue on Generic Programming},
  abstract = {The worker/wrapper transformation is a general technique for improving the performance of recursive programs by changing their types. The previous formalisation (Gill & Hutton, 2009) was based upon a simple fixed point semantics of recursion. In this article 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.},
  month = {Oct},
  year = {2009}
}