53

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 ++

Community
  • 1
  • 1
Mechanical snail
  • 29,755
  • 14
  • 88
  • 113

2 Answers2

43

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.

kiritsuku
  • 52,967
  • 18
  • 114
  • 136
  • But why did they expose `List.::` publicly? It looks like they could have implemented everything in `List.+:`, replacing the call to `::` in the first `case` with `new scala.collection.immutable.::(elem, this)`. – Mechanical snail Aug 05 '12 at 07:51
  • 1
    @Mechanicalsnail I believe it was done so to make it obvious that the algorithm relies on `List` and not on a general `Seq` for the reasons already explained by sschaef. Also, according to [this table](http://docs.scala-lang.org/overviews/collections/performance-characteristics.html) there are huge differences on how each `Seq` implementation is intended to be used. For instance `+:` will perform awfully on a `Queue` and using `::` protects you from accidently passing it to your algorithm. – Nikita Volkov Aug 05 '12 at 09:07
  • 3
    @Mechanicalsnail: The Scala community already had some discussions on the sense of `::`. Another point often mentioned is that the existence of `::` has historical reasons. The first versions of Scala did not have such generalized collections as we have today. Furthermore, the `ML` family of functional languages do have `:` as List-prepending operator. Therefore its origin is much deeper as it may look like. – kiritsuku Aug 05 '12 at 09:30
15

+: is more generic, since it allows the result type to be different from the type of the object it is called on. For example:

scala> Range(1,4).+:(0)
res7: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 2, 3)
Kim Stebel
  • 41,826
  • 12
  • 125
  • 142