What's the difference between ::: and ++ for Lists?

Question

Given two lists a and b, what's the difference between a ::: b and a ++ b? I suspected one of these operators would simply call the other, but in fact, the implementations look completely different:

def :::[B >: A](prefix: List[B]): List[B] =
  if (isEmpty) prefix
  else if (prefix.isEmpty) this
  else (new ListBuffer[B] ++= prefix).prependToList(this)

override def ++[B >: A, That](that: GenTraversableOnce[B])
                      (implicit bf: CanBuildFrom[List[A], B, That]): That = {
  val b = bf(this)
  if (b.isInstanceOf[ListBuffer[_]])(this ::: that.seq.toList).asInstanceOf[That]
  else super.++(that)
}

From a usage perspective, should I prefer a ::: b or a ++ b? From an implementation perspective, is there a specific reason why one of these operators doesn't simply call the other?

Answer 1

The difference is in that you can only use ::: on 2 lists -- this operation is only available on the List datatype. Since lists are sequences, it acts as a concatenation operators for lists.

The ++ method is more general - it allows creating a union of any two collections. That may be two sets, in which case it acts as a union, or two sequences in which case it acts as a concatenation.

There is no semantic difference between ++ and ::: for 2 lists -- ::: is the variant of ++ for functional lists that should look more familiar to functional programmers.

The if statement you see in the ++ implementation is an optimization -- if both this collection and that collection are lists, just use the list concatenation operator ::: to add the two lists together. Otherwise, use the generic implementation of ++ that adds all the elements of this and that collection to an appropriate builder for the type That.

So, the relevant difference for lists is performance -- for functional lists you don't need to traverse the second list as a generic ++ implementation would - only the nodes of the first list need to be reinstantiated to create a new functional list.