Идиоматическая конструкция, чтобы проверить, заказана ли коллекция
С целью изучения и дальнейшего изучения этого вопроса мне по-прежнему любопытны идиоматические альтернативы явной рекурсии для алгоритма, который проверяет, упорядочен ли список (или коллекция). (Я упрощаю это, используя оператор для сравнения и 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 элементов списка, даже если он мог бы остановиться раньше после нахождения первого вышедшего из строя элемента. Есть ли способ "остановить" фолд и, следовательно, сделать это лучшим решением?
Любые другие (элегантные) альтернативы?
9 ответов
Под "идиоматическим" я предполагаю, что вы говорите о "Идиомах" Макбрайда и Патерсона в их статье " Прикладное программирование с эффектами".: О)
Вот как вы можете использовать их идиомы, чтобы проверить, заказана ли коллекция:
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 функтор, или "идиома", или "сильный слабый моноидальный функтор". Так уж получилось, что каждый Monoid индуцирует такую идиому бесплатно (см. раздел 4 статьи).
Моноид - это просто ассоциативная бинарная операция над каким-либо типом и элемент идентификации для этой операции. Я определяю Semigroup[Lte[A]] (полугруппа - это то же самое, что и моноид, но без элемента идентичности), ассоциативная операция которого отслеживает меньшее из двух значений и определяет, является ли левое значение меньшим, чем правое значение. И конечно Option[Lte[A]] это просто моноид, свободно генерируемый нашей полугруппой.
В заключение, foldMapDefault пересекает тип коллекции T в идиоме, вызванной моноидом. Результат b будет содержать значение true, если каждое значение было меньше, чем все последующие (это означает, что коллекция была упорядочена), или None если 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.
И вот как вы делаете идиоматический обход, чтобы определить, заказана ли коллекция.
Это выйдет после первого элемента, который вышел из строя. Таким образом, он должен работать хорошо, но я этого не проверял. Это также намного более изящно по моему мнению.:)
def sorted(l:List[Int]) = l.view.zip(l.tail).forall(x => x._1 <= x._2)
Я иду с этим, который довольно похож на Ким Стебель, на самом деле.
def isOrdered(list: List[Int]): Boolean = (
list
sliding 2
map {
case List(a, b) => () => a < b
}
forall (_())
)
В случае, если вы пропустили элегантное решение отсутствующего фактора в комментариях выше:
(l, l.tail).zipped.forall(_ <= _)
Это решение очень читабельно и будет выходить из первого вышедшего из строя элемента.
Рекурсивная версия хороша, но ограничена List (с ограниченными изменениями, это будет хорошо работать на LinearSeq).
Если бы это было реализовано в стандартной библиотеке (имело бы смысл), это, вероятно, было бы сделано в IterableLike и иметь полностью обязательную реализацию (см., например, метод find)
Вы можете прервать foldLeft с 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)}
Скорее, кратко, и, может быть, это можно назвать идиоматическим, я не уверен. Но я думаю, что это не слишком ясно. Более того, все эти методы, вероятно, будут работать намного хуже, чем императивная или хвостовая рекурсивная версия, и я не думаю, что у них есть какая-то дополнительная ясность, которая бы это купила.
Также вы должны взглянуть на этот вопрос.
Чтобы остановить итерацию, вы можете использовать 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
Если вы разделите Список на две части и убедитесь, что последняя из первой части меньше первой из второй части. Если это так, вы можете проверить параллельно для обеих частей. Вот схематическая идея, сначала без параллели:
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)
}
}
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.
Мое решение сочетается с решением недостающего фактора и упорядочением
def isSorted[T](l: Seq[T])(implicit ord: Ordering[T]) = (l, l.tail).zipped.forall(ord.lt(_, _))
и вы можете использовать свой собственный метод сравнения. Например
isSorted(dataList)(Ordering.by[Post, Date](_.lastUpdateTime))