Fibonacci with Scalaz's State monad (uses Scala 2.10 and Scalaz 7.0.0.M8)

Fib.scala

import scalaz._
import Scalaz._

object Fib {

  type Memo = Map[Int, Int]
  def stFib(n: Int): State[Memo, Int] = n match {
    case 0 => State.state(0)
    case 1 => State.state(1)
    case n =>
      for {
        memoed <- State.gets { m: Memo => m get n }
        res <- memoed.cata(State.state[Memo, Int], for {
            a <- stFib(n - 2)
            b <- stFib(n - 1)
            fibN = { println(s"Calculated fib($n)"); a + b }
            _ <- State.modify { memo: Memo => memo + (n -> fibN) }
          } yield fibN)
      } yield res
  }

  def fib(n: Int): Int = stFib(n).eval(Map.empty)
}

// scala> Fib.fib(10)
// Calculated fib(2)
// Calculated fib(3)
// Calculated fib(4)
// Calculated fib(5)
// Calculated fib(6)
// Calculated fib(7)
// Calculated fib(8)
// Calculated fib(9)
// Calculated fib(10)
// res0: Int = 55