How to extract remainder of sequence in pattern matching

Question

I've obviously done a very poor job of explaining what I'm looking for in my original post so let's try this one more time. What I'm trying to accomplish is the ability to pass a sequence of items, extract one or more of the items, and then pass the REMAINDER of the sequence on to another extractor. Note that by sequence I mean sequence (not necessarily a List). My previous examples used list as the sequence and I gave some examples of extraction using cons (::), but I could just as well pass an Array as my sequence.

I thought I knew how pattern matching and extraction worked but I could be wrong so to avoid any more basic comments and links to how to do pattern matching sites here's my understanding:

If I want to return a single item from my extractor I would define an unapply method. This method takes whatever type I chose as input (the type could be a sequence...) and returns a single optional item (the return type could itself be a sequence). The return must be wrapped in Some if I want a match or None if I don't. Here is an example that takes a sequence as input and returns the same sequence wrapped in Some but only if it contains all Strings. I could very well just return the sequence wrapped in Some and not do anything else, but this seems to cause confusion for people. The key is if it is wrapped in Some then it will match and if it is None it will not. Just to be more clear, the match will also not happen unless the input also matches my unapply methods input type. Here is my example:

object Test {
  // In my original post I just returned the Seq itself just to verify I 
  // had matched but many people commented they didn't understand what I 
  // was trying to do so I've made it a bit more complicated (e.g. match 
  // only if the sequence is a sequence of Strings). Hopefully I don't 
  // screw this up and introduce a bug :)
  def unapply[A](xs: Seq[A]): Option[Seq[String]] = 
    if (xs forall { _.isInstanceOf[String] })
      Some(xs.asInstanceOf[Seq[String]])
    else
      None
}

Using List as an example, I can now perform the following:

// This works
def test1(xs: List[_]) = xs match {
  case (s: String) :: Test(rest) =>
    println("s = " + s + ", rest = " + rest)
  case _ =>
    println("no match")
}

test1(List("foo", "bar", "baz"))  // "s = foo, rest = List(bar, baz)"

My test1 function takes List as input and extracts the head and tail using cons via the constructor pattern (e.g. ::(s, rest)). It then uses type ascription (: String) to make sure the head (s) is a String. The tail contains List("bar", "baz"). This is a List which means it is also a Seq (sequence). It is then passed as input to my Test extractor which verifies that both "bar" and "baz" are strings and returns the List wrapped in Some. Since Some is returned it is considered a match (although in my original post where I inadvertently mixed up unapplySeq with unapply this didn't work as expected, but that aside...). This is NOT what I'm looking for. This was only an example to show that Test does in fact extract a Seq as input as expected.

Now, here's where I caused mass confusion last time when I inadvertently used unapplySeq instead of unapply in my write up. After much confusion trying to understand the comments that were posted I finally picked up on the mistake. Many thanks to Dan for pointing me in the right direction...

But just be avoid any more confusion, let me clarify my understanding of unapplySeq. Like unapply, unapplySeq takes in whatever argument I choose as input, but instead of returning a single element it returns a sequence of elements. Each item in this sequence can then be used for additional pattern matching. Again, to make a match happen the input type must match and my returned sequence must be wrapped in Some and not be None. When extracting over the sequence of items returned from unapplySeq, you can use _* to match any remaining items not yet matched.

Ok, so my extractor takes a sequence as input and returns a sequence (as a single item) in return. Since I only want to return a single item as a match I need to use unapply NOT unapplySeq. Even though in my case I'm returning a Seq, I don't want unapplySeq because I don't want to do more pattern matching on the items in the Seq. I just want to return the items as a Seq on its own to then be passed to the body of my case match. This sounds confusing, but to those that understand unapply vs unapplySeq I hope it isn't.

So here is what I WANT to do. I want to take something that returns a sequence (e.g. List or Array) and I want to extract a few items from this sequence and then extract the REMAINDER of the items (e.g. _*) as a sequence. Let's call it the remainder sequence. I want to then pass the remainder sequence as input to my extractor. My extractor will then return the remaining items as a single Seq if it matches my criteria. Just to be 100% clear. The List (or Array, etc) will have its unapplySeq extractor called to create the sequence of items. I will extract a one or more of these items and then pass what is left as a sequence to my Test extractor which will use unapply (NOT unapplySeq) to return the remainder. If you are confused by this, then please don't comment...

Here are my tests:

// Doesn't compile. Is there a syntax for this?
def test2(xs: Seq[_]) = xs match {
  // Variations tried:
  //   Test(rest) @ _*  - doesn't compile (this one seems reasonable to me)
  //   Test(rest @ _*)  - doesn't compile (would compile if Test had 
  //                      unapplySeq, but in that case would bind List's
  //                      second element to Test as a Seq and then bind 
  //                      rest to that Seq (if all strings) - not what I'm
  //                      looking for...). I though that this might work
  //                      since Scala knows Test has no unapplySeq only 
  //                      unapply so @ _* can be tied to the List not Test
  //   rest @ Test(_*)  - doesn't compile (didn't expect to)
  case List(s: String, Test(rest) @ _*) => 
    println("s = " + s + " rest = " + rest)
  case _ =>
    println("no match")
}

// This works, but messy
def test3(xs: List[_]) = xs match {
  case List(s: String, rest @ _*) if (
    rest match { case Test(rest) => true; case _ => false }
  ) => 
    println("s = " + s + " rest = " + rest)
  case _ =>
    println("no match")
}

I created test3 based on comments from Julian (thanks Julian..). Some have commented that test3 does what I want so they are confused what I'm looking for. Yes, it accomplishes what I want to accomplish, but I'm not satisfied with it. Daniel's example also works (thanks Daniel), but I'm also not satisfied with having to create another extractor to split things and then do embedded extractions. These solutions seem too much work in order to accomplish something that seems fairly straight forward to me. What I WANT is to make test2 work or know that it can't be done this way. Is the error given because the syntax is wrong? I know that rest @ _* will return a Seq, that can be verified here:

def test4(xs: List[_]) = xs match {
  case List(s: String, rest @ _*) => 
    println(rest.getClass)   // scala.collection.immutable.$colon$colon
  case _ =>
    println("no match")
}

It returns cons (::) which is a List which is a Seq. So how can I pass the _* Seq on to my extractor and have is return bound to the variable rest?

Note that I've also tried passing varargs to my unapply constructor (e.g. unapply(xs: A*)...) but that won't match either.

So, I hope it is clear now when I say I want to extract the remainder of a sequence in pattern matching. I'm not sure how else I can word it.

Based on the great feedback from Daniel I'm hoping he is going to have an answer for me :)

Answer 1

I'd like to extract the first item and pass the remainder on to another extractor.

OK. Your test1 does that, exactly. first_item :: Extractor(the_rest). The weird behavior you're seeing comes from your Test extractor. As you already had the answer to your stated question, and as expected behavior from your Test strikes you as a problem with test1, it seems that what you really want is some help with extractors.

So, please read Extractor Objects, from docs.scala-lang.org, and Pattern Matching in Scala (pdf). Although that PDF has an example of unapplySeq, and suggests where you'd want to use it, here are some extra examples:

object Sorted {
  def unapply(xs: Seq[Int]) =
    if (xs == xs.sortWith(_ < _)) Some(xs) else None
}

object SortedSeq {
  def unapplySeq(xs: Seq[Int]) =
    if (xs == xs.sortWith(_ < _)) Some(xs) else None
}

Interactively:

scala> List(1,2,3,4) match { case Sorted(xs) => Some(xs); case _ => None }
res0: Option[Seq[Int]] = Some(List(1, 2, 3, 4))

scala> List(4,1,2,3) match { case Sorted(xs) => Some(xs); case _ => None }
res1: Option[Seq[Int]] = None

scala> List(4,1,2,3) match { case first :: Sorted(rest) => Some(first, rest); case _ => None }
res2: Option[(Int, Seq[Int])] = Some((4,List(1, 2, 3)))

scala> List(1,2,3,4) match { case SortedSeq(a,b,c,d) => (a,b,c,d) }
res3: (Int, Int, Int, Int) = (1,2,3,4)

scala> List(4,1,2,3) match { case _ :: SortedSeq(a, b, _*) => (a,b) }
res4: (Int, Int) = (1,2)

scala> List(1,2,3,4) match { case SortedSeq(a, rest @ _*) => (a, rest) }
res5: (Int, Seq[Int]) = (1,List(2, 3, 4))

Or maybe -- I only have the faint suspicion of this, you haven't said as much -- you don't want extractor help, but actually you want a terse way to express something like

scala> List(1,2,3,4) match { case 1 :: xs if (xs match { case Sorted(_) => true; case _ => false }) => xs }
res6: List[Int] = List(2, 3, 4)

Erlang has a feature like this (although, without these crazy extractors):

example(L=[1|_]) -> examine(L).

, which pattern-matches the same argument twice - to L and also to [1|_]. In Erlang both sides of the = are full-fledged patterns and could be anything, and you can add a third or more patterns with more =. Scala seems to only support the L=[1|_] form, having a variable and then a full pattern.

scala> List(4,1,2,3) match { case xs @ _ :: Sorted(_) => xs }
collection.immutable.::[Int] = List(4, 1, 2, 3)

Answer 2

Well, the easiest way is this:

case (s: String) :: Test(rest @ _*) =>

If you need this to work on general Seq, you can just define an extractor to split head from tail:

object Split {
  def unapply[T](xs: Seq[T]): Option[(T, Seq[T])] = if (xs.nonEmpty) Some(xs.head -> xs.tail) else None
}

And then use it like

case Split(s: String, Test(rest @ _*)) =>

Also note that if you had defined unapply instead of unapplySeq, then @ _* would not be required on the pattern matched by Test.

Answer 3

:: is an extractor. For how it works (from a random googling), see, for example, here.

def test1(xs: List[_]) = xs match {
  case s :: rest =>
    println("s = " + s + " rest = " + rest)
  case _ =>
    println("no match")
}

scala> test1(List("a", "b", "c"))
s = a rest = List(b, c)

I think this is what you wanted?

Answer 4

Messing around with this, it seems that the issue has something to do with unapplySeq.

object Test {
  def unapply[A](xs: List[A]): Option[List[A]] = Some(xs)
}    

def test1(xs: List[_]) = xs match {
  case (s: String) :: Test(s2 :: rest) =>
    println("s = " + s + " rest = " + rest)
  case _ =>
    println("no match")
}

test1(List("foo", "bar", "baz"))

produces the output:

s = foo rest = List(baz)

I'm havng trouble googling up docs on the difference between unapply and unapplySeq.