Databases
StackOverflow2013
Postsdbo
POIs there a generic way to memoize in Scala?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIs there a generic way to memoize in Scala?
    text
    copied!<p>I wanted to memoize this:</p> <pre><code>def fib(n: Int) = if(n &lt;= 1) 1 else fib(n-1) + fib(n-2) println(fib(100)) // times out </code></pre> <p>So I wrote this and this surprisingly compiles and works (I am surprised because <code>fib</code> references itself in its declaration):</p> <pre><code>case class Memo[A,B](f: A =&gt; B) extends (A =&gt; B) { private val cache = mutable.Map.empty[A, B] def apply(x: A) = cache getOrElseUpdate (x, f(x)) } val fib: Memo[Int, BigInt] = Memo { case 0 =&gt; 0 case 1 =&gt; 1 case n =&gt; fib(n-1) + fib(n-2) } println(fib(100)) // prints 100th fibonacci number instantly </code></pre> <p>But when I try to declare fib inside of a <code>def</code>, I get a compiler error:</p> <pre><code>def foo(n: Int) = { val fib: Memo[Int, BigInt] = Memo { case 0 =&gt; 0 case 1 =&gt; 1 case n =&gt; fib(n-1) + fib(n-2) } fib(n) } </code></pre> <p>Above fails to compile <code>error: forward reference extends over definition of value fib case n =&gt; fib(n-1) + fib(n-2)</code></p> <p>Why does declaring the <code>val fib</code> inside a def fails but outside in the class/object scope works?</p> <p>To clarify, why I might want to declare the recursive memoized function in the def scope - here is my solution to the subset sum problem:</p> <pre><code>/** * Subset sum algorithm - can we achieve sum t using elements from s? * * @param s set of integers * @param t target * @return true iff there exists a subset of s that sums to t */ def subsetSum(s: Seq[Int], t: Int): Boolean = { val max = s.scanLeft(0)((sum, i) =&gt; (sum + i) max sum) //max(i) = largest sum achievable from first i elements val min = s.scanLeft(0)((sum, i) =&gt; (sum + i) min sum) //min(i) = smallest sum achievable from first i elements val dp: Memo[(Int, Int), Boolean] = Memo { // dp(i,x) = can we achieve x using the first i elements? case (_, 0) =&gt; true // 0 can always be achieved using empty set case (0, _) =&gt; false // if empty set, non-zero cannot be achieved case (i, x) if min(i) &lt;= x &amp;&amp; x &lt;= max(i) =&gt; dp(i-1, x - s(i-1)) || dp(i-1, x) // try with/without s(i-1) case _ =&gt; false // outside range otherwise } dp(s.length, t) } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload