scala - 检查集合是否有序的惯用构造

Question

带着学习的意图，进一步到此question ，我仍然对检查列表(或集合)是否有序的算法的显式递归的惯用替代方案感到好奇。 (我在这里通过使用运算符进行比较并将 Int 作为类型来保持简单；我想在深入研究它的泛型之前先看看该算法)

基本的递归版本是(@Luigi Plinge):

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: xs => x <= xs.head && isOrdered(xs)
}

表现不佳的惯用方式是:

def isOrdered(l: List[Int]) = l == l.sorted

使用折叠的替代算法:

def isOrdered(l: List[Int]) =
  l.foldLeft((true, None:Option[Int]))((x,y) =>
    (x._1 && x._2.map(_ <= y).getOrElse(true), Some(y)))._1

它的缺点是，即使它可以在找到第一个无序元素后提前停止，它也会比较列表中的所有 n 个元素。有没有办法“停止”折叠，从而使其成为更好的解决方案？

还有其他(优雅的)替代方案吗？

Answer 1

这将在第一个乱序元素之后退出。因此它应该表现良好，但我还没有测试过。在我看来，它也更加优雅。 :)

def sorted(l:List[Int]) = l.view.zip(l.tail).forall(x => x._1 <= x._2)