37

出于学习的目的并进一步解决这个问题，我一直对用于检查列表（或集合）是否有序的算法的显式递归的惯用替代方案感到好奇。（我在这里通过使用运算符进行比较和 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 个元素，即使它可以在找到第一个乱序元素后更早停止。有没有办法“停止”折叠并因此使其成为更好的解决方案？

还有其他（优雅的）替代品吗？

4

9 回答 9

63

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

def sorted(l:List[Int]) = l.view.zip(l.tail).forall(x => x._1 <= x._2)
于 2011-10-21T17:16:44.830 回答
39

通过“惯用语”，我假设您正在谈论 McBride 和 Paterson 在他们的论文Applicative Programming With Effects中的“惯用语” 。: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函子、或“成语”或“强松散单曲面函子”进行遍历。碰巧everyone 都Monoid免费引出了这样一个习语（见论文的第4 节）。

幺半群只是某种类型的关联二元运算，以及该运算的标识元素。我正在定义一个Semigroup[Lte[A]]（半群与幺半群相同，除了没有单位元素），其关联运算跟踪两个值中的较小者以及左值是否小于右值。当然Option[Lte[A]]，这只是我们的半群自由生成的幺半群。

最后，foldMapDefault遍历T由幺半群诱导的成语中的集合类型。b如果每个值都小于以下所有值（意味着集合已排序），或者没有元素，None则结果将包含 true。T由于空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.

这就是您进行惯用遍历以检测集合是否已排序的方式。

于 2011-10-21T20:24:54.073 回答
8

事实上，我同意这个，这与 Kim Stebel 的非常相似。

def isOrdered(list: List[Int]): Boolean = (
  list 
  sliding 2 
  map { 
    case List(a, b) => () => a < b 
  } 
  forall (_())
)
于 2011-10-21T19:45:56.030 回答
6

如果您在上面的评论中错过了missingfaktor的优雅解决方案：

斯卡拉 < 2.13.0

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

斯卡拉 2.13.x+

l.lazyZip(l.tail).forall(_ <= _)

这个解决方案可读性很强，会在第一个乱序元素上退出。

于 2015-04-28T01:03:11.657 回答
2

递归版本很好，但仅限于List（通过有限的更改，它会很好地工作LinearSeq）。

如果它是在标准库中实现的（会有意义），它可能会在其中完成IterableLike并具有完全命令式的实现（参见实例方法find）

foldLeft您可以用 a中断return（在这种情况下，您只需要前一个元素而不是布尔值）

import Ordering.Implicits._
def isOrdered[A: Ordering](seq: Seq[A]): Boolean = {
  if (!seq.isEmpty)
    seq.tail.foldLeft(seq.head){(previous, current) => 
      if (previous > current) return false; current
    }
  true
}

但我看不出它比命令式实现更好甚至是惯用的。我不确定我实际上不会称之为命令。

另一种解决方案可能是

def isOrdered[A: Ordering](seq: Seq[A]): Boolean = 
  ! seq.sliding(2).exists{s => s.length == 2 && s(0) > s(1)}

相当简洁，也许这可以称为惯用语，我不确定。但我认为这不是太清楚。此外，所有这些方法的性能可能都比命令式或尾递归版本差得多，而且我认为它们没有任何额外的清晰度可以购买。

你也应该看看这个问题。

于 2011-10-21T17:07:48.903 回答
1

要停止迭代，您可以使用Iteratee：

import scalaz._
import Scalaz._
import IterV._
import math.Ordering
import Ordering.Implicits._

implicit val ListEnumerator = new Enumerator[List] {
  def apply[E, A](e: List[E], i: IterV[E, A]): IterV[E, A] = e match {
    case List() => i
    case x :: xs => i.fold(done = (_, _) => i,
                           cont = k => apply(xs, k(El(x))))
  }
}

def sorted[E: Ordering] : IterV[E, Boolean] = {
  def step(is: Boolean, e: E)(s: Input[E]): IterV[E, Boolean] = 
    s(el = e2 => if (is && e < e2)
                   Cont(step(is, e2))
                 else
                   Done(false, EOF[E]),
      empty = Cont(step(is, e)),
      eof = Done(is, EOF[E]))

  def first(s: Input[E]): IterV[E, Boolean] = 
    s(el = e1 => Cont(step(true, e1)),
      empty = Cont(first),
      eof = Done(true, EOF[E]))

  Cont(first)
}


scala> val s = sorted[Int]
s: scalaz.IterV[Int,Boolean] = scalaz.IterV$Cont$$anon$2@5e9132b3

scala> s(List(1,2,3)).run
res11: Boolean = true

scala> s(List(1,2,3,0)).run
res12: Boolean = false
于 2011-10-22T06:06:27.240 回答
0

如果将 List 分成两部分，并检查第一部分的最后一个是否低于第二部分的第一部分。如果是这样，您可以同时检查这两个部分。这里的原理图，首先没有并行：

def isOrdered (l: List [Int]): Boolean = l.size/2 match {
  case 0 => true 
  case m => {
    val  low = l.take (m)
    val high = l.drop (m)
    low.last <= high.head && isOrdered (low) && isOrdered (high) 
  }
}

现在使用并行，并使用splitAt而不是take/drop：

def isOrdered (l: List[Int]): Boolean = l.size/2 match {
  case 0 => true 
  case m => {
    val (low, high) = l.splitAt (m)
    low.last <= high.head && ! List (low, high).par.exists (x => isOrdered (x) == false) 
  }
}
于 2011-10-22T19:07:40.993 回答
0 
def isSorted[A <: Ordered[A]](sequence: List[A]): Boolean = {
  sequence match {
    case Nil        => true
    case x::Nil     => true
    case x::y::rest => (x < y) && isSorted(y::rest)
  }
}

Explain how it works.
于 2016-12-08T22:29:30.803 回答
0

我的解决方案与missingfaktor的解决方案和订购相结合

def isSorted[T](l: Seq[T])(implicit ord: Ordering[T]) = (l, l.tail).zipped.forall(ord.lt(_, _))

您可以使用自己的比较方法。例如

isSorted(dataList)(Ordering.by[Post, Date](_.lastUpdateTime))
于 2017-03-16T15:03:27.103 回答