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

Abstract. Programs in functional programming languages with alge-braic datatypes are often datatype-centric and use folds or fold-like func-tions. 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, down-wards, and circular incrementalization. We also give a datatype-generic implementation for the library and demonstrate the incremental zipper, a zipper extended with attributes.