¿Por qué el conjunto inmutable de Scala no es covariante en su tipo?

94

EDITAR : reescribió esta pregunta según la respuesta original

La scala.collection.immutable.Setclase no es covariante en su parámetro de tipo. ¿Por qué es esto?

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
fuente
Vale la pena señalar que se foo(s.toSet[CharSequence])compila bien. El toSetmétodo es O (1), simplemente envuelve asInstanceOf.
john sullivan
1
Tenga en cuenta también que también se foo(Set("Hello", "World"))compila en 2.10, ya que Scala parece ser capaz de inferir el tipo correcto de Set. Sin embargo, no funciona con conversiones implícitas ( stackoverflow.com/questions/23274033/… ).
LP_

Respuestas:

55

Setes invariante en su parámetro de tipo debido al concepto detrás de los conjuntos como funciones. Las siguientes firmas deberían aclarar un poco las cosas:

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

Si Setfuera covariante A, el applymétodo no podría tomar un parámetro de tipo Adebido a la contravarianza de funciones. Setpotencialmente podría ser contravariant en A, pero esto también provoca problemas cuando se quiere hacer cosas como esta:

def elements: Iterable[A]

En resumen, la mejor solución es mantener las cosas invariables, incluso para la estructura de datos inmutable. Observará que immutable.Maptambién es invariante en uno de sus parámetros de tipo.

Daniel Spiewak
fuente
4
Supongo que este argumento gira en torno al "concepto detrás de los conjuntos como funciones". ¿Podría ampliarse esto? Por ejemplo, ¿qué ventajas me da "un conjunto como función" que "un conjunto como una colección" no? ¿Vale la pena perder el uso de ese tipo covariante?
oxbow_lakes
23
La firma de tipo es un ejemplo bastante débil. El "aplicar" de un conjunto es lo mismo que el método contiene. Por desgracia, Scala's List es covariante y también tiene un método contiene. La firma de List's contiene es diferente, por supuesto, pero el método funciona igual que el de Set. Así que no hay nada que realmente impida que Set sea covariante, excepto una decisión de diseño.
Daniel C. Sobral
6
Los conjuntos no son funciones booleanas desde una perspectiva matemática. Los conjuntos se "construyen" a partir de los axiomas de Zermelo-Fraenkel no reducidos por alguna función de inclusión. La razón detrás de esto es la paradoja de Russell: si algo puede ser miembro de un conjunto, entonces considere el Conjunto R de conjuntos que no son miembros de sí mismos. Luego haga la pregunta, ¿es R miembro de R?
oxbow_lakes
12
Todavía no estoy convencido de que sacrificar la covarianza valiera la pena para Set. Claro, es bueno que sea un predicado, pero normalmente puedes ser un poco más detallado y usar "set.contains" en lugar de "set" (y posiblemente "set.contains" se lee mejor en muchos casos de todos modos).
Matt R
4
@Martin: porque el método contiene de List toma Any, no A. El tipo de List(1,2,3).contains _es (Any) => Boolean, mientras que el tipo de Set(1,2,3).contains _es res1: (Int) => Boolean.
Seth Tisue
52

en http://www.scala-lang.org/node/9764 Martin Odersky escribe:

"Sobre el tema de los conjuntos, creo que la no varianza se deriva también de las implementaciones. Los conjuntos comunes se implementan como tablas hash, que son matrices no variantes del tipo clave. Estoy de acuerdo en que es una irregularidad un poco molesta".

Entonces, parece que todos nuestros esfuerzos para construir una razón de principios para esto fueron equivocados :-)

Seth Tisue
fuente
1
Pero algunas secuencias también se implementan con matrices, y aún Seqes covariante ... ¿me falta algo?
LP_
4
Esto podría resolverse trivialmente almacenando Array[Any]internamente.
margen derecho
@rightfold es correcto. Puede haber una razón razonable, pero no es esta.
Paul Draper
6

EDITAR : para cualquiera que se pregunte por qué esta respuesta parece un poco fuera de tema, esto se debe a que yo (el interrogador) he modificado la pregunta.

La inferencia de tipos de Scala es lo suficientemente buena como para darse cuenta de que desea CharSequences y no Strings en algunas situaciones. En particular, lo siguiente me funciona en 2.7.3:

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

En cuanto a cómo crear inmutables.HashSets directamente: no lo hagas. Como optimización de implementación, inmutable.HashSets de menos de 5 elementos no son realmente instancias de inmutable.HashSet. Son EmptySet, Set1, Set2, Set3 o Set4. Estas clases son una subclase de inmutable.Set, pero no inmutable.HashSet.

Jorge Ortiz
fuente
Tienes razón; al tratar de simplificar mi ejemplo real, cometí un error trivial :-(
oxbow_lakes