MatchError when match receives an IndexedSeq but not a LinearSeq

Question

Is there a reason that match written against Seq would work differently on IndexedSeq types than the way it does on LinearSeq types? To me it seems like the code below should do the exact same thing regardless of the input types. Of course it doesn't or I wouldn't be asking.

import collection.immutable.LinearSeq
object vectorMatch {
  def main(args: Array[String]) {
    doIt(Seq(1,2,3,4,7), Seq(1,4,6,9))
    doIt(List(1,2,3,4,7), List(1,4,6,9))
    doIt(LinearSeq(1,2,3,4,7), LinearSeq(1,4,6,9))
    doIt(IndexedSeq(1,2,3,4,7), IndexedSeq(1,4,6,9))
    doIt(Vector(1,2,3,4,7), Vector(1,4,6,9))
  }

  def doIt(a: Seq[Long], b: Seq[Long]) {
    try {
      println("OK! " + m(a, b))
    }
    catch {
      case ex: Exception => println("m(%s, %s) failed with %s".format(a, b, ex))
    }
  }

  @annotation.tailrec
  def m(a: Seq[Long], b: Seq[Long]): Seq[Long] = {
    a match {
      case Nil => b
      case firstA :: moreA => b match {
        case Nil => a
        case firstB :: moreB if (firstB < firstA) => m(moreA, b)
        case firstB :: moreB if (firstB > firstA) => m(a, moreB)
        case firstB :: moreB if (firstB == firstA) => m(moreA, moreB)
        case _ => throw new Exception("Got here: a: " + a + "  b: " + b)
      }
    }
  }
}

Running this on 2.9.1 final, I get the following output:

OK! List(2, 3, 4, 7)
OK! List(2, 3, 4, 7)
OK! List(2, 3, 4, 7)
m(Vector(1, 2, 3, 4, 7), Vector(1, 4, 6, 9)) failed with scala.MatchError: Vector(1, 2, 3, 4, 7) (of class scala.collection.immutable.Vector)
m(Vector(1, 2, 3, 4, 7), Vector(1, 4, 6, 9)) failed with scala.MatchError: Vector(1, 2, 3, 4, 7) (of class scala.collection.immutable.Vector)

It runs fine for List-y things, but fails for Vector-y things. Am I missing something? Is this a compiler bug?

The scalac -print output for m looks like:

@scala.annotation.tailrec def m(a: Seq, b: Seq): Seq = {
  <synthetic> val _$this: object vectorMatch = vectorMatch.this;
  _m(_$this,a,b){
    <synthetic> val temp6: Seq = a;
    if (immutable.this.Nil.==(temp6))
      {
        b
      }
    else
      if (temp6.$isInstanceOf[scala.collection.immutable.::]())
        {
          <synthetic> val temp8: scala.collection.immutable.:: = temp6.$asInstanceOf[scala.collection.immutable.::]();
          <synthetic> val temp9: Long = scala.Long.unbox(temp8.hd$1());
          <synthetic> val temp10: List = temp8.tl$1();
          val firstA$1: Long = temp9;
          val moreA: List = temp10;
          {
            <synthetic> val temp1: Seq = b;
            if (immutable.this.Nil.==(temp1))
              {
                a
              }
            else
              if (temp1.$isInstanceOf[scala.collection.immutable.::]())
                {
                  <synthetic> val temp3: scala.collection.immutable.:: = temp1.$asInstanceOf[scala.collection.immutable.::]();
                  <synthetic> val temp4: Long = scala.Long.unbox(temp3.hd$1());
                  <synthetic> val temp5: List = temp3.tl$1();
                  val firstB: Long = temp4;
                  if (vectorMatch.this.gd1$1(firstB, firstA$1))
                    body%11(firstB){
                      _m(vectorMatch.this, moreA, b)
                    }
                  else
                    {
                      val firstB: Long = temp4;
                      val moreB: List = temp5;
                      if (vectorMatch.this.gd2$1(firstB, moreB, firstA$1))
                        body%21(firstB,moreB){
                          _m(vectorMatch.this, a, moreB)
                        }
                      else
                        {
                          val firstB: Long = temp4;
                          val moreB: List = temp5;
                          if (vectorMatch.this.gd3$1(firstB, moreB, firstA$1))
                            body%31(firstB,moreB){
                              _m(vectorMatch.this, moreA, moreB)
                            }
                          else
                            {
                              body%41(){
                                throw new java.lang.Exception("Got here: a: ".+(a).+("  b: ").+(b))
                              }
                            }
                        }
                    }
                }
              else
                {
                  body%41()
                }
          }

        }
      else
        throw new MatchError(temp6)
  }
};

Comprehensive

Answer 1

You can't use :: for anything other than List. The Vector is failing to match because :: is a case class that extends List, so its unapply method does not work for Vector.

val a :: b = List(1,2,3)    // fine
val a :: b = Vector(1,2,3)  // error

But you can define your own extractor that works for all sequences:

object +: {
  def unapply[T](s: Seq[T]) =
    s.headOption.map(head => (head, s.tail))
}

So you can do:

val a +: b = List(1,2,3)   // fine
val a +: b = Vector(1,2,3) // fine

Lytle

Thanks, @dhg. I read this answer once, then read this (scala-lang.org/old/node/112), and then read your post again. – Teak

As already pointed here (https://mcmap.net/q/617947/-what-is-the-idiomatic-way-to-pattern-match-sequence-comprehensions) you could also use Seq as follows: case Seq(a, b, rest @ _ *). – Lydgate

Answer 2

Followed pattern match works for List, Seq, LinearSeq, IndexedSeq, Vector.

  Vector(1,2) match {
  case a +: as => s"$a + $as"
  case _      => "empty"  
}

Mcnew

Answer 3

In Scala 2.10 object +: was introduced at this commit. Since then, for every SeqLike, you can do:

@annotation.tailrec
def m(a: Seq[Long], b: Seq[Long]): Seq[Long] = {
  a match {
    case Nil => b
    case firstA +: moreA => b match {
      case Nil => a
      case firstB +: moreB if (firstB < firstA) => m(moreA, b)
      case firstB +: moreB if (firstB > firstA) => m(a, moreB)
      case firstB +: moreB if (firstB == firstA) => m(moreA, moreB)
      case _ => throw new Exception("Got here: a: " + a + "  b: " + b)
    }
  }
}

Code run at Scastie.

Didymium