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?

sth · Accepted Answer · 2011-04-05 14:19:48Z

20

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 5, 2011 at 14:19

sth

231k56 gold badges288 silver badges370 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

marcusklaas Over a year ago

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

fuz · Accepted Answer · 2011-04-05 15:21:42Z

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 5, 2011 at 15:21

answered Apr 5, 2011 at 15:06

fuz

94.8k27 gold badges216 silver badges391 bronze badges

3 Comments

HaskellElephant Over a year ago

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

Philip Kamenarsky Over a year ago

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!

Sergey Orshanskiy Over a year ago

You may need cabal install data-memocombinators.

Chris Stryczynski · Accepted Answer · 2019-02-01 23:25:07Z

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 1, 2019 at 23:25

Chris Stryczynski

34.9k60 gold badges210 silver badges334 bronze badges

answered Apr 5, 2011 at 15:12

HaskellElephant

9,8884 gold badges40 silver badges67 bronze badges

Comments

John L · Accepted Answer · 2011-04-05 16:46:08Z

3

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

edited Apr 5, 2011 at 16:46

answered Apr 5, 2011 at 14:46

John L

28.1k4 gold badges76 silver badges89 bronze badges

2 Comments

Philip Kamenarsky Over a year ago

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?

John L Over a year ago

@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.

Collectives™ on Stack Overflow

Two parameter memoization in Haskell

4 Answers 4

1 Comment

3 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

3 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related