惯用的构造，用于检查是否已下令收藏 [英] Idiomatic construction to check whether a collection is ordered

问题描述

出于学习的目的，并进一步研究了问题，对检查列表(或集合)是否有序的算法的显式递归的惯用替代方法感到好奇. (我在这里通过使用运算符比较和将Int作为类型来简化事情；在研究泛型之前，我想先看一下算法)

With the intention of learning and further to this question, I've remained curious of the idiomatic alternatives to explicit recursion for an algorithm that checks whether a list (or collection) is ordered. (I'm keeping things simple here by using an operator to compare and Int as type; I'd like to look at the algorithm before delving into the generics of it)

基本的递归版本为(@Luigi Plinge编写):

The basic recursive version would be (by @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)
}

表现不佳的惯用方式是:

A poor performing idiomatic way would be:

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

使用fold的另一种算法:

An alternative algorithm using 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个元素进行比较.有没有一种方法可以停止"折叠并因此使其成为更好的解决方案?

It has the drawback that it will compare for all n elements of the list even if it could stop earlier after finding the first out-of-order element. Is there a way to "stop" fold and therefore making this a better solution?

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

Any other (elegant) alternatives?

推荐答案

通过惯用语"，我假设您在他们的论文

By "idiomatic", I assume you're talking about McBride and Paterson's "Idioms" in their paper Applicative Programming With Effects. :o)

在这里，您将使用他们的习惯用法来检查是否订购了商品:

Here's how you would use their idioms to check if a collection is ordered:

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)

这是它的工作方式:

存在Traverse[T]实现的任何数据结构T[A]，都可以使用Applicative函子，成语"或强松散单曲面函子"遍历.碰巧的是，每个Monoid都免费地产生了这样的成语(请参见本文的第4部分).

Any data structure T[A] where there exists an implementation of Traverse[T], can be traversed with an Applicative functor, or "idiom", or "strong lax monoidal functor". It just so happens that every Monoid induces such an idiom for free (see section 4 of the paper).

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

A monoid is just an associative binary operation over some type, and an identity element for that operation. I'm defining a Semigroup[Lte[A]] (a semigroup is the same as a monoid, except without the identity element) whose associative operation tracks the lesser of two values and whether the left value is less than the right value. And of course Option[Lte[A]] is just the monoid generated freely by our semigroup.

最后，foldMapDefault遍历由类群动物生成的惯用语中的收集类型T.如果每个值小于以下所有值(表示集合已排序)，则结果b将包含true；如果T没有任何元素，则结果将包含None.由于按惯例对空的T进行了排序，因此我们将true作为第二个参数传递给Option的最后一个fold.

Finally, foldMapDefault traverses the collection type T in the idiom induced by the monoid. The result b will contain true if each value was less than all the following ones (meaning the collection was ordered), or None if the T had no elements. Since an empty T is sorted by convention, we pass true as the second argument to the final fold of the Option.

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

As a bonus, this works for all traversable collections. A demo:

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.

这就是您进行惯用遍历以检测是否已订购集合的方式.

And that's how you do idiomatic traversal to detect if a collection is ordered.

这篇关于惯用的构造，用于检查是否已下令收藏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！