Is there a generic way to memoize in Scala?

by

I found a better way to memoize using Scala:

def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {
  override def apply(key: I) = getOrElseUpdate(key, f(key))
}

Now you can write fibonacci as follows:

lazy val fib: Int => BigInt = memoize {
  case 0 => 0
  case 1 => 1
  case n => fib(n-1) + fib(n-2)
}

Here’s one with multiple arguments (the choose function):

lazy val c: ((Int, Int)) => BigInt = memoize {
  case (_, 0) => 1
  case (n, r) if r > n/2 => c(n, n - r)
  case (n, r) => c(n - 1, r - 1) + c(n - 1, r)
}

And here’s the subset sum problem:

// is there a subset of s which has sum = t
def isSubsetSumAchievable(s: Vector[Int], t: Int) = {
  // f is (i, j) => Boolean i.e. can the first i elements of s add up to j
  lazy val f: ((Int, Int)) => Boolean = memoize {
    case (_, 0) => true        // 0 can always be achieved using empty list
    case (0, _) => false       // we can never achieve non-zero if we have empty list
    case (i, j) => 
      val k = i - 1            // try the kth element
      f(k, j - s(k)) || f(k, j)
  }
  f(s.length, t)
}

EDIT: As discussed below, here is a thread-safe version

def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {self =>
  override def apply(key: I) = self.synchronized(getOrElseUpdate(key, f(key)))
}

More Related Contents:

  1. What type to use to store an in-memory mutable data table in Scala?
  2. What do
  3. Stratified sampling in Spark
  4. How do I convert csv file to rdd
  5. Scala’s “postfix ops”
  6. Get field names list from case class
  7. val-mutable versus var-immutable in Scala
  8. Usage of _ in scala lambda functions
  9. Function returns an empty List in Spark
  10. @karate How to pass parameter to a feature file in gatling simulation class?
  11. Scala – printing arrays
  12. Type mismatch on abstract type used in pattern matching
  13. Exploding nested Struct in Spark dataframe
  14. How do I iterate RDD’s in apache spark (scala)
  15. Unable to map on HList
  16. ScalaTest in sbt: is there a way to run a single test without tags?
  17. Differences between these three ways of defining a function in Scala
  18. How to reference external sbt project from another sbt project?
  19. How can I connect to a postgreSQL database into Apache Spark using scala?
  20. How to use IntelliJ with Play Framework and Scala
  21. How to serve uploaded files in Play!2 using Scala?
  22. Missing parameter type error by calling toSet?
  23. Spark column string replace when present in other column (row)
  24. Dynamically compiling scala class files at runtime in Scala 2.11
  25. scala f-bounded types explanation
  26. Scala variable argument list with call-by-name possible?
  27. How to vectorize DataFrame columns for ML algorithms?
  28. Scalaz Bind[Seq] typeclass
  29. Getting subclasses of a sealed trait
  30. How to instantiate an instance of type represented by type parameter in Scala

Leave a Comment