memoize

memoize f -- produces, from a function f, a new function which behaves the same as f, but remembers previous answers to be provided the next time the same arguments are presented.

i1 : fib = n -> if n <= 1 then 1 else fib(n-1) + fib(n-2)



o1 = fib



o1 : Function

i2 : time fib 16

     -- used 0.08 seconds



o2 = 1597

i3 : fib = memoize fib



o3 = fib



o3 : Function

i4 : time fib 16

     -- used 0.01 seconds



o4 = 1597

i5 : time fib 16

     -- used 0. seconds



o5 = 1597

The function memoize operates by constructing a MutableHashTable in which the argument sequences are used as keys for accessing the return value of the function.

Warning: when the value returned by f is null, it will always be recomputed, even if the same arguments are presented.

Warning: the new function created by memoize will save references to all arguments and values it encounters, and this will often prevent those arguments and values from being garbage-collected as soon as they might have been. If the arguments are implemented as mutable hash tables (modules, matrices and rings are implemented this way) then a viable strategy is to stash computed results in the arugments themselves!