memoized fibonacci

fibonacci.scala

class Memoize1[-T, +R](f: T => R) extends (T => R) {
  private[this] val memorized = scala.collection.mutable.Map.empty[T, R]
  def apply(x: T):R = {
    memorized.getOrElseUpdate(x, f(x))
  }
}

object Memoize1 {
  def apply[T, R](f: T => R) = new Memoize1(f)
  def Y[T,R](f: (T => R) => T => R) = {
    lazy val yf: T => R = Memoize1(f(yf)(_))
    yf
  }
}

def fib(n:Long):Long = n match {
  case 0 | 1 => 1
  case _ => fib(n-2) + fib(n-1)
}

def fibCurry(f:Long => Long)(n:Long):Long = n match {
  case 0 | 1 => 1
  case _ => f(n-2) + f(n-1)
}
lazy val fibMem = Memoize1.Y(fibCurry)

val fibBeginTime = System.nanoTime()
List.range[Long](2,40).map(fib)
println(System.nanoTime() - fibBeginTime)

val fibMemBeginTime = System.nanoTime()
List.range[Long](2,40).map(fibMem)
println(System.nanoTime() - fibMemBeginTime)