scala type woes: SoftReference, ReferenceQueues, SoftHashMap

Question

EDIT Most answers thus far are focusing on the fact that I was incorrectly extending Map. I have corrected this in the example code, but the type woes persist, and the question still stands.

I'm trying to implement a SoftHashMap in Scala, but am running into a type mismatch error:

inferred type arguments [K,V] do not conform to class SoftValue's type parameter bounds [K,+V <: AnyRef]
val sv = new SoftValue(kv._1, kv._2, queue)

I understand that I'm over-constraining the types, but I am not sure how to fix it.

import scala.collection.mutable.{Map, HashMap}    
import scala.ref._

class SoftValue[K, +V <: AnyRef](val key:K, value:V, queue:ReferenceQueue[V]) extends SoftReference(value, queue)

class SoftMap[K, V] extends Map[K, V]
{
  private val map = new HashMap[K, SoftValue[K, V]]

  private val queue = new ReferenceQueue[V]

  override def +=(kv: (K, V)):this.type =
  {
    val sv = new SoftValue(kv._1, kv._2, queue)
    map(kv._1) = sv
    this
  }
}

First things first. Are you extending scala.collection.mutable.Map? In any case, '+' in Map returns a new instance of Map ("Creates a new map containing a new key/value mapping and all the key/value mappings of this map"). — Sam Stainsby, Feb 26 '11 at 06:17

huynhjl · Accepted Answer · 2011-02-26T16:22:30.383

This compiles. (edit: I initially added val value but that created a strong reference). Not sure how you want to handle iterator...

import scala.collection.mutable.{Map, HashMap}    
import scala.ref._

class SoftValue[K, +V <: AnyRef](val key:K, value:V, 
  queue:ReferenceQueue[V]) extends SoftReference(value, queue)

class SoftMap[K, V <: AnyRef] extends Map[K, V] {
  private val map = new HashMap[K, SoftValue[K, V]]
  private val queue = new ReferenceQueue[V]

  def +=(kv: (K, V)): this.type = {
    val sv = new SoftValue(kv._1, kv._2, queue)
    map(kv._1) = sv
    this
  }

  def -=(k: K): this.type = { map -= k; this }
  def get(k: K) = map.get(k).flatMap(_.get)
  def iterator: Iterator[(K,V)] = error("todo")
}

You're missing V <: AnyRef when defining SoftMap, so that V can be used as argument of the SoftValue constructor.

To see a full implementation check out: http://stackoverflow.com/questions/5112219/is-there-a-softhashmap-in-scala — dsg, Feb 26 '11 at 18:08

score 1 · Answer 2 · answered Feb 26 '11 at 08:33

First problem, as pointed out by Sam, is that you are extending scala.collection.immutable.Map, which you are accessing through the alias scala.Map.

Second, you have declared V as a covariant type parameter. This would mean that a SoftMap[String, Dog] is a subtype of SoftMap[String, Any]. It is not valid to refer to the covariant type parameter in a contravariant position in the class definition.

trait Contra[+A] {
    def a: A    // method return type is a covariant position, okay
    def m(a: A) // method parameter is a contravariant position, error
    def n[AA >: A](a: AA) // upper bound of a type param is in covariant position, okay
}

Typesafe mutable collections need to refer to the element type in both co- and contravariant positions: to retrieve elements and to add elements respectively. For this reason, they must declare the type parameter as invariant.

The definition of collection.mutable.Map shows this:

trait Map[A, B] 
  extends Iterable[(A, B)]
     with scala.collection.Map[A, B] 
     with MapLike[A, B, Map[A, B]]

If you extend this, you will be told:

scala> trait SoftMap[K, +V] extends collection.mutable.Map[K, V]
<console>:25: error: covariant type V occurs in invariant position in type [K,+V]java.lang.Object with scala.collection.mutable.Map[K,V] of trait SoftMap
       trait SoftMap[K, +V] extends collection.mutable.Map[K, V]
             ^

On the other hand:

scala> trait SoftMap[K, V] extends collection.mutable.Map[K, V]
defined trait SoftMap

The final issue, also pointed out by Sam, is that the method + doesn't do what you intend, at least since Scala 2.8. You should implement the method +=.

axel22 · Answer 3 · 2011-02-26T15:08:29.977

If SoftMap is going to be mutable, then you cannot update it with a supertype V1 of it's value type V. If that were possible, the old map would have a binding to a key-value pair with a value of type V1, and the type of the old map is V. This would result in type errors when looking up the new binding in the old map.

Mutable maps implement + by copying the map, immutable maps have a more efficient +. On the other hand, mutable maps have += which modifies the existing map and is more efficient. The argument of += is a key and a value, where a value isn't the supertype of the map value type.

In this case, the solution is to copy the map.

EDIT:

The error message you've got after changing the question above is due to the fact that the type parameter V of the soft map can be any type whatsoever, while the type V of the SoftValue has to be a subtype of AnyRef (cannot be an Int or a Float, that is, a subtype of AnyVal). Therefore, you cannot create a SoftValue with the type V from the SoftMap, because someone might instantiate the SoftMap by setting the V to, say Int.

scala type woes: SoftReference, ReferenceQueues, SoftHashMap

3 Answers3