State-Threading Example

/**
 * 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.
 * 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
 * use general recursion without consuming stack).
 */
object Fib extends App {

  /**
   * 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.
   */
  def fib(n: Int): BigInt = {

    // A type alias is just a nickname. Our memo is an immutable map.
    type Memo = Map[Int, BigInt]

    // 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"))

}