Recalling a Multiparameter Function in Haskell

Question

The following example 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 want to memoize a multi-parameter function? We could create, for example, a “Fibonacci multiplied" that would be defined by f(m,n) = m*f(m,n-2) + m*f(m,n-1) . I modified the above code 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 mn = m*(mult_fib m (n-2)) + m*(mult_fib m (n-1)) 

The runtime of the changed function is exponential, although the original value is linear. Why does this method not work in the second case? Also, how can you change a function to use memoization (without using library functions)?

Answer 1

As Vitus said, in your example this 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, memoisation is not as strong as in your example here: it will only be used to optimize calls to individual functions, but the result list will not be saved at all between subsequent calls to multFib with the same mult .

To do this, you will need to index your memisation search for both arguments, for example:

 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 

Obviously, this will not be effective if you intend to use it with larger mult arguments: it always needs to skip the list with the length of this number.

More complex memoisation that does not suffer from such problems is provided by libraries such as MemoTrie .

Answer 2

Here is the version using MemoTrie :

 import Data.MemoTrie multFib :: Integer -> Int -> Integer multFib = memo2 multFib' where multFib' m 0 = 0 multFib' m 1 = 1 multFib' mn = m * (multFib m (n-2)) + m * (multFib m (n-1))