Why can I use :: operator with Seq in pattern matching but not elsewhere

Question

So I have been really confused with this behavior regarding Seq in Scala.

When using pattern matching I am able to use either :: or +: operator and they seem interchangeable

val s=Seq(1,2,3)
s match{
case x :: l => ...

but when I'm trying to use :: in different situation like so:

val s=1::Seq(2,3)

I receive "value :: is not a member of Seq[Int]" message. I understand that I am supposed to use += and =+ operators with Seq, but why :: work only in pattern matching scenario?

Answer 1

:: is for Lists, and in fact Seq.apply will currently give you a List:

scala> val s = Seq(1,2,3)
s: Seq[Int] = List(1, 2, 3)

So the type of value s is Seq[Int], but the object it points to is of type List[Int]. That's fine, because List extends Seq. And that will of course match a pattern involving :: because it is in fact a List:

scala> s match { case x :: xs => x }
res2: Int = 1

But the type of expression Seq(1,2,3) is not List[Int] but Seq[Int] -- even though the actual object is indeed a List. So the following fails because Seq does not define a :: method:

scala> val s = 1 :: Seq(2,3)
<console>:7: error: value :: is not a member of Seq[Int]
       val s = 1 :: Seq(2,3)

You have to use the method for Seq instead:

scala> val s = 1 +: Seq(2,3)
s: Seq[Int] = List(1, 2, 3)

The key to your confusion is that when you invoke a method on a value like s, the set of methods available depends entirely on the value's static type, whereas the pattern match checks that the object being matched is of class ::.

To show this, let's compile some sample code and use javap to see the bytecode; the first few instructions of the first method check that the argument is of class :: (rather than some other class extending Seq) and cast to it:

NS% cat Test.scala
object Test {
  def first(xs: Seq[Int]) = xs match { case x :: xs => x }
}

NS% javap -c Test\$.class
Compiled from "Test.scala"
public final class Test$ {
  public static final Test$ MODULE$;

  public static {};
    Code:
       0: new           #2                  // class Test$
       3: invokespecial #12                 // Method "<init>":()V
       6: return

  public int first(scala.collection.Seq<java.lang.Object>);
    Code:
       0: aload_1
       1: astore_2
       2: aload_2
       3: instanceof    #16                 // class scala/collection/immutable/$colon$colon
       6: ifeq          30
       9: aload_2
      10: checkcast     #16                 // class scala/collection/immutable/$colon$colon
      13: astore_3
      14: aload_3
      15: invokevirtual #20                 // Method scala/collection/immutable/$colon$colon.head:()Ljava/lang/Object;
      18: invokestatic  #26                 // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
      21: istore        4
      23: iload         4
      25: istore        5
      27: iload         5
      29: ireturn
      30: new           #28                 // class scala/MatchError
      33: dup
      34: aload_2
      35: invokespecial #31                 // Method scala/MatchError."<init>":(Ljava/lang/Object;)V
      38: athrow

Finally, you could ask why the Scala folks didn't make :: the equivalent method (prepend an element) for Seq. If they had, then 1 :: Seq(2,3) would work.

But for Seq they really needed a pair of operators, one to prepend (this one must end in a colon, so that it is right-associative) and one to append. You want to avoid appending an element to a List because you have to traverse the existing elements to do so, but the same is not true for Seqs in general -- e.g. append is quite efficient for a Vector. So they chose +: for prepend and :+ for append.

Of course, you could ask why they didn't use +: for List to match Seq. I don't know the full answer to that. I do know that :: comes from other languages which have list structures, so in part the answer is probably consistency with established conventions. And perhaps they did not realize that they wanted a matching pair of operators for a supertype of List until it was too late -- not sure. Does anyone know the history here?

Answer 2

:: pronounced cons is an operator for Lists. Seq is a generic trait that all Scala sequences inherit. This is a generic interface for any type of sequence and not just for lists.

Given that the by default Scala uses Lists as the sequence return by the Seq() factory method, then Pattern Matching can operate with cons.

So you can do

val s = 1::List(2,3)

But not

val s = 1::Seq(2,3)