Scala list concatenation, ::: vs ++
Is there any difference between ::: and ++ for concatenating lists 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
From the documentation it looks like ++ is more general whereas ::: is List-specific. Is the latter provided because it's used in other functional languages?
::: is a prefix operator like all methods starting with :
Legacy. List was originally defined to be functional-languages-looking:
1 :: 2 :: Nil // a list
list1 ::: list2 // concatenation of two lists
list match {
case head :: tail => "non-empty"
case Nil => "empty"
}
Of course, Scala evolved other collections, in an ad-hoc manner. When 2.8 came out, the collections were redesigned for maximum code reuse and consistent API, so that you can use ++ to concatenate any two collections -- and even iterators. List, however, got to keep its original operators, aside from one or two which got deprecated.
Always use :::. There are two reasons: efficiency and type safety.
Efficiency
x ::: y ::: z is faster than x ++ y ++ z, because ::: is right associative. x ::: y ::: z is parsed as x ::: (y ::: z), which is algorithmically faster than (x ::: y) ::: z (the latter requires O(|x|) more steps).
Type safety
With ::: you can only concatenate two Lists. With ++ you can append any collection to List, which is terrible:
scala> List(1, 2, 3) ++ "ab"
res0: List[AnyVal] = List(1, 2, 3, a, b)
++ is also easy to mix up with +:
scala> List(1, 2, 3) + "ab"
res1: String = List(1, 2, 3)ab
x ::: y ::: z should be replaced with List(x, y, z).flatten. pastebin.com/gkx7Hpad
x and y (z is never iterated in any case so has no effect on the run time, this is why it's better to append a long list to a short one, than the other way around) but asymptotic complexity doesn't tell the whole story. x ::: (y ::: z) iterates y and appends z, then iterates x and appends the result of y ::: z. x and y are both iterated once. (x ::: y) ::: z iterates x and appends y, then iterates the result of x ::: y and appends z. y is still iterated once but x is iterated twice in this case.
::: works only with lists, while ++ can be used with any traversable. In the current implementation (2.9.0), ++ falls back on ::: if the argument is also a List.
A different point is that the first sentence is parsed as:
scala> List(1,2,3).++(List(4,5))
res0: List[Int] = List(1, 2, 3, 4, 5)
Whereas the second example is parsed as:
scala> List(4,5).:::(List(1,2,3))
res1: List[Int] = List(1, 2, 3, 4, 5)
So if you are using macros, you should take care.
Besides, ++ for two lists is calling ::: but with more overhead because it is asking for an implicit value to have a builder from List to List. But microbenchmarks did not prove anything useful in that sense, I guess that the compiler optimizes such calls.
Micro-Benchmarks after warming up.
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
As Daniel C. Sobrai said, you can append the content of any collection to a list using ++, whereas with ::: you can only concatenate lists.
Follow WeChat
Success story sharing
Want to stay one step ahead of the latest teleworks?
Subscribe Now相似问题
- How do I check if a list is empty?
- Finding the index of an item in a list
- What is the difference between Python's list methods append and extend?
- How can I randomly select an item from a list?
- How do I split a list into equally-sized chunks?
- How do I get the last element of a list?
- How do I make a flat list out of a list of lists?
- How do I get the number of elements in a list in Python?
- How do I clone a list so that it doesn't change unexpectedly after assignment?
:::in favour of++now? Also use+:instead of::?::is useful because of pattern matching (see Daniel second example). You cannot do that with+:::and:::) and more general operation that are common to other collections. I wouldn't drop either operation from the language.:+and+:object extractors.+:in pattern matching. There is no reason to use::, in pattern matching or elsewhere, except an aesthetic preference, should you have one.