1. Introduction
Over time, Scala collections have evolved to maximize code reuse, with the goal of a consistent and common API to work on all of them. Therefore, they share some operators that help programmers abstract over the actual implementation.
List, however, has also kept its original operators and methods. Therefore, we can implement some operations in different ways. One such operation is concatenation.
In this tutorial, we’ll focus on List concatenation by looking at the differences and similarities between the ::: and ++ operators.
2. List Concatenation
In this section, we’re going to look at the two operators that are used to concatenate List objects, ::: and ++. We’ll see each of the operators in action, and then we’ll compare the two.
2.1. The ::: Operator
The ::: operator is List-specific. Let’s see how the class List[A] defines it:
def :::[B >: A](prefix: List[B]): List[B]
The operator takes a List[B] as a parameter, where B must be a supertype of A. Then, the static type of the elements in the returned List will be B as well.
::: is basically the right-associative version of the :: operator. As such, writing List(1, 2) ::: List(3, 4) is equivalent to List(3, 4).:::(List(1, 2)). Hence, ::: is equivalent to the prepend method.
This operator creates a new List object where the last element of the first list points to the head of the second:
val list1 = 1 :: 2 :: 3 :: Nil
val list2 = 4 :: 5 :: Nil
assert(list1 ::: list2 == 1 :: 2 :: 3 :: 4 :: 5 :: Nil)
Here, list1 and list2 are, respectively, 1 :: 2 :: 3 :: Nil and 4 :: 5 :: Nil. After applying :::, the result becomes 1 :: 2 :: 3 :: 4 :: 5 :: Nil. Notice how list1‘s Nil gets replaced with a pointer to the head of list2.
Additionally, we can use ::: to concatenate more than two lists in a row too:
val list1 = 1 :: 2 :: 3 :: Nil
val list2 = 4 :: 5 :: Nil
val list3 = 6 :: 7 :: Nil
assert(list1 ::: list2 ::: list3 == 1 :: 2 :: 3 :: 4 :: 5 :: 6 :: 7 :: Nil)
2.2. The ++ Operator
The definition of the ++ operator is more complex than that of the ::: operator. Let’s see how List[A] defines the ++ operator:
override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That
The ++ operator poses many additional constraints on type B. Along with it being a supertype of A, ++ requires that its parameter be an instance of GenTraversableOnce. This means That could be a List, a Set, a Map, or even a String. As a matter of fact, GenTraversableOnce is the parent trait for all traversable-once objects.
Additionally, ++ requires an implicit value of type CanBuildFrom[List[A], B, That] to be available in the scope. This means that the compiler should be able to find a way to build a collection of type That, whose actual value is still to be inferred, from a List[A] (the list ++ is being called on) and B (the type of the elements in the collection to concatenate).
Scala will infer the actual That type based on the most suitable implicit value it finds in the scope. If no such value can be found (meaning that Scala doesn’t know how to build the resulting collection), the compilation will fail.
Let’s see how to use it in practice:
val list1 = 1 :: 2 :: 3 :: Nil
val list2 = 4 :: 5 :: Nil
assert(list1 ++ list2 == 1 :: 2 :: 3 :: 4 :: 5 :: Nil)
The result is the same as before. Additionally, we can concatenate multiple lists in a row as well:
val list1 = 1 :: 2 :: 3 :: Nil
val list2 = 4 :: 5 :: Nil
val list3 = 6 :: 7 :: Nil
assert(list1 ++ list2 ++ list3 == 1 :: 2 :: 3 :: 4 :: 5 :: 6 :: 7 :: Nil)
2.3. Differences Between ::: and ++
As we saw above, using either ::: or ++ produces the same result. However, there are two main differences between the two operators.
The first difference is about performance. As ::: is right-associative (as are all of the operators beginning with : in Scala), Scala parses list1 ::: list2 ::: list3 as list1 ::: (list2 ::: list3). On the other hand, Scala parses list1 ++ list2 ++ list3 as (list1 ++ list2) ++ list3.
As Scala collections are immutable, the runtime needs to iterate the whole list to append another list. list1 ::: (list2 ::: list3) iterates list2 to append list3 and then iterates list1 to append the result of list2 ::: list3. On the contrary, (list1 ++ list2) ++ list3 iterates list1 to append list2, and then the result of list1 ++ list2 to append list3.
In the latter case, list1 is iterated twice, whereas, in the former, it is iterated just once. Hence, from a performance point of view, the ::: operator is more efficient than ++. This is not true when concatenating just two lists, but it gets more and more evident as you concatenate more than two lists in a row.
The second difference is about type safety. As we saw before, ::: only works on Lists, whereas ++ works on any GenTraversableOnces. As a matter of fact, ++ lets you create a union of two collections, even though the collections are not of the same type:
assert(List(1, 2) ++ Map(3 -> 4) == List(1, 2, 3 -> 4))
assert(List(1, 2, 3) ++ "ab" == List(1, 2, 3, 'a', 'b'))
List(1, 2) ++ Map(3 -> 4) returns a List[Any], as no other common super-type can be inferred from the two collections. Similarly, the concatenation of a List[Int] and a String produces again a List[Any].
Using ::: in the two examples above, on the other hand, would result in a compilation error.
3. Conclusion
In this article, we focused on list concatenation in Scala by looking at the differences and the similarities between ::: and ++.
As usual, the full source code can be found over on GitHub.