带着学习的意图,进一步到此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 个元素。有没有办法“停止”折叠,从而使其成为更好的解决方案?
还有其他(优雅的)替代方案吗?
最佳答案
这将在第一个乱序元素之后退出。因此它应该表现良好,但我还没有测试过。在我看来,它也更加优雅。 :)
def sorted(l:List[Int]) = l.view.zip(l.tail).forall(x => x._1 <= x._2)
关于scala - 检查集合是否有序的惯用构造,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7852471/