[Haskell-cafe] Memoization local to a function

Dusan Kolar kolar at fit.vutbr.cz
Wed Feb 25 12:38:36 EST 2009

Dear all,

  I have a function a computation of which is quite expensive, it is 
recursively dependent on itself with respect to some other function 
values - we can roughly model its behaviour with fib function (returns 
n-th number of Fibonacci's sequence). Unfortunately, it is not fib, it 
is far more complicated. Nevertheless, for demonstration of my 
question/problem I will use fib, it's quite good.

  I want to store results in a list (array, with its strong size limit 
that I do not know prior to computation, is not suitable) and then pick 
them up using (!!) operator. Well, if the list is "global" 
function/constant then it works quite well. Unfortunately, this is not, 
what I would like to have. Nevertheless, local version does not work.

  Could someone point me to some text that explains it? Memoization text 
on wiki does not seem to be helpful. Time/operation consumption is 
deduced from number of reductions reported by hugs and winhugs (tested 
both on Linux and Windows).

  Thank you for hints,


Code I used for testing.

module Testmemo
    (  fibW
    ,  fibL
    ,  fibM
    )  where

fibW m = allfib !! m
    allfib = 0:1:[allfib!!n + allfib!!(n+1) | n <- [0..]]

fibL m =
    allfib = 0:1:[allfib!!n + allfib!!(n+1) | n <- [0..]]
  in allfib !! m

fibM n = myallfib !! n
myallfib = 0:1:[myallfib!!n + myallfib!!(n+1) | n <- [0..]]

More information about the Haskell-Cafe mailing list