Warum ist Scalas unveränderliches Set in seiner Art nicht kovariant?

94

BEARBEITEN : Diese Frage wurde basierend auf der ursprünglichen Antwort neu geschrieben

Die scala.collection.immutable.SetKlasse ist in ihrem Typparameter nicht kovariant. Warum ist das?

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
quelle
Es ist erwähnenswert, dass gut foo(s.toSet[CharSequence])kompiliert. Die toSetMethode ist O (1) - sie wird nur umbrochen asInstanceOf.
John Sullivan
1
Beachten Sie auch, dass foo(Set("Hello", "World"))auch auf 2.10 kompiliert wird, da Scala in der Lage zu sein scheint, den richtigen Set-Typ abzuleiten. Es funktioniert jedoch nicht mit impliziten Konvertierungen ( stackoverflow.com/questions/23274033/… ).
LP_

Antworten:

55

Setist in seinem Typparameter aufgrund des Konzepts hinter Mengen als Funktionen unveränderlich. Die folgenden Unterschriften sollten die Dinge etwas klarer machen:

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

Wenn dies Setkovariant wäre A, könnte die applyMethode Aaufgrund der Kontravarianz der Funktionen keinen Parameter vom Typ annehmen. Setkönnte möglicherweise kontra in A, aber auch dies verursacht Probleme , wenn Sie solche Dinge zu tun:

def elements: Iterable[A]

Kurz gesagt, die beste Lösung besteht darin, die Dinge auch für die unveränderliche Datenstruktur unveränderlich zu halten. Sie werden feststellen, dass dies immutable.Mapauch in einem seiner Typparameter unveränderlich ist.

Daniel Spiewak
quelle
4
Ich denke, dieses Argument dreht sich um "das Konzept hinter Mengen als Funktionen" - könnte dies erweitert werden? Welche Vorteile bietet mir beispielsweise "eine Menge als Funktion", die eine "Menge als Sammlung" nicht bietet? Lohnt es sich, die Verwendung dieses kovarianten Typs zu verlieren?
oxbow_lakes
23
Die Typensignatur ist ein eher schwaches Beispiel. Das "Anwenden" eines Sets ist dasselbe, wie es die Methode enthält. Leider ist Scalas Liste eine Co-Variante und hat auch eine enthält-Methode. Die Signatur für List's enthält natürlich etwas anderes, aber die Methode funktioniert genauso wie die von Set. Es gibt also nichts, was Set wirklich davon abhält, eine Co-Variante zu sein, außer einer Designentscheidung.
Daniel C. Sobral
6
Mengen sind aus mathematischer Sicht keine booleschen Funktionen. Mengen werden aus den Zermelo-Fraenkel-Axiomen "aufgebaut", die durch eine Einschlussfunktion nicht reduziert werden. Der Grund dafür ist Russells Paradoxon: Wenn etwas Mitglied einer Menge sein kann, dann betrachte die Menge R von Mengen, die keine Mitglieder von sich selbst sind. Stellen Sie dann die Frage, ob R ein Mitglied von R ist.
oxbow_lakes
12
Ich bin immer noch nicht davon überzeugt, dass es sich für Set gelohnt hat, Kovarianz zu opfern. Sicher, es ist schön, dass es ein Prädikat ist, aber Sie können normalerweise etwas ausführlicher sein und "set.contains" anstelle von "set" verwenden (und wohl "set.contains" liest sich in vielen Fällen sowieso besser).
Matt R
4
@Martin: Da die Methode List enthält, ist Any, nicht A. Der Typ List(1,2,3).contains _is ist (Any) => Boolean, während der Typ Set(1,2,3).contains _is ist res1: (Int) => Boolean.
Seth Tisue
52

unter http://www.scala-lang.org/node/9764 schreibt Martin Odersky:

"In Bezug auf Mengen glaube ich, dass die Nichtvarianz auch von den Implementierungen herrührt. Gemeinsame Mengen werden als Hashtabellen implementiert, bei denen es sich um nichtvariante Arrays des Schlüsseltyps handelt. Ich stimme zu, dass dies eine etwas ärgerliche Unregelmäßigkeit ist."

Es scheint also, dass alle unsere Bemühungen, einen prinzipiellen Grund dafür zu konstruieren, fehlgeleitet waren :-)

Seth Tisue
quelle
1
Einige Sequenzen sind aber auch mit Arrays implementiert und immer noch Seqkovariant ... fehlt mir etwas?
LP_
4
Dies könnte trivial durch Array[Any]internes Speichern gelöst werden .
Rechtsfalte
@rightfold ist korrekt. Es mag einen vernünftigen Grund geben, aber das ist es nicht.
Paul Draper
6

BEARBEITEN : Für alle, die sich fragen, warum diese Antwort etwas vom Thema abweicht, liegt dies daran, dass ich (der Fragesteller) die Frage geändert habe.

Die Typinferenz von Scala ist gut genug, um herauszufinden, dass Sie in bestimmten Situationen CharSequences und nicht Strings möchten. Insbesondere funktioniert in 2.7.3 Folgendes für mich:

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

Wie man unveränderliche.HashSets direkt erstellt: nicht. Als Implementierungsoptimierung sind unveränderliche HashSets mit weniger als 5 Elementen keine Instanzen von unveränderlichem HashSet. Sie sind entweder EmptySet, Set1, Set2, Set3 oder Set4. Diese Klassen sind unveränderlich. Set, aber nicht unveränderlich. HashSet.

Jorge Ortiz
quelle
Du hast recht; Beim Versuch, mein aktuelles Beispiel zu vereinfachen, habe ich einen trivialen Fehler gemacht :-(
oxbow_lakes