7

Here is a simple memoization in Haskell for function f1 taking one argument (yes, Fibonacci):

f1 = [calc n | n <- [0..]]
     where calc 0 = 0
           calc 1 = 1
           calc n = f1 !! (n-1) + f1 !! (n-2)

Now, how would this be done for a function f2 that takes 2 arguments, or f3 that takes 3?

For f2, is the best approach a list of lists? Or can a different data structure be used?

f2 = [[calc n m | n <- [0..]] | m <- [0..]]
     where calc 0 0 = 0
           calc a b = // ...something using (f2 !! a !! b)

Of for f3 a b c, given that max_a * max_b * max_c is manageable, how would this memoization / dynamic programming work?

I'm looking for the simplest / most straight forward approach, using standard Haskell libs if possible.

Edit

As suggest in Chris Taylor's answer, I tried using MemoCombinators.hs v0.5.1 but it fails for me, like this:

Could not find module `Data.IntTrie'
Use -v to see a list of the files searched for.

and

Illegal symbol '.' in type
Perhaps you intended -XRankNTypes or similar flag
to enable explicit-forall syntax: forall <tvs>. <type>

I need this to run in "plain" haskell, this version: GHCi, version 7.6.3

Any tips to get it going?

Improve this question

2 Answers 2

Reset to default
12

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
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Hi Chris, thanks very much for your answer, I think I need to use option 1. and pull out the bare minimum of code from data-memocombinators package, it looks like I just need type Memo and memo2, memo3, does that sound right?
@vikingsteve You will also need integral from MemoCombinators. I'll take a look at your errors. It looks like you don't have the data-inttrie library. It should be installed automatically if you run cabal install data-memocombinators but you could also try cabal install data-inttrie to get it. Does that help?
@vikingsteve Note that data-memocombinators uses two extensions, Rank2Types and ScopedTypeVariables (package description here). If you don't want to depend on packages that use extensions then this won't be suitable. However, you won't need to enable those extensions in your own modules, so it may be acceptable for you.
Thanks Chris. I think I will go and read the data-inttrie library (it seems to be some super-efficient bitwise data structure, perhaps I can do something similar with Data.Map ?) and then use type Memo, wrap, integral and memo2 to have a custom, "no external libraries" implementation of what I need.
@vikingsteve You should also check out this page on memoization. My experience with using a Data.Map for memoization was that it was very difficult to get it to work for functions with more than 2 arguments, because I couldn't get the maps to be lazy enough. But maybe you will have better luck!
|
2

Since Haskell is lazy, you can memoise a function by calling it on itself.

for example, one fibonacci generator in Haskell is this:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

(from http://www.haskell.org/haskellwiki/The_Fibonacci_sequence)

which, uses the resulting list as its own storage for state.

Improve this answer

1 Comment

Ok, thanks. Can I use this lazy memoization with a function with 2 or 3 arguments that returns one Int?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.