Scala list concatenation, ::: vs ++

Question

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?

Also `:::` is a prefix operator like all methods starting with `:` — Ben Jackson, Jul 02 '11 at 22:53
The answers pretty much delineate the way that scala was evolved around lists and operator uniformity in Scala (or the lack of the latter). It is a bit unfortunate that something so simple has such a long tail of minutiae to confuse and waste the time of any Scala learner. I wish it would be leveled off in 2.12. — matanster, Jan 05 '15 at 01:24

score 350 · Accepted Answer · edited Aug 25 '14 at 21:22

350

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.

edited Aug 25 '14 at 21:22

Zoltán

21,321
14
93
134

answered Jul 02 '11 at 23:15

Daniel C. Sobral

295,120
86
501
681

21

So is it best practice to avoid `:::` in favour of `++` now? Also use `+:` instead of `::`? – Luigi Plinge Jul 02 '11 at 23:30
41

`::` is useful because of pattern matching (see Daniel second example). You cannot do that with `+:` – paradigmatic Jul 02 '11 at 23:40
@paradigmatic Yet, at any rate. It is trivial to implement `+:` and `:+` as object extractors. – Daniel C. Sobral Jul 03 '11 at 00:01
1

@Luigi If you are using `List` instead of `Seq`, you might as well use idiomatic `List` methods. On the other hand, it will make it harder to _change_ to another type, if you ever desire to do so. – Daniel C. Sobral Jul 03 '11 at 00:02
2

I find it good that one has both List idiomatic operations (like `::` and `:::`) and more general operation that are common to other collections. I wouldn't drop either operation from the language. – Giorgio Oct 29 '12 at 11:00
22

@paradigmatic Scala 2.10 has `:+` and `+:` object extractors. – 0__ Jan 18 '13 at 09:25
@ses Why would `++` be deprecated? – Daniel C. Sobral Oct 28 '13 at 17:48
@DanielC.Sobral because they (:::, ++) both do the same work (result) for lists. Or why not use only ::: for all sequences instead of ++? Just do not like idea using same-result methods, like having red hammer and green one to put a nail. – ses Oct 28 '13 at 18:55
1

@ses You cannot both respect a convention for operators on list and use the same operator for non-lists. The point of `::` and `:::` _is_ that they are `List`-only, like the other languages that have them. If you did not come through such languages, it will be meaningless to you, which doesn't mean it is meaningless. – Daniel C. Sobral Oct 29 '13 at 00:51
@paradigmatic So you can use `::` in pattern matching. But does that have any relevance to the method `::`? For consistency they are defined similarly, but they could add support for `+:` and `:+` in pattern matching right?? Is that what 0__'s point is? – samthebest Dec 23 '13 at 18:17
2

@samthebest You can use `+:` in pattern matching. There is no reason to use `::`, in pattern matching or elsewhere, except an aesthetic preference, should you have one. – lutzh Nov 01 '15 at 14:39

score 124 · Answer 2 · answered Aug 21 '15 at 08:13

124

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

answered Aug 21 '15 at 08:13

ZhekaKozlov

36,558
20
126
155

14

When concatenating just 2 lists, there's no difference, but in the case of 3 or more, you have a good point, and I confirmed it with a quick benchmark. However, if you're worried about efficiency, `x ::: y ::: z` should be replaced with `List(x, y, z).flatten`. http://pastebin.com/gkx7Hpad – Luigi Plinge Aug 21 '15 at 19:43
it doesn't add a lot of type safety... `List(1) ::: List("2")` becomes `List[Any] = List(1, 2)`. If type safety is a concern(as it should be), I would recommend to avoid both `++` and `:::` in favor of scalaz's `|+|` or similar. If efficiency is the main concern, then by all means use `:::` – caente Jul 14 '16 at 23:02
3

Please explain, why left associative concatenation requires more O(x) steps. I thought that both of them work for O(1). – pacman Jan 02 '17 at 17:30
9

@pacman Lists are singly linked, to append one list to another you need to make a copy of the first list that has the second one attached at the end. Concatenation is therefore O(n) with respect to the number of elements in the first list. The length of the second list does not effect the runtime so it is better to append a long list to a short one rather than appending a short list to a long one. – puhlen Feb 02 '17 at 19:32
1

@pacman Scala's lists are *immutable*. That's why we can not just replace the last link when doing concatenation. We must create a new list from scratch. – ZhekaKozlov Feb 13 '17 at 05:10
@ ZhekaKozlov I understand that scala collections are immutable, but both of concatenation operators - `:::` and `++` use the same concept with `ListBuffer` under the hood and both of them must have the same time complexity - `O(n)` where n = x + y + z, if I'm wrong, please, correct me. – pacman Feb 14 '17 at 09:26
@puhlen But both of concatenation - `x ::: (y ::: z)` and `(x ::: y) ::: z` force to iteration along all lists - `x, y, z` but in different order. `x ::: (y ::: z)` needs to iterate y and z and in the end x, while `(x ::: y) ::: z` - x and y and finally z. And algorithmically in both case it will `O(n) n = x+y+z` – pacman Feb 14 '17 at 09:37
9

@pacman The complexity is always linear wrt the length of `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. – puhlen Feb 14 '17 at 14:11

score 88 · Answer 3 · answered Jul 02 '11 at 23:18

88

::: 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.

answered Jul 02 '11 at 23:18

paradigmatic

40,153
18
88
147

4

So it is very easy to use both ::: and ++ working with list. That potentially can put a mess to code / style. – ses Oct 28 '13 at 18:44

score 27 · Answer 4 · edited Feb 02 '17 at 19:26

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.

Please do post your not overly simplistic microbenchmarks and i'll vote them up. — Mikaël Mayer, May 12 '15 at 14:52

Scala list concatenation, ::: vs ++

4 Answers4

Linked

Related