Почему неизменяемый набор Scala не ковариантен по своему типу?

94

РЕДАКТИРОВАТЬ : переписал этот вопрос на основе исходного ответа

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
}
scala set covariance scala-collections Oxbow_lakes
источник
Стоит отметить, что foo(s.toSet[CharSequence])компилируется нормально. toSetМетод является O (1) - это просто обертывания asInstanceOf.
Джон Салливан
1
Также обратите внимание, что foo(Set("Hello", "World"))компилируется и на 2.10, так как Scala, похоже, может определить правильный тип Set. Однако он не работает с неявными преобразованиями ( stackoverflow.com/questions/23274033/… ).
LP_

Ответы:

55

Setинвариантен в своем параметре типа из-за концепции, лежащей в основе множеств как функций. Следующие подписи должны немного прояснить ситуацию:

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

Если бы Setбыли ковариантными A, applyметод не смог бы принимать параметр типа Aиз-за контравариантности функций. Setпотенциально может быть контравариантен в A, но это тоже вызывает вопросы , когда вы хотите сделать что - то вроде этого:

def elements: Iterable[A]

Короче говоря, лучшее решение - сохранить неизменность даже для неизменной структуры данных. Вы заметите, что immutable.Mapэто также инвариантно в одном из параметров типа.

Даниэль Спивак
источник
4
Я предполагаю, что этот аргумент основан на «концепции, лежащей в основе множеств как функций» - можно ли это расширить? Например, какие преимущества дает мне «набор как функция», а не «набор как коллекция»? Стоит ли терять использование этого ковариантного типа?
oxbow_lakes,
23
Сигнатура типа - довольно слабый пример. «Применить» набора - это то же самое, что он содержит метод. Увы, Scala List является ковариантом и также имеет метод contains. Подпись для List, конечно, другая, но метод работает так же, как и Set. Так что ничто не мешает Set быть со-вариантным, кроме дизайнерского решения.
Daniel C. Sobral
6
С математической точки зрения множества не являются булевыми функциями. Множества «строятся» из аксиом Цермело-Френкеля, не сокращенных какой-либо функцией включения. Причина этого - парадокс Рассела: если что-либо может быть членом множества, то рассмотрите множество R множеств, которые не являются членами самих себя. Затем задайте вопрос, является ли R членом R?
oxbow_lakes
12
Я до сих пор не убежден, что жертвование ковариацией ради Сета того стоило. Конечно, приятно, что это предикат, но обычно вы можете быть немного более подробным и использовать «set.contains», а не «set» (и, возможно, «set.contains» в любом случае лучше читается во многих случаях).
Matt R
4
@Martin: Поскольку метод List содержит значение Any, а не A. Тип List(1,2,3).contains _is (Any) => Boolean, а тип Set(1,2,3).contains _is res1: (Int) => Boolean.
Seth Tisue
52

на http://www.scala-lang.org/node/9764 Мартин Одерски пишет:

«Что касается наборов, я считаю, что отсутствие дисперсии также проистекает из реализаций. Общие наборы реализованы в виде хэш-таблиц, которые представляют собой невариантные массивы ключевого типа. Я согласен, что это немного раздражающая нерегулярность».

Итак, похоже, что все наши попытки найти принципиальную причину для этого были ошибочными :-)

Сет Тисью
источник
1
Но некоторые последовательности также реализованы с помощью массивов и все еще Seqковариантны ... Я что-то упускаю?
LP_
4
Это можно тривиально решить, сохранив Array[Any]внутреннее хранилище .
правый фолд 09
@rightfold правильно. Может быть, на то есть разумная причина, но это не так.
Пол Дрейпер,
6

РЕДАКТИРОВАТЬ : для всех, кто задается вопросом, почему этот ответ кажется немного не по теме, это потому, что я (спрашивающий) изменил вопрос.

Вывод типа Scala достаточно хорош, чтобы понять, что в некоторых ситуациях вам нужны CharSequences, а не Strings. В частности, в 2.7.3 у меня работает следующее:

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

Что касается того, как напрямую создать immutable.HashSets: не делайте этого. В качестве оптимизации реализации immutable.HashSets из менее чем 5 элементов на самом деле не являются экземплярами immutable.HashSet. Это либо EmptySet, Set1, Set2, Set3 или Set4. Эти классы являются подклассом immutable.Set, но не immutable.HashSet.

Хорхе Ортис
источник
Ты прав; пытаясь упростить мой реальный пример, я допустил тривиальную ошибку :-(
oxbow_lakes