[Haskell-cafe] Memoization local to a function

Luke Palmer lrpalmer at gmail.com
Wed Feb 25 15:40:54 EST 2009


On Wed, Feb 25, 2009 at 10:38 AM, Dusan Kolar <kolar at fit.vutbr.cz> wrote:

>  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 suggest using
data-memocombinators<http://hackage.haskell.org/cgi-bin/hackage-scripts/package/data-memocombinators>for
this rather than rolling your own.  It accomplishes the same thing,
but
makes the choice of memo structure independent of the code that uses it (and
Memo.integral has asymptotically better performance than a list).

Luke


>
>
>  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,
>
>  Dusan
>
>
> P.S.
> Code I used for testing.
>
> module Testmemo
>   (  fibW
>   ,  fibL
>   ,  fibM
>   )  where
>
>
> fibW m = allfib !! m
>  where
>   allfib = 0:1:[allfib!!n + allfib!!(n+1) | n <- [0..]]
>
>
> fibL m =
>  let
>   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..]]
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090225/1c8a655f/attachment.htm


More information about the Haskell-Cafe mailing list