Fibonacci memoization in Scala with Memo.mutableHashMapMemo

Question

I am trying implement the fibonacci function in Scala with memoization

One example given here uses a case statement: Is there a generic way to memoize in Scala?

import scalaz.Memo
lazy val fib: Int => BigInt = Memo.mutableHashMapMemo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-2) + fib(n-1)
}

It seems the variable n is implicitly defined as the first argument, but I get a compilation error if I replace n with _

Also what advantage does the lazy keyword have here, as the function seems to work equally well with and without this keyword.

However I wanted to generalize this to a more generic function definition with appropriate typing

import scalaz.Memo
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
    var value : Int = 0
    if( n <= 1 ) { value = n; }
    else         { value = fibonachi(n-1) + fibonachi(n-2) }
    return value
}

but I get the following compilation error

cmd10.sc:4: type mismatch;
 found   : Int => Int
 required: Int
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
                                                                         ^Compilation Failed
Compilation Failed

So I am trying to understand the generic way of adding adding a memoization annotation to a scala def function

Your "generalization" actually makes the definition much worse in more ways than one: using mutable state for no reason, risking integer overflows ... Your immediate problem is that you are trying to assign the result of `mutableHashMapMemo.apply` (which is a function) to an `Int` ... but that's probably not worth solving for the reasons I mentioned above. — Dima, Jan 01 '19 at 15:24
The more general question I am trying to ask is how to take a pre-existing `def` function and add a mutable/immutable memoization annotation/wrapper to it inline. What would be the correct way to write `def fibonachi(n: Int) : Int` as a memoized function (without using a case statement)? — James McGuigan, Jan 01 '19 at 15:40
The correct way is the first snippet you showed. Case statement is idiomatic scala, and the best to express the definition in this case, but if you for some reason wanted to get rid of, it would look something like `{ n => if(n <= 1) n else fib(n-1) + fib(n-2)}` — Dima, Jan 01 '19 at 18:07
@Dima I think the OP is confused between the definition of the `fib` function itself and the definition of the `apply` function inside `Memo.mutableHashMapMemo` — Boris the Spider, Jan 01 '19 at 18:12
@OP your variable declaration, `if ... else` then `return` is very un-idiomatic. Very _Java_ even. May I suggest you read [my answer about `if` in Scala](https://stackoverflow.com/a/23480812/2071828)? — Boris the Spider, Jan 01 '19 at 18:16
"_It seems the variable `n` is implicitly defined as the first argument_". Nope. `n` is the variable in the case when the input is not `0` or `1`. Might I suggest some reading around [Pattern Matching in Scala](https://docs.scala-lang.org/tour/pattern-matching.html). Either way, you cannot replace `n` with `_` because then `n` is not captured. — Boris the Spider, Jan 01 '19 at 18:22

score 5 · Accepted Answer · answered Jan 01 '19 at 20:28

One way to achieve a Fibonacci sequence is via a recursive Stream.

val fib: Stream[BigInt] = 0 #:: fib.scan(1:BigInt)(_+_)

An interesting aspect of streams is that, if something holds on to the head of the stream, the calculation results are auto-memoized. So, in this case, because the identifier fib is a val and not a def, the value of fib(n) is calculated only once and simply retrieved thereafter.

However, indexing a Stream is still a linear operation. If you want to memoize that away you could create a simple memo-wrapper.

def memo[A,R](f: A=>R): A=>R =
  new collection.mutable.WeakHashMap[A,R] {
    override def apply(a: A) = getOrElseUpdate(a,f(a))
  }

val fib: Stream[BigInt] = 0 #:: fib.scan(1:BigInt)(_+_)
val mfib = memo(fib)
mfib(99)  //res0: BigInt = 218922995834555169026

score 3 · Answer 2 · answered Jan 02 '19 at 02:37

The more general question I am trying to ask is how to take a pre-existing def function and add a mutable/immutable memoization annotation/wrapper to it inline.

Unfortunately there is no way to do this in Scala unless you are willing to use a macro annotation for this which feels like an overkill to me or to use some very ugly design.

The contradicting requirements are "def" and "inline". The fundamental reason for this is that whatever you do inline with the def can't create any new place to store the memoized values (unless you use a macro that can re-write code introducing new val/vars). You may try to work this around using some global cache but this IMHO falls under the "ugly design" branch.

The design of ScalaZ Memo is used to create a val of the type Function[K,V] which is often written in Scala as just K => V instead of def. In this way the produced val can contain also the storage for the cached values. On the other hand syntactically the difference between usage of a def method and of a K => V function is minimal so this works pretty well. Since the Scala compiler knows how to convert def method into a function, you can wrap a def with Memo but you can't get a def out of it. If for some reason you need def anyway, you'll need another wrapper def.

import scalaz.Memo

object Fib {

  def fib(n: Int): BigInt = n match {
    case 0 => BigInt(0)
    case 1 => BigInt(1)
    case _ => fib(n - 2) + fib(n - 1)
  }

  // "fib _" converts a method into a function. Sometimes "_" might be omitted 
  // and compiler can imply it but sometimes the compiler needs this explicit hint 
  lazy val fib_mem_val: Int => BigInt = Memo.mutableHashMapMemo(fib _) 

  def fib_mem_def(n: Int): BigInt = fib_mem_val(n)

}

println(Fib.fib(5))
println(Fib.fib_mem_val(5))
println(Fib.fib_mem_def(5))

Note how there is no difference in syntax of calling fib, fib_mem_val and fib_mem_def although fib_mem_val is a value. You may also try this example online

Note: beware that some ScalaZ Memo implementations are not thread-safe.

As for the lazy part, the benefit is typical for any lazy val: the actual value with the underlying storage will not be created until the first usage. If the method will be used anyway, I see no benefits in declaring it as lazy

Fibonacci memoization in Scala with Memo.mutableHashMapMemo

2 Answers2