scala - What's the difference between `::` and `+:` for prepending to a list)?

Question

List has 2 methods that are specified to prepend an element to an (immutable) list:

• +: (implementing Seq.+:), and
• :: (defined only in List)

+: technically has a more general type signature—

def +:[B >: A, That](elem: B)(implicit bf: CanBuildFrom[List[A], B, That]): That
def ::[B >: A](x: B): List[B]

—but ignoring the implicit, which according to the doc message merely requires That to be List[B], the signatures are equivalent.

What is the difference between List.+: and List.::? If they are in fact identical, I assume +: would be preferred to avoid depending on the concrete implementation List. But why was another public method defined, and when would client code call it?

Edit

There is also an extractor for :: in pattern matching, but I'm wondering about these particular methods.

See also: Scala list concatenation, ::: vs ++

Answer 1

The best way to determine the difference between both methods is to look it the source code.

The source of :::

def ::[B >: A] (x: B): List[B] =
  new scala.collection.immutable.::(x, this)

The source of +::

override def +:[B >: A, That](elem: B)(implicit bf: CanBuildFrom[List[A], B, That]): That = bf match {
  case _: List.GenericCanBuildFrom[_] => (elem :: this).asInstanceOf[That]
  case _ => super.+:(elem)(bf)
}

As you can see, for List, both methods do one and the same (the compiler will choose List.canBuildFrom for the CanBuildFrom argument).

So, which method to use? Normally one would choose the interface (+:) than the implementation (::) but because List is a general data structure in functional languages it has its own methods which are widely used. Many algorithms are build up the way how List works. For example you will find a lot of methods which prepend single elements to List or call the convenient head or tail methods because all these operations are O(1). Therefore, if you work locally with a List (inside of single methods or classes), there is no problem to choose the List-specific methods. But if you want to communicate between classes, i.e. you want to write some interfaces, you should choose the more general Seq interface.