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?

Milkmaid

Answer 1

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))

Freeload

Shouldn't gridwalk call back to gridwalkMemo instaid of itself? – Tried

I'm chosing this because of brevity and vote count, but both sth's and John's answers helped me understand memoization in Haskell better, thanks! – Milkmaid

You may need cabal install data-memocombinators. – Forestay

Answer 2

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

Heikeheil

This should be higher up. While not as easy as the others, this is by far the most insightful answer. – Alliaceous

Answer 3

Here is a version using Data.MemoTrie from the MemoTrie package to memoize the function:

import Data.MemoTrie(memo2)

gridwalk :: Int -> Int -> Int
gridwalk = memo2 gw
  where
    gw 0 _ = 1
    gw _ 0 = 1
    gw x y = gridwalk (x - 1) y + gridwalk x (y - 1)

Tried

Answer 4

If you want maximum generality, you can memoize a memoizing function.

memo :: (Num a, Enum a) => (a -> b) -> [b]
memo f = map f (enumFrom 0)

gwvals = fmap memo (memo gw)

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

This technique will work with functions that have any number of arguments.

Edit: thanks to Philip K. for pointing out a bug in the original code. Originally memo had a "Bounded" constraint instead of "Num" and began the enumeration at minBound, which would only be valid for natural numbers.

Lists aren't a good data structure for memoizing, though, because they have linear lookup complexity. You might be better off with a Map or IntMap. Or look on Hackage.

Note that this particular code does rely on laziness, so if you wanted to switch to using a Map you would need to take a bounded amount of elements from the list, as in:

gwByMap :: Int -> Int -> Int -> Int -> Int
gwByMap maxX maxY x y = fromMaybe (gw x y) $ M.lookup (x,y) memomap
 where
  memomap = M.fromList $ concat [[((x',y'),z) | (y',z) <- zip [0..maxY] ys]
                                              | (x',ys) <- zip [0..maxX] gwvals]

fastgw2 :: Int -> Int -> Int
fastgw2 = gwByMap 20 20

I think ghc may be stupid about sharing in this case, you may need to lift out the x and y parameters, like this:

gwByMap maxX maxY = \x y -> fromMaybe (gw x y) $ M.lookup (x,y) memomap

Ithaca

How can you pass gw to memo when memo expects a function of type (a -> b) but gw is (Int -> Int -> Int)? Also, wouldn't minBound produce negative indices when applied to something of type Int? – Milkmaid

@Philip K - the type b in a->b unifies with Int -> Int, it's perfectly fine to memoize a function generator. The negative index thing is a bug, though. I'll edit my answer. – Ithaca