[Haskell-cafe] Question: Lazy Incremental Evaluation and Haskell?

Benjamin Redelings I benjamin.redelings at duke.edu
Thu Oct 6 23:55:10 CEST 2011

Hi all,

     I'm not sure this is the right forum for this question.  If so,
please let me know where else might be more appropriate.  My question
is, roughly, is there already an existing framework for incremental
evaluation in Haskell?  That is, if I write a program using Haskell, and
then change a small part of this program, can the modified program
re-use any results which are calculated by the first, unmodified
program?  This would be really useful for CPU-intensive statistical
software and other scientific computing.

     For example, if I have the expression (x+y)+z, where x=1, y=2, and
z=4, then I need not recalculate (x+y) when z changes.  However, (x+y)+z
must still be recalculated.  This is useful in speeding up statistical
software that optimizes a complex function of many arguments, when only
one argument changes at a time.  It is also useful for Markov chain
Monte Carlo (MCMC) since usually one changes only one argument at a time
there as well.

     I haven't seen much work on this using the lambda calculus for this
since JH Field's Ph.D. Thesis "Incremental Reduction in the Lambda
Calculus".  There are a number of programs that represent the
calculation as a static DAG (directed, acyclic graph), but this can't
handle functions very well.  I'm currently trying to write an
interpreter that could do this correctly, but I don't want to reinvent
the wheel.  Can anyone point me to where I could find more information
about how to do this in a Haskell framework?

Benjamin Redelings

More information about the Haskell-Cafe mailing list