[Haskell-cafe] Retaining functions in memory

[Ryan Ingram]

Use memoization.  Here's an example:

cabal-install MemoTrie


import Data.MemoTrie

fib_fix :: (Integer -> Integer) -> Integer -> Integer
fib_fix _ n | n < 0 = error "invalid input"
fib_fix _ 0 = 1
fib_fix _ 1 = 1
fib_fix rec n = rec (n-1) + rec (n-2)

-- 'tie the knot' on a recusrive function
func_fix :: ((a -> b) -> (a -> b)) -> (a -> b)
func_fix f = let rec = f rec in rec

-- memoized knot tying; 'memo' stops us from recomputing the same value more
than once.
memo_fix :: HasTrie a => ((a -> b) -> (a -> b)) -> (a -> b)
memo_fix f = let rec = memo (f rec) in rec

-- try comparing the performance of these two on large arguments
fib_slow, fib_fast :: Integer -> Integer
fib_slow = func_fix fib_fix
fib_fast = memo_fix fib_fix


On Tue, Jul 26, 2011 at 2:53 AM, Siddhartha Gadgil <
siddhartha.gadgil at gmail.com> wrote:

>       I have been making programs for mathematical applications
> (low-dimensional topology) in Haskell, which I find a delight to code
> in. However, the execution is slow, and this seems to be because
> recursively defined functions seem to be recomputed. For example
> f(100) needs f(15) which needs f(7) ... The dependencies are not
> obvious to the compiler.
>       I was looking for a way to retain the values of a specific
> function in memory. Is there some way to do this.
>                                         Thanks,
>                                         Siddhartha
>
> _______________________________________________
> 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/20110727/e44fb86d/attachment.htm>