Memoization / dynamic programming in Haskell on 2 or 3 arguments

dynamic-programming, haskell, memoization

Solution

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

Problem

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?

Original source