Mengapa Set yang tidak dapat diubah Scala tidak kovarian dalam tipenya?

94

EDIT : Tulis ulang pertanyaan ini berdasarkan jawaban asli

The scala.collection.immutable.Setkelas tidak kovarian dalam parameter jenisnya. Kenapa ini?

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
sumber
Perlu dicatat bahwa foo(s.toSet[CharSequence])kompilasi baik-baik saja. The toSetmetode adalah O (1) - itu hanya membungkus asInstanceOf.
john sullivan
1
Perhatikan juga bahwa foo(Set("Hello", "World"))mengkompilasi juga pada 2.10, karena Scala tampaknya dapat menyimpulkan jenis Set yang tepat. Ini tidak bekerja dengan konversi implisit sekalipun ( stackoverflow.com/questions/23274033/… ).
LP_

Jawaban:

55

Setadalah invarian dalam parameter tipenya karena konsep di balik himpunan sebagai fungsi. Tanda tangan berikut harus sedikit menjelaskan hal-hal:

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

Jika Setkovarian masuk A, applymetode tidak akan dapat mengambil parameter tipe Akarena pertentangan fungsi. Setberpotensi menjadi contravariant di A, tapi ini terlalu menyebabkan masalah ketika Anda ingin melakukan hal-hal seperti ini:

def elements: Iterable[A]

Singkatnya, solusi terbaik adalah menjaga hal-hal tetap tidak berubah, bahkan untuk struktur data yang tidak dapat diubah. Anda akan melihat bahwa immutable.Mapitu juga tidak berubah di salah satu parameter tipenya.

Daniel Spiewak
sumber
4
Saya kira argumen ini bergantung pada "konsep di balik set sebagai fungsi" - bisakah ini diperluas? Misalnya, keuntungan apa yang diberikan "set sebagai fungsi" kepada saya, sedangkan "set sebagai koleksi" tidak? Apakah layak kehilangan penggunaan jenis kovarian itu?
oxbow_lakes
23
Jenis tanda tangan adalah contoh yang agak lemah. Satu set "terapkan" sama dengan metode berisi. Sayangnya, Scala's List adalah co-variant dan memiliki metode berisi juga. Tanda tangan untuk List's contains tentu saja berbeda, tetapi metodenya bekerja seperti Set. Jadi tidak ada yang benar-benar menghentikan Set untuk menjadi co-varian, kecuali keputusan desain.
Daniel C. Sobral
6
Himpunan bukanlah fungsi boolean dari perspektif matematika. Set "dibangun" dari aksioma Zermelo-Fraenkel yang tidak direduksi oleh beberapa fungsi inklusi. Alasan di balik ini adalah paradoks Russell: jika sesuatu dapat menjadi anggota suatu himpunan, maka pertimbangkan Himpunan R yang bukan anggota himpunan itu sendiri. Kemudian ajukan pertanyaan, apakah R adalah anggota R?
oxbow_lakes
12
Saya masih tidak yakin bahwa mengorbankan kovarian sepadan untuk Set. Tentu, itu bagus karena itu predikat, tetapi Anda biasanya bisa sedikit lebih bertele-tele dan menggunakan "set.contains" daripada "set" (dan bisa dibilang "set.contains" dibaca lebih baik dalam banyak kasus).
Matt R
4
@Martin: Karena metode List berisi mengambil Any, bukan A. Jenisnya List(1,2,3).contains _adalah (Any) => Boolean, sedangkan jenisnya Set(1,2,3).contains _adalah res1: (Int) => Boolean.
Seth Tisue
52

di http://www.scala-lang.org/node/9764 Martin Odersky menulis:

"Mengenai masalah set, saya percaya non-varians juga berasal dari implementasi. Set umum diimplementasikan sebagai hashtable, yang merupakan array non-varian dari jenis kunci. Saya setuju ini adalah ketidakteraturan yang sedikit mengganggu."

Jadi, tampaknya semua upaya kami untuk membangun alasan yang berprinsip untuk ini salah arah :-)

Seth Tisue
sumber
1
Tetapi beberapa urutan juga diimplementasikan dengan array, dan masih Seqkovarian ... apakah saya melewatkan sesuatu?
LP_
4
Hal ini dapat diselesaikan dengan mudah dengan menyimpan secara Array[Any]internal.
kanan
@rightfold benar. Mungkin ada alasan yang masuk akal, tetapi bukan ini.
Paul Draper
6

EDIT : bagi siapa pun yang bertanya-tanya mengapa jawaban ini tampak sedikit di luar topik, ini karena saya (penanya) telah mengubah pertanyaannya.

Jenis inferensi Scala cukup baik untuk mengetahui bahwa Anda menginginkan CharSequences dan bukan Strings dalam beberapa situasi. Secara khusus, berikut ini berfungsi untuk saya di 2.7.3:

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

Mengenai cara membuat immutable.HashSets secara langsung: jangan. Sebagai pengoptimalan implementasi, immutable.HashSet yang kurang dari 5 elemen sebenarnya bukan instance dari immutable.HashSet. Mereka adalah EmptySet, Set1, Set2, Set3, atau Set4. Kelas-kelas ini merupakan subkelas immutable.Set, tetapi tidak immutable.HashSet.

Jorge Ortiz
sumber
Kamu benar; dalam mencoba menyederhanakan contoh aktual saya, saya membuat kesalahan sepele :-(
oxbow_lakes