Memoization of multi-parameter function in Haskell

Question

The following example of a function using memoization is presented on this page:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0..] !!)
    where fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)

What if we wanted to memoize a multi-parameter function, though? We could create a 'multiplied Fibonacci', for example, that would be defined f(m,n) = m*f(m,n-2) + m*f(m,n-1). I modified the code above for this 'multiplied Fibonacci' function as follows:

mult_fib :: Integer -> Int -> Integer
mult_fib mult = (map (m_fib mult) [0..] !!)
    where m_fib _ 0 = 0
          m_fib _ 1 = 1
          m_fib m n = m*(mult_fib m (n-2)) + m*(mult_fib m (n-1))

The runtime of the modified function is exponential, even though the original is linear. Why does this technique not work in the second case? Also, how could the function be modified to make use of memoization (without using library functions)?

In this case you can just remove m_fib's first argument,replace m by mult and mult_fib m by m_fib. In a sense, this would define a family of memoized functions indexed by mult. — Vitus
– Vitus, Commented Aug 19, 2013 at 0:32
@Vitus: right, though it doesn't quite work like that (recursing on the un-memoised m_fib would destroy the performance advantage). — leftaroundabout
– leftaroundabout, Commented Aug 19, 2013 at 0:49
@leftaroundabout: Right, I forgot the one layer of indirection which is your multFib', sorry. — Vitus
– Vitus, Commented Aug 19, 2013 at 1:39
So the issue is that GHC can't (or shouldn't?) recognize that mult_fib mult and mult_fib m are the same partially applied functions? — John G
– John G, Commented Aug 19, 2013 at 22:32
@JohnG: This is one of the things you usually do not want to recognize because it can lead to space leaks; showing that this transformation doesn't introduce such leak is much harder task indeed. Also, you do not want to depend on optimizations in this case; you want the memoization to be reliable. It's better to be explicit about the sharing and have a guarantee that your code will do the right thing no matter the optimizations. — Vitus
– Vitus, Commented Aug 20, 2013 at 0:46

Vitus · Accepted Answer · 2013-08-19 01:47:31Z

8

As said by Vitus, in your example in can be done quite simply. The correct implementation of this idea:

multFib :: Integer -> Int -> Integer
multFib mult = multFib'
    where multFib' = (map m_fib [0..] !!)
          m_fib 0 = 0
          m_fib 1 = 1
          m_fib n = mult * (multFib' $ n-2) + mult * (multFib' $ n-1)

However, the memoisation is not quite as powerful as in your example here: it'll only serve to optimise single function calls, but the result list will in general not be stored between subsequent calls of multFib with the same mult argument.

To achieve that, you'll need to index your memisation lookup on both arguments, like so:

multFibFullMemo :: Int -> Int -> Integer
multFibFullMemo = \mult n -> memo_table !! mult !! n
 where memo_table = [ [m_fib mult' n' | n'<-[0..]] | mult' <- [0..] ]
       m_fib _ 0 = 0
       m_fib _ 1 = 1
       m_fib mult n = m * (multFibFullMemo mult $ n-2) + m * (multFibFullMemo mult $ n-1)
        where m = toInteger mult

Quite obviously, this won't be efficient if you intend to use it with larger mult arguments: it'll always need to skip to a list with the length of that number.

More sophisticated memoisation that doesn't suffer from such issues is provided by libraries such as MemoTrie.

edited Aug 19, 2013 at 1:47

Vitus

12k8 gold badges39 silver badges64 bronze badges

answered Aug 19, 2013 at 0:48

leftaroundabout

121k6 gold badges185 silver badges337 bronze badges

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

3 Comments

Vitus Over a year ago

As a rule of thumb, GHC will evaluate any given expression at most once every time the enclosing lambda is entered. If you leave the lambda and enter it again with the same value later, the expression can (and usually will) be recomputed.

Vitus Over a year ago

Anyways, since it looks like my two edits got merged together and only the last edit message remains: the original list comprehension was inside the \mult n -> lambda so it was recomputed everytime you called multFibFullMemo.

Anton Over a year ago

As i understood, to get memoized something we have to put it in at the top of lamda expression. And make all computations inside this lambda. It seems like play with compiler features.

Chris · Accepted Answer · 2013-12-26 02:09:16Z

1

Here is a version using MemoTrie:

import Data.MemoTrie

multFib :: Integer -> Int -> Integer          
multFib = memo2 multFib'
  where multFib' m 0 = 0
        multFib' m 1 = 1
        multFib' m n = m * (multFib m (n-2)) + m * (multFib m (n-1))

answered Dec 26, 2013 at 2:09

Chris

9731 gold badge11 silver badges16 bronze badges

Collectives™ on Stack Overflow

Memoization of multi-parameter function in Haskell

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related