Scala: partially evaluate a function and cache fixed values

Question

Is there an easy way to cache the fixed values of a partially applied function, in a pure functional way.

Code sample:

scala> def f(x:Int,y:Int)={
    def expensiveCalculation(num:Int)={
        println("I've spent a lot of time(!) calculating square of "+num)
        num*num
    }
    lazy val x2=expensiveCalculation(x)
    lazy val y2=expensiveCalculation(y)
    lazy val r=x2+y2
    r
}

scala> def g=f(1,_:Int)

scala> g(2)
I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 2
res18: Int = 5

scala> g(3)
I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 3
res19: Int = 10

But I don't want the expensiveCalculation to be called two times for num=1. Since the expensiveCalculation is side effect free, there is no problem in saving the results (please don't consider the side effect of printing on output stream in my sample code).

I can implement what I'm looking for using OOP style by saving the state manually (though it is not very clean if you want to write a general reusable code for it).

I think in FP where every function is side effect free, it should be even easier to achieve this goal. Actually I can't think of a strict limitation in using this as the default behavior in a purely functional language (except some practical concerns like amount of memory needed for the cache and etc).

Answer 1

You can leverage the fact that Scala is an OOP and FP language at the same time and that functions in Scala are objects.

object CachedFunction extends App {

  val f = new Function2[Int, Int, Int] {
    def expensiveCalculation(num: Int) = {
      println("I've spent a lot of time(!) calculating square of " + num)
      num * num
    }

    var precomputed: Map[Int, Int] = Map()

    def getOrUpdate(key: Int): Int =
      precomputed.get(key) match {
        case Some(v) => v
        case None =>
          val newV = expensiveCalculation(key)
          precomputed += key -> newV
          newV
      }

    def apply(x: Int, y: Int): Int =
      getOrUpdate(x) + getOrUpdate(y)
  }

  def g = f(1, _: Int)

  g(2)
  g(3)
  g(3)
  f(1, 2)
}

prints:

I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 2
I've spent a lot of time(!) calculating square of 3

I've changed f from def to val - that allows f to be an object that "stores" the function rather than just being a method that runs its whole body every time. In this case only apply is run every time and instance variables of the function object are preserved. The rest is OOPish kind of way.

Although this can be considered immutable for the caller because the returned result does not change over time it's not thread safe.You might want to use some sort of synchronized map for storing cached values.

EDIT: After I wrote this I googled for "function memoization" and got these similar solutions. They are more generic though:

Scala Memoization: How does this Scala memo work?

Is there a generic way to memoize in Scala?

http://eed3si9n.com/learning-scalaz-day16

Apparently there is even something in Scalaz :)

EDIT:

The problem is that Scala does not eagerly evaluate arguments of the function even if the function is partially applied or curried. It simply stores the values of the arguments. Here is an example:

object CachedArg extends App {

  def expensiveCalculation(num: Int) = {
    println("I've spent a lot of time(!) calculating square of " + num)
    num * num
  }

  val ff: Int => Int => Int = a => b => expensiveCalculation(a) + expensiveCalculation(b)
  val f1 = ff(1) // prints nothing

  val e1 = expensiveCalculation(1) // prints for 1
  val f: (Int, Int) => Int = _ + expensiveCalculation(_)
  val g1 = f(e1, _: Int)
  g1(2) // does not recalculate for 1 obviously
  g1(3)
}

Prints:

I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 2
I've spent a lot of time(!) calculating square of 3

This shows that you can still evaluate an argument once manually and "save" it by partially applying it to the function (or currying). I think that's what you were going after. To have a more convenient way you can use this approach:

object CachedFunction extends App {

  val f = new Function1[Int, Int => Int] {
    def expensiveCalculation(num: Int) = {
      println("I've spent a lot of time(!) calculating square of " + num)
      num * num
    }

    def apply(x: Int) =
      new Function[Int, Int] {
        val xe = expensiveCalculation(x)

        def apply(y: Int) = xe + expensiveCalculation(y)
      }
  }

  val g1 = f(1) // prints here for eval of 1
  g1(2)
  g1(3)
}

Prints:

I've spent a lot of time(!) calculating square of 1
I've spent a lot of time(!) calculating square of 2
I've spent a lot of time(!) calculating square of 3

However, in both last examples, memoizaition is local to the function object. You have to reuse the same function object for it to work. Unlike that, in the first example memoizaition is global to the scope where the function is defined.

Answer 2

A simple implementation:

lazy val _f=  scala.collection.mutable.Map[Int, Int]()
def f(x: Int)(y: Int) = {
  def expensiveCalculation(num: Int) = {
    println("I've spent a lot of time(!) calculating square of " + num)
    num * num
  }
  def _cached(a:Int) =_f.getOrElseUpdate(a, expensiveCalculation(a))

  lazy val r = _cached(x)+_cached(y)
  r
}
val g=f(1)_
g(2)
g(3)

Answer 3

I'm must be missing something, but why a simple closure doesn't work for you?

scala> def f(x:Int): Int => Int ={
     |       
     |       def expensiveCalculation(num:Int)={
     |         println("I've spent a lot of time(!) calculating square of "+num)
     |         num*num
     |       }
     |       val cached=expensiveCalculation(x)
     |     
     |       def add(num: Int) = {
     |         cached + num
     |       }
     |       
     |       add
     |       
     |     }
f: (x: Int)Int => Int

scala> val g = f(1)
I've spent a lot of time(!) calculating square of 1
g: Int => Int = <function1>

scala> g(2)
res0: Int = 3

scala> g(3)
res1: Int = 4

scala> g(4)
res2: Int = 5

scala>