如何使Scala的类型系统捕获这个匹配错误?

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):

我已经定义了Seq (Seq[T])的一个排序，它是一个正常的字典顺序，除了所有的项(子序列)都是先反转的(所以C、B、a在a、B、C之前，但是在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.

这以前是在List[T]上定义的，但后来我意识到我想要所有的Seq[Seq[T]];这就是为什么我最初在模式匹配块中保留了Nils，而没有实现零匹配，例如一个空数组。

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.

——虽然我理解错误的原因完全好,我无法理解(或至少接受),如果订购成功定义在所有Seq[Seq[T]],一个表面上有效但显然不兼容(doCompare)是如何定义的Seq[Seq[T]](例如数组[[String]|列表数组[String]])尝试使用排序结果没有任何静态类型错误或者警告。

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?

这是因为模式匹配的代码没有被静态地验证来覆盖Seq[Seq[T]的所有可能的“实例”，而且它只处理列表的情况?如果是，在这种情况下，目前可用的解决方案是什么?Scalaz还有什么值得再看一遍的吗?

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.

注:我知道我可以很容易地做了解决方案,适用于所有Seq[Seq[T]]通过不使用模式匹配和诉诸脑袋和尾巴一个if - else块(或语句如果警卫,这只是表面上更好),但我热衷于学习如何充分利用Scala的类型功能(AFAIK f#和Haskell捕捉这些错误早餐);更不用说模式匹配更优雅和可读。

3 个解决方案

#1

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.

它最近在ML上出现了。在这里。

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.

对不起，我懒，上床睡觉。

#2

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.

Scala编译器只对密封类型产生非详尽的匹配警告，而Seq不是。AFAIK，没有办法强迫它去检查，就像尾部递归一样。

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

(afaikf#和Haskell在早餐时发现了这些错误)

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.

Haskell没有类似于Seq的;您所使用的列表中的代码与Haskell(模块化的惰性)相当，而Scala在这种情况下确实捕获了错误。我不知道f#，但是看看http://msdn.microsoft.com/en-us/library/dd547125.aspx，似乎没有支持模式匹配一般IEnumerable 。

#3

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

正如我所提到的，注释Nil与Seq()不一样。例如，WrappedArray不是一个列表。当你使用x:: xs时，它被匹配为列表。Array(“Tallinn”，“爱沙尼亚”)被转换为WrappedArray。当你使用Seq时，总是使用+:模式匹配。

#1