memo1.scala

scala> def time[A](f: => A): A = {
     |   val s = System.nanoTime
     |   val x = f
     |   val e = System.nanoTime
     |   (((e - s) / 1000).toDouble / 1000000).println
     |   x
     | }
time: [A](f: => A)A

scala> object Fib {
     |   def unapply(n: Long): Option[Long] = (n >= 2).option(n - 2)
     | }
defined module Fib

scala> lazy val fib: Long => Long = {
     |   case 0 => 0
     |   case 1 => 1
     |   case Fib(n) => fib(n) + fib(n + 1)
     | }
fib: Long => Long = <lazy>

scala> time(fib(40))
4.055657
res6: Long = 102334155

scala> time(fib(43))
16.81403
res7: Long = 433494437

memo2.scala

scala> implicit lazy val m = immutableHashMapMemo[Long, Long]
m: scalaz.Memo[Long,Long] = <lazy>

scala> val memofib = m(fib)
memofib: Long => Long = <function1>

scala> val memofib = !fib
memofib: Long => Long = <function1>

scala> time(memofib(40))
4.034974
res8: Long = 102334155

scala> time(memofib(40))
2.8E-5
res9: Long = 102334155

scala> time(memofib(43))
16.980203
res10: Long = 433494437

scala> time(memofib(43))
2.5E-5
res11: Long = 433494437

memo3.scala

scala> implicit lazy val m = mutableHashMapMemo[Long, Long]
m: scalaz.Memo[Long,Long] = <lazy>

scala> lazy val mfib: Long => Long = m {
     |   case 0 => 0
     |   case 1 => 1
     |   case Fib(n) => mfib(n) + mfib(n + 1)
     | }
mfib: Long => Long = <lazy>

scala> time(mfib(43))
0.002366
res13: Long = 433494437

scala> time(mfib(50))
1.23E-4
res14: Long = 12586269025

memo4.scala

scala> val optionMemo = memo[Int, Int] { f =>
     |   var o = none[(Int, Int)]
     |   k => {
     |     o some {
     |       case (kk, vv) => (kk === k).fold(vv, f(k))
     |     } none {
     |       val v = f(k)
     |       o = (k, v).some
     |       v
     |     }
     |   }
     | }
optionMemo: scalaz.Memo[Int,Int] = scalaz.Memos$$anon$3@1dd8a94

scala> val f = optionMemo { i =>
     |   Thread.sleep(1000)
     |   i |+| 100
     | }
f: Int => Int = <function1>

scala> time(f(10))
1.002767
res44: Int = 110

scala> time(f(10))
0.001382
res45: Int = 110

scala> time(f(11))
1.000204
res46: Int = 111