Simple memoization using the State monad

gistfile1.scala

def memoized[A, B](f: A => B): A => State[Map[A, B], B] =
  a => State { m =>
    m get a match {
      case Some(b) => (b, m)
      case None =>
        val b = f(a)
        (b, m.updated(a, b))
    }
  }

def f: Int => Int = i => {
  println("computing f("+i+")")
  i * 1337
}


scala> List(1, 2, 3, 1, 2, 3) map f
computing f(1)
computing f(2)
computing f(3)
computing f(1)
computing f(2)
computing f(3)
res1: List[Int] = List(1337, 2674, 4011, 1337, 2674, 4011)

scala> List(1, 2, 3, 1, 2, 3) traverseS memoized(f) eval Map.empty
computing f(1)
computing f(2)
computing f(3)
res2: scalaz.package.Id[List[Int]] = List(1337, 2674, 4011, 1337, 2674, 4011)

Does this (breaking the getOrElse into a match) just save the expense of always updating m?

Yes, that was the reason for the change. It's a shame there is no getOrElseUpdate method for an immutable.Map.