Filling mutable map with defaults OR alternative to mutable map for Scala function memoization

2
votes

I know that withDefault allows you to specify a function that will be applied to a key to produce a default map value, but that function gets called every time you pass an unknown key into the map, even if you pass in the same key -- the values aren't stored in the map.

scala> case class Foo(foo: String) {}
defined class Foo

scala> val m = mutable.OpenHashMap[String, Foo]().withDefault( s => {
       | println(s"creating new value for $s")
       | Foo(s)
       | })
m: scala.collection.mutable.Map[String,Foo] = Map()

scala> m("elvis")
creating value for elvis
res1: Foo = Foo(elvis)

scala> m("elvis")
creating value for elvis
res2: Foo = Foo(elvis)

Now obviously this isn't a big deal for case classes, but if the values are themselves mutable collections, or any other mutable object, it's not very helpful. I'm reduced to using getOrElseUpdate wherever I access the map. Surely there's a more elegant solution?

Or, since in this case the 'default' function is actually the only way I'm going to be generating map values, is there an elegant, Scala-like solution for caching function return values that doesn't involve mutable maps?

ETA: To be clear, I do want to call the function again for each different key. But for a given key, I want to only call the function once, and get the same object back the next time.

2
scaladictionarydefault-value
See mutable.Map.getOrElseUpdate. Also see Map.computeIfAbsent. - Boris the Spider
I know about getOrElseUpdate but (as I mentioned in the question) I don't want to have to use it anywhere I access the map. Is computeIfAbsent available in Scala? - David Moles
They're basically the same thing. I actually can't remember that the status of Java 8 support is in Scala... - Boris the Spider
Couldn't you inherit from mutable.Map and override the get method to call getOrElseUpdate with a defined function? - Boris the Spider
Ah, I didn't look closely enough at the computeIfAbsent docs. And no, getOrElseUpdate() calls get() (see source), so overriding get() wouldn't work. But I could override get() to just do more or less what getOrElseUpdate() does. I suppose that's my fallback if there's nothing more elegant. - David Moles

2 Answers

4
votes

Scalas mutable.Map is actually designed to be subclassed, so that default can be overridden. The default default just throw a NoSuchElementException and the existing withDefault(Value) methods just override default. You can do the same while caching the value.

scala> import scala.collection.mutable
import scala.collection.mutable

scala> case class Foo(foo: String)
defined class Foo

scala> val m = new mutable.OpenHashMap[String, Foo] {
     |   override def default(key: String): Foo = {
     |     println(s"creating new value for $key")
     |     val foo = Foo(key)
     |     put(key, foo)
     |     foo
     |   }
     | }
m: scala.collection.mutable.OpenHashMap[String,Foo] = OpenHashMap()

scala> m("elvis")
creating new value for elvis
res0: Foo = Foo(elvis)

scala> m("elvis")
res1: Foo = Foo(elvis)

scala> m("not elvis")
creating new value for not elvis
res2: Foo = Foo(not elvis)
0
votes

Try this solution. It needs to improve. But the main idea consist of:

  case class Foo(foo: String) {}

  implicit class MapExt[K, V](m: mutable.Map[K, V]) {
    def withCachedDefault(f: K => V): mutable.Map[K, V] = {
      new mutable.Map[K, V] { // create wrapper around 'm'
        override def apply(k: K): V = this.get(k) match {
          case None =>
            val v: V = f(k) 
            m.put(k, v)       // caching new non-existing value
            v
          case Some(v) => v
        }
        override def get(key: K): Option[V] = m.get(key)
        override def iterator: Iterator[(K, V)] = m.iterator
        override def +=(kv: (K, V)): this.type = ??? /* TODO wrap m.+= */
        override def -=(key: K): this.type = ??? /* TODO wrap m.-= */
      }
    }
  }

  val m = mutable.OpenHashMap[String, Foo]().withCachedDefault(s => {
    println(s"creating new value for $s")
    Foo(s)
  })

 println(m("elvis"))
 println(m("elvis"))
 println(m("word"))
 println(m("word"))

 // output:
 //> creating new value for elvis
 //> Foo(elvis)
 //> Foo(elvis)
 //> creating new value for word
 //> Foo(word)
 //> Foo(word)

This solution has several problems, which need to be improved. For example, unpredictability for mutable state:

val m = mutable.OpenHashMap[String, Foo]().withCachedDefault(fun1)

val m2 = m.withCachedDefault(fun2)
m2("elvis")     
m2("new value")

and etc..