title: How to make Scala's type system catch this MatchError?
body: <p>I've defined an ordering for <code>Seq[Seq[T]]</code> such that it's a normal lexicographic ordering except all items (sub-sequences) are reversed first (so that <code>C,B,A</code> comes before <code>A,B,C</code> but after <code>A,B,A</code>):</p>
  
  <pre><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 (Nil, Nil) =&gt; 0
      case (x :: _, Nil) =&gt; 1
      case (Nil, x :: _) =&gt; -1
      case (x :: xs, y :: ys) =&gt;
        val a = implicitly[Ordering[T]].compare(x, y)
        if (a != 0) a else doCompare(xs, ys)
    }
  }
  </code></pre>
  
  <p>This used to be defined on <code>List[List[T]]</code> at first but I later realized I want it for all <code>Seq[Seq[T]]</code>; this is why I initially left in the <code>Nil</code>s in the pattern matching block, while failing to realize <code>Nil</code> never matches e.g. an empty <code>Array</code>.</p>
  
  <p>Later I tried to run this block of code:</p>
  
  <pre><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)
  </code></pre>
  
  <p>This compiles just fine but results in the following error at runtime:</p>
  
  <pre><code>scala.MatchError: (WrappedArray(Estonia, Tallinn),List(Estonia)) (of class scala.Tuple2)
  </code></pre>
  
  <p>— while I understand the cause of the error perfectly well, what I fail to understand (or at least accept) is, if the <code>Ordering</code> is successfully defined on all <code>Seq[Seq[T]]</code>, yet a superficially valid but obviously incompatible (in terms of how <code>doCompare</code> is defined) <code>Seq[Seq[T]]</code> (i.e. <code>Array[List[String] | Array[String]]</code>) attempt to use that ordering results in no static type errors or even warnings whatsoever.</p>
  
  <p>Is this caused by the fact that the pattern matching code is not statically verified to cover all possible "instances" of <code>Seq[Seq[T]]</code> and that it only handles the <code>List</code> case? If yes, what are the currently available workarounds to achieving type safety in such cases? Is <a href="https://github.com/scalaz/scalaz" rel="nofollow">Scalaz</a> something to be looked at yet again for a decent solution?</p>
  
  <p><code>P.S.</code> I'm aware I could easily do away with a solution that works for all <code>Seq[Seq[T]]</code> by not using pattern matching and resorting to <code>head</code> and <code>tail</code> with an if-else block (or <code>case</code> 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.</p>