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?

score 19 · Answer 1 · answered Apr 05 '11 at 14:19

19

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

answered Apr 05 '11 at 14:19

sth

222,467
53
283
367

2

This should be higher up. While not as easy as the others, this is by far the most insightful answer. – marcusklaas Nov 20 '14 at 00:04

fuz · Accepted Answer · 2011-04-05T15:21:42.647

9

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

edited Apr 05 '11 at 15:21

answered Apr 05 '11 at 15:06

fuz

88,405
25
200
352

Shouldn't gridwalk call back to gridwalkMemo instaid of itself? – HaskellElephant Apr 05 '11 at 15:10
1

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! – Philip Kamenarsky Apr 06 '11 at 09:39
You may need `cabal install data-memocombinators`. – Sergey Orshanskiy Oct 27 '15 at 00:47

score 5 · Answer 3 · edited Feb 01 '19 at 23:25

5

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)

edited Feb 01 '19 at 23:25

Chris Stryczynski

30,145
48
175
286

answered Apr 05 '11 at 15:12

HaskellElephant

9,819
4
38
67

John L · Answer 4 · 2011-04-05T16:46:08.193

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

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`? — Philip Kamenarsky, Apr 05 '11 at 15:19
@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. — John L, Apr 05 '11 at 16:16

Two parameter memoization in Haskell

4 Answers4

Linked

Related