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

Ответ 1

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

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

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.

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

Ответ 2

Это выйдет после первого элемента, который вышел из строя. Поэтому он должен хорошо работать, но я не проверял это. На мой взгляд, это также намного элегантнее.:)

def sorted(l:List[Int]) = l.view.zip(l.tail).forall(x => x._1 <= x._2)

Ответ 3

Я собираюсь с этим, что на самом деле похоже на Ким Стебеля.

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

Ответ 4

Если вы пропустили элегантное решение missingfaktor в комментариях выше:

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

Это решение очень читаемо и выйдет из первого элемента вне порядка.

Ответ 5

Рекурсивная версия в порядке, но ограничена List (с ограниченными изменениями она будет хорошо работать на LinearSeq).

Если бы он был реализован в стандартной библиотеке (имел бы смысл), это, вероятно, было бы сделано в IterableLike и иметь полностью императивную реализацию (см. пример метода find)

Вы можете прервать foldLeft с помощью return (в этом случае вам нужен только предыдущий элемент, а не boolean).

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

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

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

Ответ 6

Чтобы остановить итерацию, вы можете использовать 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] = [email protected]

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

scala> s(List(1,2,3,0)).run
res12: Boolean = false

Ответ 7

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

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

Ответ 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. 

Ответ 9

мое решение объединяется с решением missingfaktor и 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))