title: Is there a generic way to memoize in Scala?
body: <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>