Generic Incremental Computation for Regular Datatypes in Haskell

Abstract

Incremental computation is a method which tries to save time by only recomputing the output of changed input. A technique of incremental computation is memoization. Memoization stores the result of a computation and returns the cached result when the same input occurs again. As a result, a large part of memoization becomes dependent on determining if the input is equal to an already cached input. This can become problematic when a computation is given a large recursive data structure. To improve the performance of memoization this paper introduces an incremental algorithm which determines the equality in constant time. This is accomplished by storing hash values/digests, which describe the internal structure, inside the data structure. Furthermore, the incremental algorithm describes how to efficiently update the digests, using a Zipper, when the data structure changes. The incremental algorithm is then implemented using Datatype-generic programming, to support the class of regular datatypes. Meanwhile, the usage of the generic implementation stays the same for the developers as writing the non-incremental algorithm in Haskell. Finally, we show that the performance is better than the non-incremental version with minimal extra memory usage, when correctly tuned with cache policies.