class memoize private (val f: Int => Int) {
  import scala.collection.mutable
  val cache = new mutable.HashMap[Int, Int]()
  def memoized_f(x : Int) : Int =
    cache.getOrElseUpdate(x, f(x))
}
object memoize {
  def apply(f: Int => Int) : Int => Int = new memoize(f).memoized_f
}

val fib : Int=>Int = memoize((n:Int) => {
  if (n <= 1) n else fib(n-1) + fib(n-2)
})