What type to use to store an in-memory mutable data table in Scala?

by

You could use a mutable.Map[TupleN[A1, A2, ..., AN], R] , or if memory is a concern, a WeakHashMap[1]. The definitions below (built on the memoization code from michid’s blog) allow you to easily memoize functions with multiple arguments. For example:

import Memoize._

def reallySlowFn(i: Int, s: String): Int = {
   Thread.sleep(3000)
   i + s.length
}

val memoizedSlowFn = memoize(reallySlowFn _)
memoizedSlowFn(1, "abc") // returns 4 after about 3 seconds
memoizedSlowFn(1, "abc") // returns 4 almost instantly

Definitions:

/**
 * A memoized unary function.
 *
 * @param f A unary function to memoize
 * @param [T] the argument type
 * @param [R] the return type
 */
class Memoize1[-T, +R](f: T => R) extends (T => R) {
   import scala.collection.mutable
   // map that stores (argument, result) pairs
   private[this] val vals = mutable.Map.empty[T, R]

   // Given an argument x, 
   //   If vals contains x return vals(x).
   //   Otherwise, update vals so that vals(x) == f(x) and return f(x).
   def apply(x: T): R = vals getOrElseUpdate (x, f(x))
}

object Memoize {
   /**
    * Memoize a unary (single-argument) function.
    *
    * @param f the unary function to memoize
    */
   def memoize[T, R](f: T => R): (T => R) = new Memoize1(f)

   /**
    * Memoize a binary (two-argument) function.
    * 
    * @param f the binary function to memoize
    * 
    * This works by turning a function that takes two arguments of type
    * T1 and T2 into a function that takes a single argument of type 
    * (T1, T2), memoizing that "tupled" function, then "untupling" the
    * memoized function.
    */
   def memoize[T1, T2, R](f: (T1, T2) => R): ((T1, T2) => R) = 
      Function.untupled(memoize(f.tupled))

   /**
    * Memoize a ternary (three-argument) function.
    *
    * @param f the ternary function to memoize
    */
   def memoize[T1, T2, T3, R](f: (T1, T2, T3) => R): ((T1, T2, T3) => R) =
      Function.untupled(memoize(f.tupled))

   // ... more memoize methods for higher-arity functions ...

   /**
    * Fixed-point combinator (for memoizing recursive functions).
    */
   def Y[T, R](f: (T => R) => T => R): (T => R) = {
      lazy val yf: (T => R) = memoize(f(yf)(_))
      yf
   }
}

The fixed-point combinator (Memoize.Y) makes it possible to memoize recursive functions:

val fib: BigInt => BigInt = {                         
   def fibRec(f: BigInt => BigInt)(n: BigInt): BigInt = {
      if (n == 0) 1 
      else if (n == 1) 1 
      else (f(n-1) + f(n-2))                           
   }                                                     
   Memoize.Y(fibRec)
}

[1] WeakHashMap does not work well as a cache. See http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html and this related question.

More Related Contents:

  1. Scala 2.8 breakOut
  2. Is the Scala 2.8 collections library a case of “the longest suicide note in history”? [closed]
  3. Why is Scala’s immutable Set not covariant in its type?
  4. What is the difference between JavaConverters and JavaConversions in Scala?
  5. When should I choose Vector in Scala?
  6. What does param: _* mean in Scala?
  7. Scala 2.8 collections design tutorial
  8. withFilter instead of filter
  9. Scala Map implementation keeping entries in insertion order?
  10. Stream vs Views vs Iterators
  11. How to read files from resources folder in Scala?
  12. Function returns an empty List in Spark
  13. Is there a generic way to memoize in Scala?
  14. Scala: Why does Seq.contains take an Any argument, instead of an argument of the sequence type?
  15. Reduce, fold or scan (Left/Right)?
  16. Scala Sets contain the same elements, but sameElements() returns false
  17. Difference between MutableList and ListBuffer
  18. Scala: Parallel collection in object initializer causes a program to hang
  19. Scala best way of turning a Collection into a Map-by-key?
  20. scala parallel collections degree of parallelism
  21. Scala: Write a function to swap a number in place without using temporary variables
  22. What is a “context bound” in Scala?
  23. Understanding implicit in Scala
  24. Do scala constructor parameters default to private val?
  25. Composing Option with List in for-comprehension gives type mismatch depending on order
  26. NullPointerException in Scala Spark, appears to be caused be collection type?
  27. Is there a way to use “type” word as a variable name in Scala?
  28. How does the “scala.sys.process” from Scala 2.9 work?
  29. How do you define a local var/val in the primary constructor in Scala?
  30. Scala 2.10 reflection, how do I extract the field values from a case class, i.e. field list from case class

Leave a Comment