Scala Listenverkettung, ::: vs ++

Question

Gibt es einen Unterschied zwischen ::: y ++ für die Verkettung von Listen in Scala?

scala> List(1,2,3) ++ List(4,5)
res0: List[Int] = List(1, 2, 3, 4, 5)

scala> List(1,2,3) ::: List(4,5)
res1: List[Int] = List(1, 2, 3, 4, 5)

scala> res0 == res1
res2: Boolean = true

En die Dokumentation es sieht so aus ++ allgemeiner ist, während ::: es List -spezifisch. Ist letzteres vorgesehen, weil es in anderen funktionalen Sprachen verwendet wird?

Answer 1

Vermächtnis. List war ursprünglich so definiert, dass es sich um funktionale Sprachen handelt:

1 :: 2 :: Nil // a list
list1 ::: list2  // concatenation of two lists

list match {
  case head :: tail => "non-empty"
  case Nil          => "empty"
}

Natürlich hat Scala auch andere Sammlungen entwickelt, und zwar auf eine Ad-hoc-Art. Als 2.8 herauskam, wurden die Sammlungen für maximale Wiederverwendung von Code und eine konsistente API umgestaltet, so dass Sie mit ++ zu verketten jede zwei Sammlungen - und sogar Iteratoren. List, jedoch bekam, um seine ursprüngliche Operatoren zu halten, abgesehen von einem oder zwei, die veraltet wurde.

Answer 2

Verwenden Sie immer ::: . Dafür gibt es zwei Gründe: Effizienz und Typensicherheit.

Wirkungsgrad

x ::: y ::: z ist schneller als x ++ y ++ z denn ::: ist rechts assoziativ. x ::: y ::: z wird geparst als x ::: (y ::: z) die algorithmisch schneller ist als (x ::: y) ::: z (letzteres erfordert O(|x|) weitere Schritte).

Typ Sicherheit

Con ::: können Sie nur zwei Dateien miteinander verknüpfen List s. Mit ++ können Sie eine beliebige Sammlung anhängen List was schrecklich ist:

scala> List(1, 2, 3) ++ "ab"
res0: List[AnyVal] = List(1, 2, 3, a, b)

++ ist auch leicht zu verwechseln mit + :

scala> List(1, 2, 3) + "ab"
res1: String = List(1, 2, 3)ab

Answer 3

::: funktioniert nur mit Listen, während ++ kann mit jedem Traversable verwendet werden. In der aktuellen Implementierung (2.9.0), ++ fällt zurück auf ::: wenn das Argument auch ein List .

Answer 4

Ein anderer Punkt ist, dass der erste Satz wie folgt geparst wird:

scala> List(1,2,3).++(List(4,5))
res0: List[Int] = List(1, 2, 3, 4, 5)

Das zweite Beispiel hingegen wird geparst als:

scala> List(4,5).:::(List(1,2,3))
res1: List[Int] = List(1, 2, 3, 4, 5)

Wenn Sie also Makros verwenden, sollten Sie vorsichtig sein.

Außerdem, ++ für zwei Listen ist der Aufruf ::: aber mit mehr Overhead, weil es für einen impliziten Wert fragen, um einen Builder von Liste zu Liste haben. Aber Microbenchmarks haben nichts Nützliches in diesem Sinne bewiesen, ich vermute, dass der Compiler solche Aufrufe optimiert.

Micro-Benchmarks nach dem Aufwärmen.

scala>def time(a: => Unit): Long = { val t = System.currentTimeMillis; a; System.currentTimeMillis - t}
scala>def average(a: () => Long) = (for(i<-1 to 100) yield a()).sum/100

scala>average (() => time { (List[Int]() /: (1 to 1000)) { case (l, e) => l ++ List(e) } })
res1: Long = 46
scala>average (() => time { (List[Int]() /: (1 to 1000)) { case (l, e) => l ::: List(e ) } })
res2: Long = 46

Wie Daniel C. Sobrai sagte, können Sie den Inhalt einer beliebigen Sammlung an eine Liste anhängen, indem Sie ++ während bei ::: können Sie nur Listen miteinander verknüpfen.