Pull-Ups, Push-Downs, and Passing It Around Exercises in Functional Incrementalization

Abstract. Programs in languages such as Haskell are often datatype-centric and make extensive use of folds on that datatype. Incremen-talization of such a program can significantly improve its performance by transforming monolithic atomic folds into incremental computations. Functional incrementalization separates the recursion from the applica-tion of the algebra in order to reduce redundant computations and reuse intermediate results. In this paper, we motivate incrementalization with a simple example and present a library for transforming programs using upwards, downwards, and circular incrementalization. Our benchmarks show that incrementalized computations using the library are nearly as fast as handwritten atomic functions.