http://blog.tmorris.net/you-lazy-thunk/
In scala, there's the lazy keyword which will make an assignment lazy.
But I didn't know of anything that would trade space for time, ie caching.
I was reading about clojure (lisp on the java) programming-clojure ,
and they mentioned the built in memoization http://en.wikipedia.org/wiki/Memoization
So I decided to do my own implementation of memoization in scala.
def mem[A,R](func: A=>R) : A=>R = {
var cache = Map[A,R]()
(a:A) => {
if (cache.contains(a)) {
cache(a)
} else {
val result = func(a)
cache += a -> result
result
}
}
}
val double = (x:Int) => {
println("double "+x)
x*2
}
double(2)
double(2)
val memDouble = mem(double)
memDouble(2)
memDouble(2)
memDouble(4)
memDouble(4)
when you run this in the repl you get:
scala> double(2)
double 2
res13: Int = 4
scala> double(2)
double 2
res13: Int = 4
scala> double(2)
double 2
res13: Int = 4
double 2
res9: Int = 4
scala> memDouble(2)
res10: Int = 4
scala> memDouble(2)
res10: Int = 4
scala> memDouble(4)
double 4scala> memDouble(4)
res11: Int = 8
scala> memDouble(4)
res12: Int = 8
as you can see from the repl output;
When you call double, it executes the body everytime you execute the function. ie it prints double 2 each time.
The memDouble function is different however, the first time you call the memDouble function, it prints, but the second time (with the same arguments), it just gives you the value.
Using this mem function, we can automagically cache the results of any function that takes a single argument.
In order for it to work with functions of any arity (number of arguments), we need to implement different versions for each arity.
We can then wrap those functions up in a singleton object, to hide the arity details.
Here I've done it for 1 and 2 argument functions, it's pretty easy to extrapolate. The key to the cache map becomes a tuple of the arguments.
object Mem {
def mem1[A,R](func: A=>R) : A=>R = {
var cache = Map[A,R]()
(a:A) => {
if (cache.contains(a)) {
cache(a)
} else {
val result = func(a)
cache += a -> result
result
}
}
}
def mem2[A,B,R](func:(A,B)=>R) : (A,B)=>R = {
var cache = Map[(A,B),R]()
(a:A,b:B) => {
if (cache.contains((a,b))) {
cache((a,b))
} else {
val result = func(a,b)
cache += (a,b) -> result
result
}
}
}
...
def apply[A,R](func:A=>R) = mem1(func)
def apply[A,B,R](func:(A,B)=>R) = mem2(func)
...
}
object Test extends Application {
val mult = (x:Int,y:Int) => { println("mult"); x*y }
val double = (x:Int) => { println("double"); mult(x,2) }
val hello = (x:String) => { println("hello"); "hello "+x }
val memDouble = Mem(double)
memDouble(2)
memDouble(2)
memDouble(4)
memDouble(4)
memDouble(4)
val memMult = Mem(mult)
memMult(2,3)
memMult(2,3)
memMult(4,4)
memMult(4,4)
val memHello = Mem(hello)
memHello("me")
memHello("me")
case class MyObj(val value:Int) {
def multiply(x:Int) = x*value
}
val memMyTriple = Mem(MyObj(3).multiply(_:Int))
memMyTriple(2)
memMyTriple(2)
}
As you can see, it's not just for basic functions, it also works with methods on objects as well.
I've found these functional concepts fairly straightforward to implement in scala, the only issue being with different function arities.
This is an effective way to use space in order to save time, while leaving your source code relatively unaffected.
