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:
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.