Memoisation

Given the imperative features of Standard ML and the array datatype we may now construct an extremely useful function which allows the Standard ML programmer to achieve greater efficiency from programs without damaging the clarity of the functional style of programming.

The simple technique of memoisation involves storing a value once it has been computed to avoid re-evaluating the expression. We present a very simple version of the memoisation function which assumes:

1.

the function to be memoised returns integers greater than zero;

2.

the only arguments of the function are between zero and fifty.

A more general version which does not have these restrictions was implemented by Kevin Mitchell. It can be found in the Edinburgh ML library [Ber91].

fun memo f =
      let val answers = (Array.array(50,0))
          fun compute answers i =
              ( case Array.sub(answers, i) of
                  0 => let val v = f (compute answers) i 
                       in ( Array.update(answers, i, v); v )
                       end 
               |  v => v
              )
      in 
         compute answers  
      end;

The function which is to be memoised is the fibonacci function. This is presented as a ``lifted'' variant of its usual (exponential running time) version. The lifted function is called mf.

fun mf fib 0 = 1
  | mf fib 1 = 1
  | mf fib n = fib(n-1) + fib(n-2);

The memoised version of fibonacci is then simply memo mf.

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX