Combining Memoisation and Change Propagation for Automatic Incremental Evaluation of Haskell Arrow Programs

Abstract

Implementing re-use of previously computed values is hard and is therefore often dismissed by programmers: a missed opportunity for improved computational efficiency. Memoisation and change propagation are techniques for implementing the re-use of previously computed values. Using existing libraries either destroys the conciseness of the code or is too limited for a real-world application where fine-grained control over the amount of memory used is necessary. We combine both memoisation and change propagation and provide clean interfaces through the ubiquitous applicative, monad, and arrow interfaces.