How is the pattern matching for :: implemented?

Question

For instance,

List(1, 2, 3) match {
  case x :: y => (x, y)
}

In the code above, pattern matching will automatically find out that any non-empty List matches the case x :: y. I would like to know, why this happens?

As we all know, there is a :: method in List class. In addition, I find there is a :: case class in "list.scala":

/** A non empty list characterized by a head and a tail.
 *  @param head the first element of the list
 *  @param tl   the list containing the remaining elements of this list after the first one.
 *  @tparam B   the type of the list elements.
 *  @author  Martin Odersky
 *  @version 1.0, 15/07/2003
 *  @since   2.8
 */
@SerialVersionUID(509929039250432923L) // value computed by serialver for 2.11.2, annotation added in 2.11.4
final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false
}

Therefore, we can write ::(1, Nil) to construct a new List. What's more, with the infix notation in Scala, we are able to equivalently write 1 :: Nil (although it turns out that Nil.::(1) will be invoked rather than ::(1, Nil), maybe owing to some precedence rules.)

As a result, I guess the case class :: has something to do with the pattern matching for :: (say, pattern x :: y will be matched by something like ::.unapply). But I did not find any unapply method or companion object for case class ::.

Could anyone please tell me whether my guess is correct? If not, how is the pattern matching for :: implemented in Scala?

Thanks!

EDIT:

Obviously, case class as :: is, a ::.unapply will be automatically generated for ::. Thus I can understand that case x :: y will match instance of :: (say, ::(1, 2)). But as we all know, case x :: y also matches all instances of type List, which is the base class of ::. Thus I think there might be some special unapply were my guess correct.

::.unapply exists because unapply is automatically generated for case classes, which :: is. — Michael Zajac
Thanks @m-z, I can understand why x :: y will match a instance of :: case class. But I can't figure out why it also matches a general List, which is the base class of case class ::. — Lifu Huang
@m-z, please correct me if I am wrong, I think the automatically generated D.unapply only matches instance of D but not the base class of D. — Lifu Huang
@m-z unapply isn't used for constructor pattern, not that you said so. — som-snytt
Pattern matching in Scala works by using unapply method of companion object as Extractors. You can read more about them in Part-1 and Part-2 of The Neophyte's Guide to Scala — sarveshseri

som-snytt som-snytt · Accepted Answer · 2016-09-21T04:41:10

It's called a constructor pattern:

http://www.scala-lang.org/files/archive/spec/2.11/08-pattern-matching.html#constructor-patterns

The type (::) just has to conform to the pattern type (List), and then the "arg" patterns must match.

It looks similar to an extractor pattern, but is different.

edit to show look ma, no extractor:

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

scala> vs match { case 1 :: rest => "ok" }
<console>:13: warning: match may not be exhaustive.
It would fail on the following inputs: List((x: Int forSome x not in 1)), Nil
       vs match { case 1 :: rest => "ok" }
       ^
res0: String = ok

scala> :javap -pv -
[snip]

  public $line4.$read$$iw$$iw$();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=4, locals=5, args_size=1
         0: aload_0
         1: invokespecial #30                 // Method java/lang/Object."<init>":()V
         4: aload_0
         5: putstatic     #32                 // Field MODULE$:L$line4/$read$$iw$$iw$;
         8: aload_0
         9: getstatic     #35                 // Field $line3/$read$$iw$$iw$.MODULE$:L$line3/$read$$iw$$iw$;
        12: invokevirtual #39                 // Method $line3/$read$$iw$$iw$.vs:()Lscala/collection/immutable/List;
        15: astore_2
        16: aload_2
        17: instanceof    #41                 // class scala/collection/immutable/$colon$colon
        20: ifeq          52
        23: aload_2
        24: checkcast     #41                 // class scala/collection/immutable/$colon$colon
        27: astore_3
        28: aload_3
        29: invokevirtual #45                 // Method scala/collection/immutable/$colon$colon.head:()Ljava/lang/Object;
        32: invokestatic  #51                 // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
        35: istore        4
        37: iconst_1
        38: iload         4
        40: if_icmpne     49
        43: ldc           #53                 // String ok
        45: astore_1
        46: goto          64
        49: goto          55
        52: goto          55
        55: new           #55                 // class scala/MatchError
        58: dup
        59: aload_2
        60: invokespecial #58                 // Method scala/MatchError."<init>":(Ljava/lang/Object;)V
        63: athrow
        64: aload_1
        65: putfield      #28                 // Field res0:Ljava/lang/String;
        68: return
[snip]

any non-empty List matches the case x :: y. I would like to know, why this happens?

A non-empty List must be of type ::. That's what it tests in a constructor pattern. The empty list, Nil, is not.

How is the pattern matching for :: implemented?

1 Answers