Идиоматическая конструкция, чтобы проверить, заказана ли коллекция

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

Альтернативный алгоритм, использующий сложение:

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

Под «идиоматическим» я предполагаю, что вы говорите о «Идиомах» Макбрайда и Патерсона в их статье Прикладное программирование с эффектами . : О)

Вот как бы вы использовали их идиомы для проверки упорядоченности коллекции:

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.

И это как вы делаете идиоматический обход, чтобы определить, заказана ли коллекция.

Answer 3

Я пойду с этим, который на самом деле очень похож на Ким Стебель.

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

Answer 4

В случае, если вы пропустили элегантное решение отсутствующего фактора в комментариях выше :

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

Это решение очень читабельно и будет выходить из первого вышедшего из строя элемента.

Answer 5

Рекурсивная версия хороша, но ограничена 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)}

Скорее, кратким, и, возможно, это можно назвать идиоматическим, я не уверен.Но я думаю, что это не слишком ясно.Более того, все эти методы, вероятно, будут работать намного хуже, чем императивная или хвостовая рекурсивная версия, и я не думаю, что у них есть какая-то дополнительная ясность, которая бы это купила.

Также вам стоит взглянуть на этот вопрос .

Answer 6

Чтобы остановить итерацию, вы можете использовать Итерация :

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

Answer 7

мое решение в сочетании с решением отсутствующего фактора и Ordering

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

, и вы можете использовать свой собственный метод сравнения.Например,

isSorted(dataList)(Ordering.by[Post, Date](_.lastUpdateTime))

Answer 8

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. 

Answer 9

Если вы разделите Список на две части и проверьте, будет ли последняя из первой части ниже первой из второй части.Если это так, вы можете проверить параллельно для обеих частей.Вот схематическая идея, сначала без параллели:

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) 
  }
}