Groovy Functional Programming - Memoization

Suppose you have a computation heavy function.

def computeHeavyFunction(def number) {
    println "computeHeavyFunction called with $number"
    number + 1
}

println computeHeavyFunction(1)
println computeHeavyFunction(2)
println computeHeavyFunction(1)

In the absence of println statement, this function would have been pure. I have added the print statement just for the purpose of understanding what is going on under the hood. If you run the above code, it would produce the following output

computeHeavyFunction called with 1
2
computeHeavyFunction called with 2
3
computeHeavyFunction called with 1
2

As pure functions do not depend on any side effects, the output will solely depend on the values of input parameters. In this case, the return value will depend only on the value of number.

If you are not familiar with the concept of pure functions, this post has the details.

This leaves us with the advantage of caching the results of the function upon invocation and for the subsequent invocations with the same argument, the result can be fetched from the cache instead of computing it allover again. That's what languages with functional programming support provide. This technique is called memoization.

In Groovy, to enable memoization for a function, we have annotate the function with @Memoized AST transformation. Let's apply this AST transformation to the function computeHeavyFunction.

import groovy.transform.Memoized

@Memoized
def computeHeavyFunction(def number) {
    println "computeHeavyFunction called with $number"
    number + 1
}

println computeHeavyFunction(1)
println computeHeavyFunction(2)
println computeHeavyFunction(1)

Now this code will produce the following output upon running

computeHeavyFunction called with 1
2
computeHeavyFunction called with 2
3
2

Notice that when we invoke the function with argument 1 for the second time, the function body was not executed, but the function returned the correct result.

You may want to take a look at the slides from my FunctionalConf talk for more examples.