View difference between Paste ID: f8fnthSg and buVze5gF

 
-/**
+// Not a super great example, but here is `fib` using state-threading. You can
- * Not a super great example, but here is `fib` using state-threading. You can
+// use this same technique for `pascal` or any function you'd like to memoize.
- * use this same technique for `pascal` or any function you'd like to memoize.
+// If you continue with FP you will learn how to do this with the State monad,
- * If you continue with FP you will learn how to do this with the State monad,
+// (which removes most of the clutter) and the Free monad (which allows you to
- * (which removes most of the clutter) and the Free monad (which allows you to
+// use general recursion without consuming stack).
- * use general recursion without consuming stack).
+
- */
+
   // Calculate the nth Fibonacci number using a recursive algorithm. Note that
   // this will run out of stack space for large values of `n` (around 6000 for
-  /**
+  // me, but it will depend on VM settings.
-   * Calculate the nth Fibonacci number using a recursive algorithm. Note that
+
-   * this will run out of stack space for large values of `n` (around 6000 for
+
-   * me, but it will depend on VM settings.
+
-   */
+
 
     // The actual implementation threads our state, so it consumes an initial
     // memo and returns the answer along with a [possibly new] memo.
     def fib0(n: Int, m: Memo): (Memo, BigInt) =
       if (n < 3) (m, BigInt(1)) // Our base case
       else m.get(n) match {
         case Some(a) => (m, a)  // Answer is already known
         case None =>            // Need to calculate
           val (mx, a) = {
             val (m0, a0) = fib0(n - 2, m)  // Note the data flow from here
             val (m1, a1) = fib0(n - 1, m0) // ... to here
             (m1, a0 + a1)                  // ... to here
           }
           (mx + (n -> a), a)    // A new memo, and our answer
       }
 
     // Delegate to `fib0` with an initial empty memo, and then throw the memo
     // away when we get our answer back. We could also return the memo as part
     // of the public API so it could be used again later; here we rebuild it
     // each time someone calls the top-level `fib`.
     require(n > 0, "fib(n) is defined only for positive n")
     fib0(n, Map())._2
 
   }
 
   // Calculate a rather large number, then print it out in chunks.
   val big = fib(2500)
   println(big.toString.grouped(80).mkString("\n"))
 
 }