Dlaczego niezmienny zestaw Scali nie jest kowariantny w swoim typie?

94

EDYCJA : Ponownie napisano to pytanie na podstawie oryginalnej odpowiedzi

scala.collection.immutable.SetKlasa nie jest kowariantna w jego parametr typu. Dlaczego to?

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
źródło
Warto zauważyć, że foo(s.toSet[CharSequence])kompiluje się dobrze. toSetSposób O (1) - nie tylko otacza asInstanceOf.
john sullivan,
1
Zauważ również, że foo(Set("Hello", "World"))kompiluje się również w wersji 2.10, ponieważ Scala wydaje się być w stanie wywnioskować właściwy typ Set. Nie działa jednak z niejawnymi konwersjami ( stackoverflow.com/questions/23274033/… ).
LP_

Odpowiedzi:

55

Setjest niezmienna w swoim parametrze typu ze względu na koncepcję zbiorów jako funkcji. Poniższe podpisy powinny nieco wyjaśnić:

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

Gdyby Setbyły kowariantne w A, applymetoda nie mogłaby przyjąć parametru typu Aze względu na kontrawariancję funkcji. Setmoże potencjalnie być sprzeczne w programie A, ale to również powoduje problemy, gdy chcesz robić takie rzeczy:

def elements: Iterable[A]

Krótko mówiąc, najlepszym rozwiązaniem jest zachowanie niezmienności elementów, nawet w przypadku niezmiennej struktury danych. Zauważysz, że immutable.Mapjest to również niezmienne w jednym z parametrów typu.

Daniel Śpiewak
źródło
4
Wydaje mi się, że ten argument opiera się na „koncepcji zbiorów jako funkcji” - czy można to rozszerzyć? Na przykład, jakie korzyści daje mi „zestaw jako funkcja”, a nie „zestaw jako zbiór”? Czy warto zrezygnować z tego kowariantnego typu?
oxbow_lakes
23
Podpis typu jest raczej słabym przykładem. „Zastosuj” zestawu to to samo, co zawiera metodę. Niestety, Lista Scali jest równoległa i zawiera również metodę zawierającą. Podpis dla list zawiera, oczywiście, jest inny, ale metoda działa tak samo, jak metoda Set. Więc nic tak naprawdę nie powstrzymuje Seta przed byciem ko-wariantem, z wyjątkiem decyzji projektowej.
Daniel C. Sobral
6
Z matematycznego punktu widzenia zbiory nie są funkcjami logicznymi. Zbiory są „budowane” z aksjomatów Zermelo-Fraenkla, a nie redukowane przez jakąś funkcję włączającą. Powodem tego jest paradoks Russella: jeśli cokolwiek może być składnikiem zbioru, rozważ zbiór R zbiorów, które nie są członkami siebie. Następnie zadaj pytanie, czy R jest członkiem R?
oxbow_lakes
12
Nadal nie jestem przekonany, że poświęcenie kowariancji było tego warte dla Seta. Jasne, fajnie jest, że jest to predykat, ale zazwyczaj możesz być trochę bardziej rozwlekły i użyć „set.contains” zamiast „set” (i prawdopodobnie „set.contains” i tak brzmi lepiej w wielu przypadkach).
Matt R
4
@Martin: Ponieważ metoda List's zawiera metodę Any, a nie A. Typ List(1,2,3).contains _to (Any) => Boolean, a typ Set(1,2,3).contains _to res1: (Int) => Boolean.
Seth Tisue
52

na http://www.scala-lang.org/node/9764 Martin Odersky pisze:

"Jeśli chodzi o zbiory, to uważam, że niezmienność wynika również z implementacji. Wspólne zestawy są implementowane jako tablice haszujące, które są niezmiennymi tablicami typu klucza. Zgadzam się, że jest to nieco denerwująca nieprawidłowość."

Wygląda więc na to, że wszystkie nasze wysiłki zmierzające do skonstruowania pryncypialnego powodu były błędne :-)

Seth Tisue
źródło
1
Ale niektóre sekwencje są również zaimplementowane z tablicami i nadal Seqsą kowariantne ... czy czegoś mi brakuje?
LP_
4
Można to w trywialny sposób rozwiązać, przechowując je Array[Any]wewnętrznie.
prawy bok
@rightfold jest poprawne. Może istnieć rozsądny powód, ale to nie jest to.
Paul Draper
6

EDYCJA : dla każdego, kto zastanawia się, dlaczego ta odpowiedź wydaje się nieco nie na temat, to dlatego, że ja (pytający) zmodyfikowałem pytanie.

Wnioskowanie o typie Scali jest wystarczająco dobre, aby dowiedzieć się, że w niektórych sytuacjach chcesz CharSequences, a nie Strings. W szczególności działa dla mnie w 2.7.3:

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

Jeśli chodzi o bezpośrednie tworzenie niezmiennych.HashSets: nie. W ramach optymalizacji implementacji immutable.HashSets zawierające mniej niż 5 elementów nie są w rzeczywistości wystąpieniami immutable.HashSet. Są to EmptySet, Set1, Set2, Set3 lub Set4. Klasy te stanowią podklasę immutable.Set, ale nie immutable.HashSet.

Jorge Ortiz
źródło
Masz rację; próbując uprościć mój rzeczywisty przykład, popełniłem trywialny błąd :-(
oxbow_lakes