2

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.

Lifu Huang
  • 11,930
  • 14
  • 55
  • 77
  • 2
    `::.unapply` exists because `unapply` is automatically generated for case classes, which `::` is. – Michael Zajac Sep 21 '16 at 03:21
  • 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 Sep 21 '16 at 03:44
  • @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 Sep 21 '16 at 03:47
  • @m-z unapply isn't used for constructor pattern, not that you said so. – som-snytt Sep 21 '16 at 04:46
  • 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](http://danielwestheide.com/scala/neophytes.html) – sarveshseri Sep 21 '16 at 04:53
  • @SarveshKumarSingh No, that's wrong. Also, there's the thing about not answering questions in the comments. :) – som-snytt Sep 21 '16 at 05:02
  • @SarveshKumarSingh I see the classic guide speaks wrongly, but in the comments he correctly links to http://stackoverflow.com/questions/754166/how-is-pattern-matching-in-scala-implemented-at-the-bytecode-level but that's not an implementation detail. Arguably this question duplicates that. – som-snytt Sep 21 '16 at 05:08
  • @som-snytt Yes... if we really talk about how it actually works under the hood, but I doubt the OP was talking about under the hood stuff. My guess is that OP is interested in figuring out more flexible or dry patterns. And specifically the semantics of `::` pattern is explained in part-2. – sarveshseri Sep 21 '16 at 06:56
  • @SarveshKumarSingh No, it's *not* implementation detail. The case class has to conform to the expected type of the pattern; the semantics are different. OP asked for implementation but really needed to know just the spec. I don't understand why you say :: is in part 2, because he is showing List.unapplySeq there, which is totally different. (Or please show me where I'm mistaken.) – som-snytt Sep 21 '16 at 07:27
  • @som-snytt You are right. I remember reading about `::` pattern details somewhere and confused the memory with Neophytes guide. – sarveshseri Sep 21 '16 at 09:41

1 Answers1

2

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.

som-snytt
  • 39,429
  • 2
  • 47
  • 129
  • Thanks @som-snytt. So the existence of :: case class has nothing to do with pattern matching for ::, right? – Lifu Huang Sep 21 '16 at 04:54
  • It's a ctor pattern because it's a case class. Related confusion: https://issues.scala-lang.org/browse/SI-9795 – som-snytt Sep 21 '16 at 05:00
  • Contrast `scala> (1 :: Nil) match { case List(h) => h }` which is an extractor (an unapplySeq). – som-snytt Sep 21 '16 at 05:13
  • That's weird. Why `List(1, 2, 3).isInstanceOf[::[Int]]` gives `true`? I thought `::`(the case class) is a subtype of `List`. (Sorry, I am new to Scala) – Lifu Huang Sep 21 '16 at 08:53
  • Sorry, maybe I did not express myself clearly. Thanks to your help, I have already understood the difference between extractor and constructor pattern. But I still have a question that why `List(1, 2, 3).isInstanceOf[::[Int]]` gives `true`. – Lifu Huang Sep 21 '16 at 14:52
  • I misunderstood you. `List.apply(1)` gives you a `::`. Asking isInstanceOf is not asking `List[Int] <:< ::[Int]`. It's a runtime reflective type check. So a boxed Int i isInstanceOf[java.lang.Integer] for example. – som-snytt Sep 21 '16 at 16:31