memoize -- record results of function evaluation for future use

Description

memoize f -- produces, from a function f, a new function that 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 : FunctionClosure

i2 : time fib 28
     -- used 0.946028 seconds

o2 = 514229

i3 : fib = memoize fib

o3 = fib

o3 : FunctionClosure

i4 : time fib 28
     -- used 0.000051523 seconds

o4 = 514229

i5 : time fib 28
     -- used 1.313e-6 seconds

o5 = 514229

An optional second argument to memoize provides a list of initial values, each of the form x => v, where v is the value to be provided for the argument x.

Alternatively, values can be provided after defining the memoized function using the syntax f x = v. A slightly more efficient implementation of the above would be

i6 : fib = memoize( n -> fib(n-1) + fib(n-2) )

o6 = fib

o6 : FunctionClosure

i7 : fib 0 = fib 1 = 1;

i8 : fib 28

o8 = 514229

The function memoize operates by constructing a MutableHashTable, in which the arguments are used as keys for accessing the return value of the function. This mutable hash table can be obtained using the function memoizeValues, as follows.

i9 : peek memoizeValues fib

o9 = MutableHashTable{0 => 1      }
                      1 => 1
                      2 => 2
                      3 => 3
                      4 => 5
                      5 => 8
                      6 => 13
                      7 => 21
                      8 => 34
                      9 => 55
                      10 => 89
                      11 => 144
                      12 => 233
                      13 => 377
                      14 => 610
                      15 => 987
                      16 => 1597
                      17 => 2584
                      18 => 4181
                      19 => 6765
                      20 => 10946
                      21 => 17711
                      22 => 28657
                      23 => 46368
                      24 => 75025
                      25 => 121393
                      26 => 196418
                      27 => 317811
                      28 => 514229

That hash table can be replaced by an empty one with the function memoizeClear.

i10 : memoizeClear fib

i11 : peek memoizeValues fib

o11 = MutableHashTable{}

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 arguments themselves. See also CacheTable.

Ways to use memoize :

memoize(Function)
memoize(Function,List)

For the programmer

The object memoize is a method function.