Why is Scala's immutable Set not covariant in its type?

Question

EDIT: Re-written this question based on original answer

The scala.collection.immutable.Set class is not covariant in its type parameter. Why is this?

import scala.collection.immutable._

def foo(s: Set[CharSequence]): Unit = {
    println(s)
}

def bar(): Unit = {
   val s: Set[String] = Set("Hello", "World");
   foo(s); //DOES NOT COMPILE, regardless of whether type is declared 
           //explicitly in the val s declaration
}

It's worth noting that `foo(s.toSet[CharSequence])` compiles fine. The `toSet` method is O(1) - it just wraps `asInstanceOf`. — john sullivan, Sep 22 '13 at 19:46
Note also that `foo(Set("Hello", "World"))` compiles too on 2.10, since Scala seems to be able to infer the right type of Set. It doesn't work with implicit conversions though (http://stackoverflow.com/questions/23274033/implicit-definition-working-for-seq-but-not-for-set/). — Lionel Parreaux, Apr 25 '14 at 16:06

score 57 · Accepted Answer · answered Mar 24 '09 at 18:34

57

Set is invariant in its type parameter because of the concept behind sets as functions. The following signatures should clarify things slightly:

trait Set[A] extends (A=>Boolean) {
  def apply(e: A): Boolean
}

If Set were covariant in A, the apply method would be unable to take a parameter of type A due to the contravariance of functions. Set could potentially be contravariant in A, but this too causes issues when you want to do things like this:

def elements: Iterable[A]

In short, the best solution is to keep things invariant, even for the immutable data structure. You'll notice that immutable.Map is also invariant in one of its type parameters.

answered Mar 24 '09 at 18:34

Daniel Spiewak

54,515
14
108
120

4

I guess this argument hinges around "the concept behind sets as functions" - could this be expanded upon? For example, what advantages does "a set as a function" give me that a "set as a collection" not? Is it worth losing the use of that covariant type? – oxbow_lakes Mar 24 '09 at 22:00
In light of your answer, would you (in general) *not* use Set as the type returned by an API? I would commonly have a service implementation keep an internal Set in Java, with the service API itself wrap this in a Collections.unmodifiable on an access method. – oxbow_lakes Mar 24 '09 at 22:05
I think I will ask a related question – oxbow_lakes Mar 24 '09 at 22:05
1

Sets are really boolean functions by definition; it's a math thing that has nothing to do with Scala. In fact, iterable sets (set as a collection) are an extension to the idea rather than part of the core. – Daniel Spiewak Mar 25 '09 at 00:28
23

The type signature is a rather weak example. A set's "apply" is the same thing as it's contains method. Alas, Scala's List is co-variant and has a contains method as well. The signature for List's contains is different, of course, but the method works just like Set's. So there is nothing really stopping Set from being co-variant, except a design decision. – Daniel C. Sobral Jul 24 '09 at 02:44
Why not have Set extend (AnyRef=>Boolean) instead of (A=>Boolean)? – Craig P. Motlin Jul 28 '09 at 22:36
6

Sets are not boolean functions from a mathematical perspective. Sets are "built up" from the Zermelo-Fraenkel axioms not *reduced* by some inclusion function. The reason behind this is Russell's paradox: if anything can be a member of a set, then consider the Set R of sets which are not members of themselves. Then ask the question, is R a member of R? – oxbow_lakes Jan 11 '10 at 22:39
If Sets extended Any=>Boolean instead of A=>Boolean, then couldn't they be covariant? apply() should take Any anyway. – Craig P. Motlin Dec 18 '10 at 06:51
13

I'm still unconvinced that sacrificing covariance was worth it for Set. Sure, it's nice that it's a predicate, but you can usually just be a little more verbose and use "set.contains" rather than "set" (and arguably "set.contains" reads better in many cases anyway). – Matt R Mar 03 '11 at 20:32
2

Going to `contains` doesn't solve the problem. The parameter type for that method will need to vary contravariantly, no differently from if `Set` were to extend `A => Boolean`. In fact, the cases are trivially isomorphic, so it makes sense that just eliminating `apply` is insufficient. – Daniel Spiewak Mar 04 '11 at 21:51
2

Why can a List be covariant then when it also has an apply method?. – Martin Konicek May 12 '11 at 17:58
4

@Martin: Because List's contains method takes Any, not A. The type of `List(1,2,3).contains _` is `(Any) => Boolean`, while the type of `Set(1,2,3).contains _` is `res1: (Int) => Boolean`. – Seth Tisue Jun 27 '11 at 01:31
1

@SethTisue and Daniel - Shouldn't Set.apply and Set.contains also take Any, not A? – Craig P. Motlin Jul 17 '12 at 17:11
@CraigP.Motlin Not while Set remains invariant. If Set were made covariant, the situation would be different. – Seth Tisue Jul 18 '12 at 18:28
1

@SethTisue Right, I'm just saying the two go together. Everyone is pointing out that Set isn't covariant because of the types on apply() and contains(), but those ought to change at the same time. – Craig P. Motlin Jul 19 '12 at 17:21

score 55 · Answer 2 · answered May 31 '11 at 04:49

55

at http://www.scala-lang.org/node/9764 Martin Odersky writes:

"On the issue of sets, I believe the non-variance stems also from the implementations. Common sets are implemented as hashtables, which are non-variant arrays of the key type. I agree it's a slightly annoying irregularity."

So, it seems that all of our efforts to construct a principled reason for this were misguided :-)

answered May 31 '11 at 04:49

Seth Tisue

29,985
11
82
149

1

But some sequences are also implemented with arrays, and still `Seq` is covariant... am I missing something? – Lionel Parreaux Apr 25 '14 at 16:09
4

This could trivially be solved by storing `Array[Any]` internally. – Mar 09 '15 at 16:26
@rightfold is correct. There might be a reasonable reason, but this isn't it. – Paul Draper May 26 '15 at 19:15

score 6 · Answer 3 · edited Mar 24 '09 at 16:05

EDIT: for anyone wondering why this answer seems slightly off-topic, this is because I (the questioner) have modified the question.

Scala's type inference is good enough to figure out that you want CharSequences and not Strings in some situations. In particular, the following works for me in 2.7.3:

import scala.collections.immutable._
def findCharSequences(): Set[CharSequence] = Set("Hello", "World")

As to how to create immutable.HashSets directly: don't. As an implementation optimization, immutable.HashSets of less than 5 elements are not actually instances of immutable.HashSet. They are either EmptySet, Set1, Set2, Set3, or Set4. These classes subclass immutable.Set, but not immutable.HashSet.

You are right; in trying to simplify my actual example I made a trivial mistake :-( — oxbow_lakes, Mar 24 '09 at 11:44

Why is Scala's immutable Set not covariant in its type?

3 Answers3

Linked

Related