Example 2 code from blog post "Memoisation with State"

FibMemo2.scala

case class State[S, A](run: S => (A, S))

//Fix FibMemo2 in
// http://blog.tmorris.net/posts/memoisation-with-state-using-scala/index.html
// Again the results were not being memoised. (Added debug option to see what
// gets calculated
object FibMemo2 {
   type Memo = Map[BigInt, BigInt]

   def fibmemo2(n: BigInt, debug: Boolean=false): BigInt = {
     def fibmemoR(z: BigInt): State[Memo, BigInt] =
       State(memo =>
         if(z <= 1)
           (z, memo)
         else memo get z match {
           case None => {
             val (r, memo0) = fibmemoR(z - 1) run memo
             val (s, memo1) = fibmemoR(z - 2) run memo0
             val res = r+s
             if (debug) println(z+"->"+res)
             (res, memo1 + Pair(z,res)) // <- add results to memory
           }
           case Some(v) => (v, memo)
         })

     fibmemoR(n).run(Map())._1
   }
}