Test if added on immutable sets

Question
1

I can write a class Store using mutable sets:

  class Store[A] {
    private val elems = mutable.Set.empty[A]
    def +=(elem: A): Boolean = elems.add(elem)
  }

or immutable sets:

  class Store[A] {
    private var elems = Set.empty[A]
    def +=(elem: A): Boolean = {
      val s = elems + elem
      (s ne elems) && {
        elems = s
        true
      }
    }
  }

My questions are:

  • Is the second implementation valid, i.e., is there a guarantee that (S + x) eq S if S contains x?
  • Is there a better/simpler way (without the cost of doing a search first)?
2

I find this simpler:

	def +=(elem: A): Boolean = {
		!elems.contains(elem) && {elems += elem; true}
	}

Even if contains() does a “search”, but the + on a HashSet effectively does the same.

3

That’s why I don’t want to do it twice.

4

So, the docs say:

a new set that contains all elements of this set and that also contains elem.

If this was correct, then it would never return the same set, even if the element was already included.

But, the default Set actually does return itself:


Welcome to Scala 2.13.1 (OpenJDK 64-Bit Server VM, Java 11.0.6).
Type in expressions for evaluation. Or try :help.

> val set = Set(1,2,3)
set: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

> val set2 = set + 3
set2: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

> set eq set2
res0: Boolean = true

There is no guarantee.

I could imagine the Set is effectively some kind of lazily evaluated view and trying to add another element would trigger the evaluation.

5

You could simply compare the size of the sets before and afterwards:

val s = elems
elems += elem
elems.size > s.size
3 Likes
6

That is not the documentation I see:

Creates a new set with an additional element, unless the element is already present.

This unless makes me think that no new set is created if the element is already present (which is what the current implementations seem to be doing).

1 Like
7

It’s under “returns”.