Two parameter memoization in Haskell

Question

I'm trying to memoize the following function:

gridwalk x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (gridwalk (x - 1) y) + (gridwalk x (y - 1))

Looking at this I came up with the following solution:

gw :: (Int -> Int -> Int) -> Int -> Int -> Int
gw f x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (f (x - 1) y) + (f x (y - 1))

gwlist :: [Int]
gwlist = map (\i -> gw fastgw (i `mod` 20) (i `div` 20)) [0..]

fastgw :: Int -> Int -> Int
fastgw x y = gwlist !! (x + y * 20)

Which I then can call like this:

gw fastgw 20 20

Is there an easier, more concise and general way (notice how I had to hardcode the max grid dimensions in the gwlist function in order to convert from 2D to 1D space so I can access the memoizing list) to memoize functions with multiple parameters in Haskell?

Answer 1

You can use a list of lists to memoize the function result for both parameters:

memo :: (Int -> Int -> a) -> [[a]]
memo f = map (\x -> map (f x) [0..]) [0..]


gw :: Int -> Int -> Int
gw 0 _ = 1
gw _ 0 = 1
gw x y = (fastgw (x - 1) y) + (fastgw x (y - 1))

gwstore :: [[Int]]
gwstore = memo gw

fastgw :: Int -> Int -> Int
fastgw x y = gwstore !! x !! y

Answer 2

Use the data-memocombinators package from hackage. It provides easy to use memorization techniques and provides an easy and breve way to use them:

import Data.MemoCombinators (memo2,integral)

gridwalk = memo2 integral integral gridwalk' where
  gridwalk' x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (gridwalk (x - 1) y) + (gridwalk x (y - 1))