my tech blog

To iterate is human, to recurse divine

Memoization

This technique feels like it’s mandatory to describe if you are writing a book about functional programming. That might be because it emphasize the side effect free property of languages in this genre. However this technique can be used in a imperative language as well.

So what is memoization? I would sum it up as an optimization technique to cache calculations done by a function in run-time.

The beauty with side effect free functions is that with the same input we will always receive the same result no matter when/where we call it. This make it very easy to store the calculated result into a dictionary and use it at a later time.

Lets show the memoization in action with a simple example in F#:

This memoization function works fine in this simple case, however we would get in trouble if it were a recursive function that we wanted to memoize. The solution for a recursive function might be good material for a part two post of the memoization function :-)

If you would like to find out more about this technique I recommend you to search the net on these keywords: memoization, memo and memoised function.

Finally the memoization technique was “invented” by Professor Donald Michie, [“‘Memo’ functions: and machine learning”, Donald Michie, Nature, 218, 19-22, 1968]. Here is his site: Donald Michie Home Page

Comments