Concatenación de lista Scala, ::: vs ++

362

¿Hay alguna diferencia entre :::y ++para concatenar listas en 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

De la documentación parece que ++es más general, mientras que :::es Listespecífico. ¿Se proporciona este último porque se usa en otros lenguajes funcionales?

Luigi Plinge
fuente
44
También :::es un operador de prefijo como todos los métodos que comienzan con:
Ben Jackson
3
Las respuestas delinean la forma en que Scala se desarrolló alrededor de las listas y la uniformidad del operador en Scala (o la falta de este último). Es un poco desafortunado que algo tan simple tenga una cola tan larga de minucias para confundir y perder el tiempo de cualquier alumno de Scala. Desearía que se nivelara en 2.12.
matanster

Respuestas:

321

Legado. La lista se definió originalmente para tener un aspecto funcional de idiomas:

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

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

Por supuesto, Scala desarrolló otras colecciones, de manera ad-hoc. Cuando salieron 2,8, las colecciones han sido rediseñados para una máxima reutilización de código y API consistente, por lo que se puede utilizar ++para concatenar los dos colecciones - e incluso los iteradores. List, sin embargo, debe mantener sus operadores originales, aparte de uno o dos que quedaron en desuso.

Daniel C. Sobral
fuente
19
Entonces, ¿es mejor evitar :::a favor de ++ahora? También usar en +:lugar de ::?
Luigi Plinge
37
::es útil debido a la coincidencia de patrones (ver el segundo ejemplo de Daniel). No se puede hacer eso con+:
paradigmático
1
@Luigi Si está utilizando en Listlugar de Seq, también podría utilizar Listmétodos idiomáticos . Por otro lado, hará que sea más difícil cambiar a otro tipo, si alguna vez desea hacerlo.
Daniel C. Sobral
2
Me parece bien que uno tenga tanto operaciones idiomáticas de Lista (como ::y :::) como operaciones más generales que son comunes a otras colecciones. No descartaría ninguna operación del lenguaje.
Giorgio
21
@paradigmatic Scala 2.10 tiene :+y +:extractores de objetos.
0__
97

Siempre uso :::. Hay dos razones: eficiencia y seguridad de tipo.

Eficiencia

x ::: y ::: zes más rápido que x ++ y ++ z, porque :::es correcto asociativo. x ::: y ::: zse analiza como x ::: (y ::: z), que es algorítmicamente más rápido que (x ::: y) ::: z(este último requiere O (| x |) más pasos).

Tipo de seguridad

Con :::usted solo puede concatenar dos Lists. Con ++usted puede agregar cualquier colección List, lo cual es terrible:

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

++También es fácil de mezclar con +:

scala> List(1, 2, 3) + "ab"
res1: String = List(1, 2, 3)ab
ZhekaKozlov
fuente
99
Al concatenar solo 2 listas, no hay diferencia, pero en el caso de 3 o más, tiene un buen punto, y lo confirmó con un punto de referencia rápido. Sin embargo, si le preocupa la eficiencia, x ::: y ::: zdebe reemplazarlo por List(x, y, z).flatten. pastebin.com/gkx7Hpad
Luigi Plinge
3
Explique por qué la concatenación asociativa izquierda requiere más pasos O (x). Pensé que ambos trabajan para O (1).
pacman
66
@pacman Las listas están vinculadas individualmente, para agregar una lista a otra, debe hacer una copia de la primera lista que tiene la segunda adjunta al final. Por lo tanto, la concatenación es O (n) con respecto al número de elementos en la primera lista. La longitud de la segunda lista no afecta el tiempo de ejecución, por lo que es mejor agregar una lista larga a una corta en lugar de agregar una lista corta a una larga.
puhlen
1
Las listas de @pacman Scala son inmutables . Es por eso que no podemos simplemente reemplazar el último enlace cuando hacemos concatenación. Debemos crear una nueva lista desde cero.
ZhekaKozlov
44
@pacman La complejidad siempre es lineal con la longitud de xy y( znunca se repite en ningún caso, por lo que no tiene ningún efecto en el tiempo de ejecución, es por eso que es mejor agregar una lista larga a una corta que al revés) pero La complejidad asintótica no cuenta toda la historia. x ::: (y ::: z)itera yy agrega z, luego itera xy agrega el resultado de y ::: z. xy yambos se repiten una vez. (x ::: y) ::: zitera xy agrega y, luego itera el resultado de x ::: yy agrega z. ytodavía se repite una vez, pero xse repite dos veces en este caso.
puhlen
84

:::funciona solo con listas, mientras que ++se puede usar con cualquier tragable. En la implementación actual (2.9.0), ++cae de nuevo sobre :::si el argumento es también una List.

paradigmático
fuente
44
Por lo tanto, es muy fácil usar tanto ::: como ++ trabajando con list. Potencialmente puede poner un desastre al código / estilo.
ses
24

Un punto diferente es que la primera oración se analiza como:

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

Mientras que el segundo ejemplo se analiza como:

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

Entonces, si está utilizando macros, debe tener cuidado.

Además, ++para dos listas se llama :::pero con más sobrecarga porque se pide un valor implícito para tener un generador de Lista a Lista. Pero los microbenchmarks no probaron nada útil en ese sentido, supongo que el compilador optimiza tales llamadas.

Micro-puntos de referencia después del calentamiento.

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

Como dijo Daniel C. Sobrai, puede agregar el contenido de cualquier colección a una lista usando ++, mientras que con :::solo puede concatenar listas.

Mikaël Mayer
fuente
20
Publique sus microbenchmarks no demasiado simplistas y los votaré.
Mikaël Mayer