CODEWITHSUNDEEP
scalapattern-matchingtypeclassscalazstatic-typing
Erik Kaplun
Erik Kaplun

Reputation: 38217

How to make Scala's type system catch this MatchError?

I've defined an ordering for Seq[Seq[T]] such that it's a normal lexicographic ordering except all items (sub-sequences) are reversed first (so that C,B,A comes before A,B,C but after A,B,A):

implicit def ReverseListOrdering[T: Ordering] = new Ordering[Seq[T]] {
  override def compare(xs1: Seq[T], xs2: Seq[T]) =
    doCompare(xs1.reverse, xs2.reverse)

  private def doCompare(xs1: Seq[T], xs2: Seq[T]): Int = (xs1, xs2) match {
    case (Nil, Nil) => 0
    case (x :: _, Nil) => 1
    case (Nil, x :: _) => -1
    case (x :: xs, y :: ys) =>
      val a = implicitly[Ordering[T]].compare(x, y)
      if (a != 0) a else doCompare(xs, ys)
  }
}

This used to be defined on List[List[T]] at first but I later realized I want it for all Seq[Seq[T]]; this is why I initially left in the Nils in the pattern matching block, while failing to realize Nil never matches e.g. an empty Array.

Later I tried to run this block of code:

// the Seq[String] declarations are needed; otherwise sample` will be Array[Object] for some reason
val sample = List(
  List("Estonia"): Seq[String],
  Array("Tallinn", "Estonia"): Seq[String],
  List("Tallinn", "Harju", "Estonia"): Seq[String])

println(sample.sorted)

This compiles just fine but results in the following error at runtime:

scala.MatchError: (WrappedArray(Estonia, Tallinn),List(Estonia)) (of class scala.Tuple2)

— while I understand the cause of the error perfectly well, what I fail to understand (or at least accept) is, if the Ordering is successfully defined on all Seq[Seq[T]], yet a superficially valid but obviously incompatible (in terms of how doCompare is defined) Seq[Seq[T]] (i.e. Array[List[String] | Array[String]]) attempt to use that ordering results in no static type errors or even warnings whatsoever.

Is this caused by the fact that the pattern matching code is not statically verified to cover all possible "instances" of Seq[Seq[T]] and that it only handles the List case? If yes, what are the currently available workarounds to achieving type safety in such cases? Is Scalaz something to be looked at yet again for a decent solution?

P.S. I'm aware I could easily do away with a solution that works for all Seq[Seq[T]] by not using pattern matching and resorting to head and tail with an if-else block (or case statements if guards, which is only superficially nicer), but I'm keen to learn how to make the most of out Scala's type capabilities (AFAIK F# and Haskell catch these errors for breakfast); not to mention pattern matching is by far more elegant and readable.

Upvotes: 2

Views: 1413

Answers (3)

som-snytt
som-snytt

Reputation: 39577

This might be closer:

scala> def cmp[A, B[_] <: Seq[_]](xs: B[A], ys: B[A]) = (xs, ys) match { case (Nil, Nil) => true }
<console>:7: error: pattern type is incompatible with expected type;
 found   : scala.collection.immutable.Nil.type
 required: B[?A1] where type ?A1 (this is a GADT skolem)
       def cmp[A, B[_] <: Seq[_]](xs: B[A], ys: B[A]) = (xs, ys) match { case (Nil, Nil) => true }
                                                                           ^

There is a known syndrome when the type parameter is on the class instead of the method.

It has surfaced on the ML recently. Here.

Comparing to:

scala> (null: Seq[_]) match { case _: Nil.type => true }
scala.MatchError: null
  ... 33 elided

scala> (null: List[_]) match { case _: Nil.type => true }
<console>:8: warning: match may not be exhaustive.
It would fail on the following input: List(_)
              (null: List[_]) match { case _: Nil.type => true }
                   ^
scala.MatchError: null
  ... 33 elided

scala> (null: List[_]) match { case Nil => true }
<console>:8: warning: match may not be exhaustive.
It would fail on the following input: List(_)
              (null: List[_]) match { case Nil => true }
                   ^
scala.MatchError: null
  ... 33 elided

Sorry to be lazy, but off to bed.

Upvotes: 2

Alexey Romanov
Alexey Romanov

Reputation: 170745

Scala compiler produces non-exhaustive match warnings only for sealed types, which Seq isn't. AFAIK, there is no way to force it to check, like there is for tail recursion.

(AFAIK F# and Haskell catch these errors for breakfast)

Haskell doesn't have an equivalent to Seq; the code you used to have with List is the one which is equivalent to Haskell (modulo laziness), and Scala does catch the error in this case. I don't know F# well, but looking at http://msdn.microsoft.com/en-us/library/dd547125.aspx it seems that pattern matching a general IEnumerable<T> isn't supported.

Upvotes: 1

Andrzej Jozwik
Andrzej Jozwik

Reputation: 14649

Use code:

    implicit def ReverseListOrdering[T: Ordering] = new Ordering[Seq[T]] {
            override def compare(xs1: Seq[T], xs2: Seq[T]) =
            doCompare(xs1.reverse, xs2.reverse)

    private def doCompare(xs1: Seq[T], xs2: Seq[T]): Int = (xs1, xs2) match {
            case (Seq(), Seq()) => 0
            case (x +: _, Seq()) => 1
            case (Seq(), x +: _) => -1
            case (x +: xs, y +: ys) =>
            val a = implicitly[Ordering[T]].compare(x, y)
            if (a != 0) a else doCompare(xs, ys)
            }
   }

As I mention is comment Nil is not the same type as Seq(). For example WrappedArray is not a List. And when you use x :: xs - it is matched as List. Array("Tallinn", "Estonia") is converted to WrappedArray. Always use +: in pattern matching when you use Seq

Upvotes: 0

Related Questions