为什么Scala的不可变Set在类型上不是协变的？

Question

编辑: 根据原始答案重新编写了这个问题

scala.collection.immutable.Set 类在其类型参数中不是协变的。为什么会这样呢？

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
}

- oxbow_lakes

---

值得注意的是，foo(s.toSet [CharSequence]) 可以编译通过。 toSet 方法的时间复杂度为 O(1) - 它只是将 asInstanceOf 包装起来。 - john sullivan

请注意，在2.10上，foo(Set("Hello", "World"))也可以编译通过，因为Scala似乎能够推断出Set的正确类型。但是它不适用于隐式转换（http://stackoverflow.com/questions/23274033/implicit-definition-working-for-seq-but-not-for-set/）。 - Lionel Parreaux

Answer 1

Set 的类型参数是不变的，因为集合背后的概念是作为函数存在的。下面的签名应该能稍微澄清一些事情：

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

如果Set在A上是协变的，由于函数的逆变性，apply方法将无法接受A类型的参数。尽管Set可能在A上是逆变的，但当您想做像这样的事情时，它也会导致问题：

def elements: Iterable[A]

简而言之，即使对于不可变数据结构，最好的解决方案也是保持事物不变。您将注意到，immutable.Map 在其一个类型参数上也是不变的。

- Daniel Spiewak

---

我猜这个论点的关键在于“将集合视为函数的概念” - 这能否进一步扩展呢？例如，“将集合视为函数”相对于“将集合视为集合”有什么优势？放弃协变类型的使用是否值得？ - oxbow_lakes

类型签名是一个相对较弱的例子。集合的“apply”方法与其“contains”方法是相同的。然而，遗憾的是，Scala的List是协变的并且也有一个“contains”方法。当然，List的“contains”方法的签名不同，但该方法的工作方式与Set的相同。因此，没有真正阻止Set成为协变的，仅仅是一个设计决策。 - Daniel C. Sobral

从数学角度来看，集合不是布尔函数。集合是由策梅洛-弗兰克尔公理构建而成的，而不是通过某些包含函数进行“简化”。这是因为罗素悖论：如果任何东西都可以是一个集合的成员，那么考虑集合R，其中包含所有不属于自己的集合。然后问问题：R是R的成员吗？ - oxbow_lakes

我仍然不确定为了 Set 数据结构而牺牲协变性是否值得。当然，它是一个谓词，这很好，但通常你可以多写一点，使用 "set.contains" 而不是 "set"（而且在许多情况下，可以说 "set.contains" 读起来更好）。 - Matt R

@Martin: 因为List的contains方法接受Any类型参数，而不是A类型。List(1,2,3).contains _ 的类型是 (Any) => Boolean，而 Set(1,2,3).contains _ 的类型是 (Int) => Boolean。 - Seth Tisue

Answer 2

在http://www.scala-lang.org/node/9764上，Martin Odersky写道：

“关于集合的问题，我认为非变性也源于实现方式。常见的集合被实现为哈希表，它们是键类型的非变数组。我同意这是一个稍微有些烦人的不规则之处。”

因此，看来我们所有努力构建原则上的理由都是错误的 :-)

- Seth Tisue

---

但是有些序列也是用数组实现的，而且Seq仍然是协变的...我有什么遗漏吗？ - Lionel Parreaux

可以通过内部存储Array[Any]轻松解决这个问题。 - user1804599

@rightfold 是正确的。可能有合理的原因，但这不是其中之一。 - Paul Draper

Answer 3

编辑: 对于任何想知道为什么这个答案似乎有点离题的人，这是因为我（提问者）修改了问题。

Scala的类型推断足够好，可以在某些情况下确定您需要CharSequences而不是Strings。 特别是，在2.7.3中，以下内容适用于我：

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

关于如何直接创建不可变的HashSet：不要这样做。作为一种实现优化，少于5个元素的不可变的HashSet实际上并不是immutable.HashSet的实例。它们可能是EmptySet、Set1、Set2、Set3或Set4。这些类是immutable.Set的子类，但不是immutable.HashSet。

- Jorge Ortiz

---

你说得对；在试图简化我的实际例子时，我犯了一个微不足道的错误 :-( - oxbow_lakes