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

Answer 1

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.