StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You could use a <code>mutable.Map[TupleN[A1, A2, ..., AN], R]</code> <strike>, or if memory is a concern, a WeakHashMap</strike>[1]. The definitions below (built on the memoization code from <a href="http://michid.wordpress.com/2009/02/23/function_mem/" rel="nofollow noreferrer">michid's blog</a>) allow you to easily memoize functions with multiple arguments. For example:</p> <pre><code>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 </code></pre> <p>Definitions:</p> <pre><code>/** * 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 } } </code></pre> <p>The fixed-point combinator (<code>Memoize.Y</code>) makes it possible to memoize recursive functions:</p> <pre><code>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) } </code></pre> <p>[1] WeakHashMap does not work well as a cache. See <a href="http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html" rel="nofollow noreferrer">http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html</a> and <a href="https://stackoverflow.com/questions/3651313/how-to-cache-results-in-scala">this related question</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload