We touched on how pure functions offer referential transparency in the previous blog. In this blog, we discuss another benefit from this list: pure functions are memoizable.

Let's start with a little exercise.

What's `2 + 3`

?

Don't be shy, please do the math.

You got the answer, of course.

Let's try that again, what's 2 + 3?

Obviously, the answer is still the same. That's because pure functions produce the same result for a given set of arguments, no matter how many times they're called—we discussed this in a previous blog. But, we can use this property of pure functions as an advantage. Let's see how.

What's `332 + 544`

?

This involves a bit more effort that the previous arithmetic required. Once you complete, move on to the next step.

OK, once more, what's `332 + 544`

?

You got it again. Though, I bet, this time you were way faster than the first time. You've become so good at this so fast!

You're probably saying "I cached it!"

Sure, but there was more. You cached the result only because you knew that `+`

is pure and the operands are immutable in that expression; otherwise, you'd not be caching.

What you did—caching—is called memoization.

Memoization is an optimization technique. The main goal is to reduce the computational time at the expense of space, that is, by storing or caching the results of computations based on the values of the operands or arguments.

Memoization is an example of referential transparency. That is, when we use memoization, we're replacing an expression with its value. However, referential transparency does not always mean memoization. For example, referential transparency may use expression substitution, like replacing `2 + 3`

with `5`

at compile time. On the other hand, memoization involves maintaining a cache table.

When programming, we may implement a `Map`

to store the operands or arguments as keys and the corresponding result of the expression as the values. Some languages also provide specialized library functions for memoization. Let's take a look at a couple of examples.

Here's an example in Groovy:

```
def fib;
fib = { n ->
if (n < 2)
1
else
fib(n - 1) + fib(n - 2)
}
def start = System.nanoTime()
println(fib(40))
def end = System.nanoTime()
println((end - start)/1.0e9)
```

`fib`

is a variable that refers to a closure. The closure recursively computes the Fibonacci value for a given position `n`

. Running `groovy sample.groovy`

produces the following result:

```
165580141
16.15600300
```

The code took a little over `16`

seconds to run. It performs repeated calls to the function `fib`

for different positions when the recursion unfolds. Momoization will save time.

The Groovy library provides a convenience function to memoize. Let's change the previous code to use that.

```
def fib;
fib = { n ->
if (n < 2)
1
else
fib(n - 1) + fib(n - 2)
}.memoize()
def start = System.nanoTime()
println(fib(40))
def end = System.nanoTime()
println((end - start)/1.0e9)
```

The call to `memoize()`

returns another closure. This closure will check if the value for the given parameter has already been computed. If so, it will return the cached value instead of executing the underlying closure. If the value does not exist, it will compute, cache, and return.

Here's the output of the modified code:

```
165580141
0.042137395
```

Thanks to memoization, the code took significantly less time to produce the same result.

Groovy provides a few variations for the `memoize()`

function, with various options to tailor the memory usage.

Clojure also has a `memoize`

function. Here's an example from Clojure.

```
(def fib (fn [n]
(if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))
(time (println (fib 40)))
(def mem-fib (memoize (fn [n]
(if (< n 2) 1 (+ (mem-fib (- n 1)) (mem-fib (- n 2)))))))
(time (println (mem-fib 40)))
```

`fib`

is a variable that refers to a lambda expression. The lambda expression computes the Fibonacci value. `mem-fib`

, on the other hand, is a variable that refer to the result of calling `memoize`

on a lambda expression. Within the second lambda expression, the anonymous function calls the memoized version.

The call to `fib`

will take way more time than the call to `mem-fib`

, as we can see from the output of running the code:

```
165580141
"Elapsed time: 2217.313342 msecs"
165580141
"Elapsed time: 1.070711 msecs"
```

Convenience functions like this can greatly reduce our efforts to memoize. The degree of support, however, varies across languages.

Memoization makes sense only if the result of the function will be the same for a given set of arguments or input. Since pure functions have this property, they're readily memoizable.

In this series of blogs, we've looked at four benefits so far. In the next blog we'll look at another benefit: easier to parallelize.