用于检查集合是否已订购的惯用法构造

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

使用fold的替代算法:

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)

Answer 2

通过"惯用语",我假设你在他们的论文" Applicative Programming With Effects "中谈论McBride和Paterson的"成语" .:O)

以下是如何使用他们的习语来检查是否订购了一个集合:

import scalaz._
import Scalaz._

case class Lte[A](v: A, b: Boolean)

implicit def lteSemigroup[A:Order] = new Semigroup[Lte[A]] {
  def append(a1: Lte[A], a2: => Lte[A]) = {
    lazy val b = a1.v lte a2.v
    Lte(if (!a1.b || b) a1.v else a2.v, a1.b && b && a2.b)
  }
}

def isOrdered[T[_]:Traverse, A:Order](ta: T[A]) =
  ta.foldMapDefault(x => some(Lte(x, true))).fold(_.b, true)

这是如何工作的:

T[A]存在实现的任何数据结构Traverse[T]都可以使用Applicative仿函数或"惯用法"或"强松弛的monoidal仿函数" 遍历.只是碰巧每个人都能Monoid免费获得这样的成语(参见论文第4节).

monoid只是某种类型的关联二元运算,以及该运算的标识元素.我正在定义一个Semigroup[Lte[A]](半群与monoid相同,除了没有identity元素),其关联操作跟踪两个值中的较小值以及左值是否小于正确值.当然Option[Lte[A]]只是我们的半群自由生成的幺半群.

最后,foldMapDefault遍历T由幺半群诱导的习语中的集合类型.b如果每个值小于以下所有值(意味着集合已订购),或者None如果T没有元素,则结果将包含true .由于空T按常规排序,因此我们将true第二个参数传递给最后fold一个Option.

作为奖励,这适用于所有可遍历的集合.演示:

scala> val b = isOrdered(List(1,3,5,7,123))
b: Boolean = true

scala> val b = isOrdered(Seq(5,7,2,3,6))
b: Boolean = false

scala> val b = isOrdered(Map((2 -> 22, 33 -> 3)))
b: Boolean = true

scala> val b = isOrdered(some("hello"))
b: Boolean = true

一个测试:

import org.scalacheck._

scala> val p = forAll((xs: List[Int]) => (xs /== xs.sorted) ==> !isOrdered(xs))
p:org.scalacheck.Prop = Prop

scala> val q = forAll((xs: List[Int]) => isOrdered(xs.sorted))
q: org.scalacheck.Prop = Prop

scala> p && q check
+ OK, passed 100 tests.

这就是你如何通过惯用遍历来检测集合是否有序.

Answer 3

事实上,我正在使用它,这与Kim Stebel非常相似.

def isOrdered(list: List[Int]): Boolean = (
  list 
  sliding 2 
  map { 
    case List(a, b) => () => a < b 
  } 
  forall (_())
)

Answer 4

万一你在上面的评论中错过了missfaktor的优雅解决方案:

(l, l.tail).zipped.forall(_ <= _)

此解决方案非常易读,将在第一个无序元素上退出.