Concaténation de la liste Scala, ::: vs ++

362

Y a-t-il une différence entre :::et ++pour concaténer des listes dans 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

D'après la documentation, il semble être ++plus général alors qu'il :::est Listspécifique. Ce dernier est-il fourni car il est utilisé dans d'autres langages fonctionnels?

Luigi Plinge
la source
4
Est également :::un opérateur de préfixe comme toutes les méthodes commençant par:
Ben Jackson
3
Les réponses décrivent à peu près la façon dont scala a évolué autour des listes et de l'uniformité des opérateurs dans Scala (ou l'absence de ces dernières). Il est un peu malheureux que quelque chose d'aussi simple ait une si longue queue de minuties pour confondre et perdre le temps de tout apprenant Scala. Je souhaite qu'il soit stabilisé en 2.12.
matanster

Réponses:

321

Héritage. La liste a été initialement définie pour ressembler à des langages fonctionnels:

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

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

Bien sûr, Scala a fait évoluer d'autres collections, de manière ponctuelle. Lorsque 2.8 est sorti, les collections ont été redessinés pour une réutilisation du code et l' API cohérente, de sorte que vous pouvez utiliser ++pour concaténer les deux collections - et même itérateurs. List, cependant, a réussi à conserver ses opérateurs d'origine, à l'exception d'un ou deux qui se sont dépréciés.

Daniel C. Sobral
la source
19
Est-ce donc la meilleure pratique à éviter :::en faveur de ++maintenant? Utilisez également +:au lieu de ::?
Luigi Plinge
37
::est utile en raison de la correspondance de motifs (voir le deuxième exemple de Daniel). Vous ne pouvez pas faire ça avec+:
paradigmatique
1
@Luigi Si vous utilisez Listau lieu de Seq, vous pourriez aussi bien utiliser des Listméthodes idiomatiques . D'un autre côté, il sera plus difficile de passer à un autre type, si vous le souhaitez.
Daniel C.Sobral
2
Je trouve bon que l'on ait à la fois des opérations idiomatiques List (comme ::et :::) et des opérations plus générales qui sont communes à d'autres collections. Je ne laisserais tomber aucune des opérations de la langue.
Giorgio
21
@paradigmatic Scala 2.10 a :+et +:extracteurs d'objet.
0__
97

Utilisez toujours :::. Il y a deux raisons: l'efficacité et la sécurité du type.

Efficacité

x ::: y ::: zest plus rapide que x ++ y ++ z, parce que :::c'est juste associatif. x ::: y ::: zest analysé comme x ::: (y ::: z), ce qui est algorithmiquement plus rapide que (x ::: y) ::: z(ce dernier nécessite O (| x |) étapes supplémentaires).

Type de sécurité

Avec ::: vous ne pouvez concaténer que deux Lists. Avec ++vous pouvez ajouter n'importe quelle collection List, ce qui est terrible:

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

++est également facile à mélanger avec +:

scala> List(1, 2, 3) + "ab"
res1: String = List(1, 2, 3)ab
ZhekaKozlov
la source
9
Lors de la concaténation de seulement 2 listes, il n'y a pas de différence, mais dans le cas de 3 ou plus, vous avez un bon point, et je l'ai confirmé avec une référence rapide. Cependant, si vous êtes inquiet au sujet de l'efficacité, x ::: y ::: zdevrait être remplacé par List(x, y, z).flatten. pastebin.com/gkx7Hpad
Luigi Plinge
3
Veuillez expliquer pourquoi la concaténation associative gauche nécessite plus d'étapes O (x). Je pensais que tous les deux travaillaient pour O (1).
pacman le
6
Les listes @pacman sont liées individuellement, pour ajouter une liste à une autre, vous devez faire une copie de la première liste avec la deuxième attachée à la fin. La concaténation est donc O (n) par rapport au nombre d'éléments dans la première liste. La longueur de la deuxième liste n'affecte pas le temps d'exécution, il est donc préférable d'ajouter une longue liste à une courte plutôt que d'ajouter une courte liste à une longue.
puhlen
1
Les listes de @pacman Scala sont immuables . C'est pourquoi nous ne pouvons pas simplement remplacer le dernier lien lors de la concaténation. Nous devons créer une nouvelle liste à partir de zéro.
ZhekaKozlov
4
@pacman La complexité est toujours linéaire sur la longueur de xet y( zn'est jamais itérée dans tous les cas, donc n'a aucun effet sur le temps d'exécution, c'est pourquoi il est préférable d'ajouter une longue liste à une courte que l'inverse) mais la complexité asymptotique ne raconte pas toute l'histoire. x ::: (y ::: z)itère yet ajoute z, puis itère xet ajoute le résultat de y ::: z. xet ysont tous deux répétés une fois. (x ::: y) ::: zitère xet ajoute y, puis itère le résultat de x ::: yet ajoute z. yest toujours itéré une fois mais xest itéré deux fois dans ce cas.
puhlen
84

:::ne fonctionne qu'avec des listes, alors qu'il ++peut être utilisé avec n'importe quel traversable. Dans l'implémentation actuelle (2.9.0), ++retombe :::si l'argument est également a List.

paradigmatique
la source
4
Il est donc très facile d'utiliser à la fois ::: et ++ avec list. Cela peut potentiellement gâcher le code / style.
ses
24

Un autre point est que la première phrase est analysée comme suit:

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

Alors que le deuxième exemple est analysé comme suit:

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

Donc, si vous utilisez des macros, vous devez faire attention.

En outre, ++pour deux listes appelle::: mais avec plus de surcharge car cela demande une valeur implicite pour avoir un générateur de List en List. Mais les microbenchmarks n'ont rien prouvé d'utile dans ce sens, je suppose que le compilateur optimise de tels appels.

Micro-repères après échauffement.

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

Comme l'a dit Daniel C. Sobrai, vous pouvez ajouter le contenu de n'importe quelle collection à une liste en utilisant ++, alors qu'avec :::vous, vous ne pouvez concaténer que des listes.

Mikaël Mayer
la source
20
Veuillez publier vos repères non simplistes et je les voterai.
Mikaël Mayer