Verkettung der Scala-Liste, ::: vs ++

362

Gibt es einen Unterschied zwischen :::und ++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

Aus der Dokumentation geht hervor, dass ++es allgemeiner ist, während :::es Listspezifisch ist. Wird letzteres bereitgestellt, weil es in anderen funktionalen Sprachen verwendet wird?

Luigi Plinge
quelle
4
Auch :::ist ein Präfix-Operator wie alle Methoden beginnend mit:
Ben Jackson
3
Die Antworten beschreiben ziemlich genau die Art und Weise, wie sich Scala um Listen und die Einheitlichkeit der Operatoren in Scala (oder das Fehlen der letzteren) entwickelt hat. Es ist ein bisschen bedauerlich, dass etwas so Einfaches einen so langen Schwanz von Kleinigkeiten hat, dass es die Zeit eines jeden Scala-Lernenden verwirrt und verschwendet. Ich wünschte, es würde in 2.12 abgeflacht.
Matanster

Antworten:

321

Erbe. Die Liste wurde ursprünglich so definiert, dass sie nach funktionalen Sprachen aussieht:

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 andere Sammlungen ad-hoc weiterentwickelt. Als 2.8 herauskam, wurden die Sammlungen für maximale Code-Wiederverwendung und konsistente API neu gestaltet, sodass Sie zwei beliebige Sammlungen - und sogar Iteratoren - ++verketten können . List musste jedoch seine ursprünglichen Operatoren behalten, abgesehen von einem oder zwei, die veraltet waren.

Daniel C. Sobral
quelle
19
So ist es am beste Praxis zu vermeiden , :::für ++jetzt? Auch +:anstelle von verwenden ::?
Luigi Plinge
37
::ist wegen des Mustervergleichs nützlich (siehe Daniel, zweites Beispiel). Sie können das nicht mit+:
paradigmatischen
1
@Luigi Wenn Sie Listanstelle von verwenden Seq, können Sie auch idiomatische ListMethoden verwenden. Auf der anderen Seite wird es schwieriger, zu einem anderen Typ zu wechseln , wenn Sie dies jemals wünschen.
Daniel C. Sobral
2
Ich finde es gut, dass man sowohl List-idiomatische Operationen (wie ::und :::) als auch allgemeinere Operationen hat, die anderen Sammlungen gemeinsam sind. Ich würde keine Operation aus der Sprache streichen.
Giorgio
21
@paradigmatic Scala 2.10 hat :+und Objektextraktoren +:.
0__
97

Immer benutzen :::. Es gibt zwei Gründe: Effizienz und Typensicherheit.

Effizienz

x ::: y ::: zist schneller als x ++ y ++ z, weil :::richtig assoziativ ist. x ::: y ::: zwird analysiert als x ::: (y ::: z), was algorithmisch schneller ist als (x ::: y) ::: z(letzteres erfordert O (| x |) mehr Schritte).

Typensicherheit

Mit können :::Sie nur zwei Lists verketten . Mit können ++Sie jede 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
ZhekaKozlov
quelle
9
Wenn Sie nur 2 Listen verketten, gibt es keinen Unterschied, aber bei 3 oder mehr haben Sie einen guten Punkt, und ich habe ihn mit einem schnellen Benchmark bestätigt. Wenn Sie sich jedoch Sorgen um die Effizienz machen, x ::: y ::: zsollten Sie diese durch ersetzen List(x, y, z).flatten. pastebin.com/gkx7Hpad
Luigi Plinge
3
Bitte erläutern Sie, warum die linke assoziative Verkettung mehr O (x) -Schritte erfordert. Ich dachte, dass beide für O (1) arbeiten.
Pacman
6
@pacman-Listen sind einzeln verknüpft. Um eine Liste an eine andere anzuhängen, müssen Sie eine Kopie der ersten Liste erstellen, an deren Ende die zweite angehängt ist. Die Verkettung ist daher O (n) in Bezug auf die Anzahl der Elemente in der ersten Liste. Die Länge der zweiten Liste wirkt sich nicht auf die Laufzeit aus. Daher ist es besser, eine lange Liste an eine kurze Liste anzuhängen, als eine kurze Liste an eine lange Liste anzuhängen.
Puhlen
1
Die Listen von @pacman Scala sind unveränderlich . Deshalb können wir bei der Verkettung nicht nur den letzten Link ersetzen. Wir müssen eine neue Liste von Grund auf neu erstellen.
ZhekaKozlov
4
@pacman Die Komplexität ist immer linear über die Länge von xund y( zwird auf keinen Fall iteriert, hat also keinen Einfluss auf die Laufzeit, deshalb ist es besser, eine lange Liste an eine kurze anzuhängen, als umgekehrt), aber asymptotische Komplexität erzählt nicht die ganze Geschichte. x ::: (y ::: z)iteriert yund hängt an z, dann iteriert xund hängt das Ergebnis von an y ::: z. xund ywerden beide einmal iteriert. (x ::: y) ::: ziteriert xund hängt an y, dann iteriert das Ergebnis von x ::: yund hängt an z. ywird immer noch einmal iteriert, xwird aber in diesem Fall zweimal iteriert.
Puhlen
84

:::funktioniert nur mit Listen, ++kann aber mit jedem Traversable verwendet werden. In der aktuellen Implementierung (2.9.0) wird ++zurückgegriffen, :::wenn das Argument auch a ist List.

paradigmatisch
quelle
4
Es ist also sehr einfach, sowohl ::: als auch ++ mit list zu arbeiten. Das kann möglicherweise den Code / Stil durcheinander bringen.
Ses
24

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

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

Während das zweite Beispiel wie folgt analysiert wird:

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 wird ++für zwei Listen aufgerufen, :::jedoch mit mehr Overhead, da nach einem impliziten Wert gefragt wird, um einen Builder von Liste zu Liste zu haben. Aber Mikrobenchmarks haben sich in diesem Sinne nicht als nützlich erwiesen. Ich denke, der Compiler optimiert solche Aufrufe.

Mikro-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 jeder Sammlung mit an eine Liste anhängen ++, während :::Sie damit nur Listen verketten können.

Mikaël Mayer
quelle
20
Bitte poste deine nicht allzu simplen Mikrobenchmarks und ich werde sie abstimmen.
Mikaël Mayer