cache using functional callbacks/ proxy pattern implementation scala

Question

How to implement cache using functional programming

A few days ago I came across callbacks and proxy pattern implementation using scala. This code should only apply inner function if the value is not in the map. But every time map is reinitialized and values are gone (which seems obivous.

How to use same cache again and again between different function calls

class Aggregator{
  def memoize(function: Function[Int, Int] ):Function[Int,Int] = {
    val cache = HashMap[Int, Int]()
     (t:Int) => {
      if (!cache.contains(t)) {
        println("Evaluating..."+t)
        val r = function.apply(t);
        cache.put(t,r)
        r
      }
       else
      {
        cache.get(t).get;
      }
    }
  }

  def memoizedDoubler = memoize( (key:Int) => {
    println("Evaluating...")
    key*2
    })
  }

object Aggregator {

  def main( args: Array[String] ) {
    val agg = new Aggregator()
    agg.memoizedDoubler(2)
    agg.memoizedDoubler(2)// It should not evaluate again but does
    agg.memoizedDoubler(3)
    agg.memoizedDoubler(3)// It should not evaluate again but does

 }

Put `cache` outside of the function. – Dima Apr 12 '16 at 10:16 — Dima, Apr 12 '16 at 10:16

Brian Agnew · Answer 1 · 2016-04-12T11:30:33.017

1

Aren't you declaring a new Map per invocation ?

def memoize(function: Function[Int, Int] ):Function[Int,Int] = {
    val cache = HashMap[Int, Int]()

rather than specifying one per instance of Aggregator ?

e.g.

class Aggregator{
  private val cache = HashMap[Int, Int]()
  def memoize(function: Function[Int, Int] ):Function[Int,Int] = {

edited Apr 12 '16 at 11:30

answered Apr 12 '16 at 10:13

Brian Agnew

268,207
37
334
440

A field which is a mutable collection inside a method. **is that a good idea for distributed program like spark** – Pushpendra Jaiswal Apr 12 '16 at 11:25
Bit confused. You can't declare a field within a method – Brian Agnew Apr 12 '16 at 12:51

score 1 · Accepted Answer · edited May 23 '17 at 10:28

I see what you're trying to do here, the reason it's not working is that every time you call memoizedDoubler it's first calling memorize. You need to declare memoizedDoubler as a val instead of def if you want it to only call memoize once.

  val memoizedDoubler = memoize( (key:Int) => {
    println("Evaluating...")
    key*2
  })

This answer has a good explanation on the difference between def and val. https://stackoverflow.com/a/12856386/37309

score 0 · Answer 3 · answered Apr 21 '16 at 01:24

To answer your question:

How to implement cache using functional programming

In functional programming there is no concept of mutable state. If you want to change something (like cache), you need to return updated cache instance along with the result and use it for the next call.

Here is modification of your code that follows that approach. function to calculate values and cache is incorporated into Aggregator. When memoize is called, it returns tuple, that contains calculation result (possibly taken from cache) and new Aggregator that should be used for the next call.

class Aggregator(function: Function[Int, Int], cache:Map[Int, Int] = Map.empty) {

  def memoize:Int => (Int, Aggregator) = {
    t:Int =>
      cache.get(t).map {
        res =>
          (res, Aggregator.this)
      }.getOrElse {
        val res = function(t)
        (res, new Aggregator(function, cache + (t -> res)))
      }
  }
}

object Aggregator {

  def memoizedDoubler = new Aggregator((key:Int) => {
    println("Evaluating..." + key)
    key*2
  })


  def main(args: Array[String]) {
    val (res, doubler1)  = memoizedDoubler.memoize(2)
    val (res1, doubler2)  = doubler1.memoize(2)
    val (res2, doubler3)  = doubler2.memoize(3)
    val (res3, doubler4)  = doubler3.memoize(3)
  }
}

This prints:

Evaluating...2
Evaluating...3

cache using functional callbacks/ proxy pattern implementation scala

How to implement cache using functional programming

3 Answers3