[Haskell-cafe] Memoisation

[Jeremy Shaw]

At Mon, 26 Feb 2007 07:54:56 +1000,
Tony Morris wrote:
> 
> [1  <multipart/signed (7bit)>]
> [1.1  <text/plain; ISO-8859-1 (quoted-printable)>]
> I have a backtracking algorithm that I need to memoise with. Rather than
> go into the intricacies of the algorithm, I figure (and hope) the
> factorial function is trivial enough to point out my problem.

Have you seen the paper, Modular Lazy Search for Constraint
Satisfaction Problems by Thomas Nordin and Andrew Tolmach?

http://web.cecs.pdx.edu/~apt/jfp01.ps

It starts with simple backtracking, and then adds 'memoising' to
extend the algorithm to conflict directed backtracking, backmarking,
forward checking, dynamic variable ordering, and other fun stuff.

Although the algorithms are designed around solving constraint
satisfaction problems, is is pretty easy to apply the technique a
domain specific solver as well.

I definitely recommend reading the paper if you are doing any sort of
backtracking-type solvers.

j.