Update! The final version is now available.
Andres Löh, Johan Jeuring, and I have submitted a paper to IFL 2009.
Pull-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization
Abstract Programs in functional programming languages with algebraic datatypes are often datatype-centric and use folds or fold-like functions. Incrementalization of such a program can significantly improve its performance. Functional incrementalization separates the recursion from the calculation and significantly reduces redundant computation. In this paper, we motivate incrementalization with a simple example and present a library for transforming programs using upwards, downwards, and circular incrementalization. We also give a datatype-generic implementation for the library and demonstrate the incremental zipper, a zipper extended with attributes.
This is the result of work that has previously been mentioned on this blog:
- Smart constructors
- Incremental fold, a design pattern
- Incremental attributes
- Latest on the incremental fold and attributes
- "Upwards and downwards accumulations on trees" translated into Haskell
We would be happy to have any feedback.
Update! Here's the (completely messy, badly formatted, undocumented, and screwy) code used in the paper if you want to have a go at it.
