Add memoization to a recursively defined haskell function

Question

I've solved a dynamic programming problem in Haskell (actually a Project Euler problem) with what boils down to a generalisation of the Fibonacci sequence:

 f(n) = f(n-1) + f(n-2)
 g(n) = g(n-1) + g(n-3)
 h(n) = h(n-1) + h(n-4)

There are a few more functions like this, and because of the size of the problem, I've had to add memoization, which is pretty trivial, like so:

memF = (map f' [0 ..] !!)
  where f' x | x <=1 = 1
        f' 2         = 2
        f' x         = memF(x-1) + memF(x-2)


memG = (map f' [0 ..] !!)
  where f' x | x <=2 = 1
        f' 3         = 2
        f' x         = memG(x-1) + memG(x-3)

This works fine, so I can get the answer as (memF 100) + (memG 100) + ... and I've answered the question, but the repeated code is ugly, and I'd rather define a single function to generate the memoized functions, so something like:

mem d = (map f' [0 ..] !!)
  where f' x | x < d  = 1
        f' x | x == d = 2
        f' x          = (mem d) (x-1) + (mem d)(x-d)

And then answer as mem 2 100 + mem 3 100 + ... This fails, or at least the caching doesn't work, I guess because the array is recreated with each call, I suppose I could use the StateMonad or a memoization library, but I'd be interested to know if there is a way to do this without Monads. Is there please?

chi · Accepted Answer · 2019-07-20 21:56:54Z

4

You need another binding to avoid the recursive call to mem d:

mem d = g
  where g = (map f' [0 ..] !!)
        f' x | x < d  = 1
        f' x | x == d = 2
        f' x          = g (x-1) + g (x-d)

Also be careful when you are calling mem, since each call to mem will create its own cache. E.g.

mem 10 x + mem 10 y

will not cache anything, while

let g = mem 10 in g x + g y

will use the same cache.

An alternative could be to use a single "global" cache for all the calls mem d x, using memoization on the pair (d,x). This looks a bit more tricky to achieve, though.

answered Jul 20, 2019 at 21:56

chi

117k4 gold badges143 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user118165 Over a year ago

OK that works, thank you: so the binding captures the function call and delta value. Nice.

chi Over a year ago

@user118165 Yes, that's the idea.

user118165 Over a year ago

The global cache is an interesting idea -- I guess you'd use a map? Of course as you point out it doesn't add much in this case. Thanks again.

chi Over a year ago

@user118165 I'm not sure about what I would use right now. Data.Map.Map is strict, so that can not be used. We need a lazy data structure.

Collectives™ on Stack Overflow

Add memoization to a recursively defined haskell function

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related