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