惯用的构造,用于检查是否已下令收藏 [英] 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屋!