## Memoization in scala

A simple, yet effective optimization technique

I've been off work ill today, but reading was getting on my nerves, so I decided to do more work in scala, and wrote some objects to do easy Memoization. I thought I needed them to optimise something else that I was doing, then found a better way to do it without classical memoization (sigh).

The code was heavily based on something I found here (hat tip michid), with minor tweaks of my own. Here's how you use the memo classes anyway:

``````scala> import com.uncarved.helpers.Memoize
scala> val circArea =
|       Memoize((r:Double)=>Math.Pi * Math.pow(r,2))
circArea: com.uncarved.helpers.Memoize.MemoizedFunction1[Double,Double] = <function>

scala>   val area = circArea(2)
area: Double = 12.566370614359172
``````

So you can use something like a function and it seems to do the right thing. "But how", you may well ask, "do I know it's actually memoizing and this isn't all a big trick?". A fair and honest question. We need to add a function that has a side-effect so we can demonstrate that it is in fact doing the right thing.

We need a function that will print something to the terminal when the calculation is actually invoked. When it isn't, it will return the same result, but without any printing.

``````scala>   val cylVol = Memoize {
|       (r:Double, h:Double) =>
|         val vol = Math.Pi * Math.pow(r,2) * h
|         println("Radius: " + r + " Height: " +
|             h + " Volume: " + vol)
|       vol
|  }
cylVol: com.uncarved.helpers.Memoize.MemoizedFunction2[Double,Double,Double] = <function>
``````

The first time we invoke our function it hits the print statement:

``````scala> cylVol(3,4.5)
Radius: 3.0 Height: 4.5 Volume: 127.23450247038662
res1: Double = 127.23450247038662
``````

...but when we invoke the function again on identical arguments, the cached result is used, so we don't see the print.

``````scala> cylVol(3,4.5)
res2: Double = 127.23450247038662
``````

If the arguments change, a fresh invocation is made.

``````scala> cylVol(3,4)
Radius: 3.0 Height: 4.0 Volume: 113.09733552923255
res3: Double = 113.09733552923255
``````

You can get the code and libs by using sbaz to update your uncarved-helpers package, or just via the tarball. For the curious, here's the full text of the scala code.