Scala pattern matching on sequences other than Lists

Question

I have the following code which recursively operates on each element within a List

def doMatch(list: List[Int]): Unit = list match {
  case last :: Nil  => println("Final element.")
  case head :: tail => println("Recursing..."); doMatch(tail)
}

Now, ignoring that this functionality is available through filter() and foreach(), this works just fine. However, if I try to change it to accept any Seq[Int], I run into problems:

• Seq doesn't have ::, but it does have +:, which as I understand is basically the same thing. If I try to match on head +: tail however, the compiler complains 'error: not found: value +:'
• Nil is specific to List, and I'm not sure what to replace it with. I'm going to try Seq() if I ever get past the previous problem

Here is how I think the code should look, except it doesn't work:

def doMatch(seq: Seq[Int]): Unit = seq match {
  case last +: Seq() => println("Final element.")
  case head +: tail  => println("Recursing..."); doMatch(tail)
}

Edit: So many good answers! I'm accepting agilesteel's answer as his was the first that noted that :: isn't an operator in my example, but a case class and hence the difference.

Answer 1

As of the ides of March 2012, this works in 2.10+:

  def doMatch(seq: Seq[Int]): Unit = seq match {
    case last +: Seq() => println("Final element.")
    case head +: tail  => println("Recursing..."); doMatch(tail)
  }                                               //> doMatch: (seq: Seq[Int])Unit

  doMatch(List(1, 2))                             //> Recursing...
                                                  //| Final element.

More generally, two different head/tail and init/last decomposition objects mirroring append/prepend were added for Seq in SeqExtractors:

List(1, 2) match { case init :+ last => last } //> res0: Int = 2                                              
List(1, 2) match { case head +: tail => tail } //> res1: List[Int] = List(2)                                               
Vector(1, 2) match { case init :+ last => last } //> res2: Int = 2                                              
Vector(1, 2) match { case head +: tail => tail } //> res3: scala.collection.immutable.Vector[Int] = Vector(2)

Answer 2

Kind of cheating, but here it goes:

def doMatch(seq: Seq[Int]): Unit = seq match {
  case Seq(x) => println("Final element " + x)
  case Seq(x, xs@_*) => println("Recursing..." + x); doMatch(xs)
}

Don't ask me why xs* doesn't work...

Answer 3

There are two :: (pronounced cons) in Scala. One is an operator defined in class List and one is a class (subclass of List), which represents a non empty list characterized by a head and a tail.

head :: tail is a constructor pattern, which is syntactically modified from ::(head, tail).

:: is a case class, which means there is an extractor object defined for it.

Answer 4

You can actually define an object for +: to do exactly what you are looking for:

object +: { 
  def unapply[T](s: Seq[T]) = 
    if(s.nonEmpty)
      Some(s.head, s.tail) 
    else
      None
}

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

Then your code works exactly as expected.

This works because h +: t is equivalent to +:(h,t) when used for patten matching.

Answer 5

I don't think there is pattern matching support for arbitrary sequences in the standard library. You could do it with out pattern matching though:

  def doMatch(seq: Seq[Int]) {
    if (seq.size == 1) println("final element " + seq(0)) else {
      println("recursing")
      doMatch(seq.tail)
    }
  }
  doMatch(1 to 10)

You can define your own extractor objects though. See http://www.scala-lang.org/node/112

object SEQ {
  def unapply[A](s:Seq[A]):Option[(A, Seq[A])] = {
    if (s.size == 0) None else {
      Some((s.head, s.tail))
    }
  }
}

def doMatch(seq: Seq[Int]) {
  seq match {
    case SEQ(head, Seq()) => println("final")
    case SEQ(head, tail) => {
      println("recursing")
      doMatch(tail)
    }
  }
}

Answer 6

A simple tranformation from Seq to List would do the job:

def doMatch (list: List[Int]): Unit = list match {           
    case last :: Nil => println ("Final element.")             
    case head :: tail => println ("Recursing..."); doMatch (tail)
    case Nil => println ("only seen for empty lists") 
  }

def doMatchSeq (seq: Seq[Int]) : Unit = doMatch (seq.toList)

doMatch (List(3, 4, 5))
doMatchSeq (3 to 5)