concaténation de listes en Scala, :: : vs ++

Question

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

Desde la documentation on dirait que ++ est plus général alors que ::: es List -spécifique. Ce dernier est-il fourni parce qu'il est utilisé dans d'autres langages fonctionnels ?

Answer 1

L'héritage. La liste a été définie à l'origine pour être de type fonctionnel-langage :

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 ad-hoc. Lors de la sortie de la version 2.8, les collections ont été repensées pour une réutilisation maximale du code et une API cohérente, de sorte que vous pouvez utiliser ++ pour concaténer tout deux collections -- et même des itérateurs. List, cependant, a pu conserver ses opérateurs originaux, à part un ou deux qui ont été dépréciés.

Answer 2

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

Efficacité

x ::: y ::: z est plus rapide que x ++ y ++ z parce que ::: est associatif à droite. x ::: y ::: z est interprété comme x ::: (y ::: z) qui est algorithmiquement plus rapide que (x ::: y) ::: z (cette dernière nécessite O(|x|) étapes supplémentaires).

Sécurité de type

Avec ::: vous ne pouvez concaténer que deux List s. 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

Answer 3

::: ne fonctionne qu'avec des listes, tandis que ++ peut être utilisé avec n'importe quel traversable. Dans l'implémentation actuelle (2.9.0), ++ se rabat sur ::: si l'argument est également un List .

Answer 4

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 interprété comme :

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.

D'ailleurs, ++ pour deux listes est d'appeler ::: mais avec plus de frais généraux car il demande une valeur implicite pour avoir un constructeur de liste à liste. Mais les microbenchmarks n'ont rien prouvé d'utile dans ce sens, je suppose que le compilateur optimise ces appels.

Micro-benchmarks après le ré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 à l'aide de la fonction ++ alors qu'avec ::: vous pouvez seulement concaténer des listes.