Memoization / dynamic programming in Haskell on 2 or 3 arguments

Question

Here is a simple memoization in Haskell for function f1 taking one argument (yes, Fibonacci):

f1 = [calc n | n <- [0..]]
     where calc 0 = 0
           calc 1 = 1
           calc n = f1 !! (n-1) + f1 !! (n-2)

Now, how would this be done for a function f2 that takes 2 arguments, or f3 that takes 3?

For f2, is the best approach a list of lists? Or can a different data structure be used?

f2 = [[calc n m | n <- [0..]] | m <- [0..]]
     where calc 0 0 = 0
           calc a b = // ...something using (f2 !! a !! b)

Of for f3 a b c, given that max_a * max_b * max_c is manageable, how would this memoization / dynamic programming work?

I'm looking for the simplest / most straight forward approach, using standard Haskell libs if possible.

Edit

As suggest in Chris Taylor's answer, I tried using MemoCombinators.hs v0.5.1 but it fails for me, like this:

Could not find module `Data.IntTrie'
Use -v to see a list of the files searched for.

and

Illegal symbol '.' in type
Perhaps you intended -XRankNTypes or similar flag
to enable explicit-forall syntax: forall <tvs>. <type>

I need this to run in "plain" haskell, this version: GHCi, version 7.6.3

Any tips to get it going?

Answer 1

I can think of two approaches -

1. MemoCombinators

The easiest way to create generic memoized functions is probably to use the data-memocombinators library. Say you have the following two argument function.

f :: Int -> Int -> Integer
f 0 _ = 1
f _ 0 = 1
f a b = f (a-1) b + f a (b-1)

You can try calling f 20 20, but be prepared to wait a while. You can easily write a memoizing version with

import Data.MemoCombinators

f :: Int -> Int -> Integer
f = memo2 integral integral f'
  where
    f' 0 _ = 1
    f' _ 0 = 1
    f' a b = f (a-1) b + f a (b-1)

Note that it's important that in the helper function f' the recursive calls are not to f' but rather to the memoized function f. Calling f 20 20 now returns almost instantly.

2. Lists of Lists of ...

If you know that the arguments to your function are Int and that you will need to use all of 0..n and 0..m to compute f (n+1) (m+1) then it might make sense to use the list of lists approach. However, note that this scales badly with the number of arguments to the function (in particular, it is difficult to tell at a glance what the function is doing if you have more than 2 arguments).

flist :: [[Integer]]
flist = [[f' n m | m <- [0..]] | n <- [0..]]
 where
  f' _ 0 = 1
  f' 0 _ = 1
  f' a b = flist !! (a-1) !! b + flist !! a !! (b-1)

f :: Int -> Int -> Integer
f a b = flist !! a !! b

Answer 2

Since Haskell is lazy, you can memoise a function by calling it on itself.

for example, one fibonacci generator in Haskell is this:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

(from http://www.haskell.org/haskellwiki/The_Fibonacci_sequence)

which, uses the resulting list as its own storage for state.