scala - spark - Construcción idiomática para verificar si una colección está ordenada

foldleft spark

Question

Con la intención de aprender y profundizar en esta question , sigo sintiendo curiosidad por las alternativas idiomáticas a la recursión explícita para un algoritmo que verifica si se ordena una lista (o colección). (Estoy simplificando las cosas aquí usando un operador para comparar e Int como tipo; me gustaría ver el algoritmo antes de profundizar en los genéricos)

La versión recursiva básica sería (por @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)
}

Una forma idiomática deficiente sería:

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

Un algoritmo alternativo que usa 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

Tiene el inconveniente de que se comparará para todos los n elementos de la lista, incluso si pudiera detenerse antes después de encontrar el primer elemento fuera de servicio. ¿Hay alguna manera de "detener" el doblez y por lo tanto hacer de esta una mejor solución?

¿Alguna otra alternativa (elegante)?

Answer 1

En caso de que se haya perdido la solución elegante de missingfaktor en los comentarios above :

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

Esta solución es muy legible y saldrá en el primer elemento fuera de servicio.

Answer 2

Esto saldrá después del primer elemento que está fuera de servicio. Por lo tanto, debería funcionar bien, pero no he probado eso. También es mucho más elegante en mi opinión. :)

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

Answer 3

La versión recursiva está bien, pero limitada a List (con cambios limitados, funcionaría bien en LinearSeq ).

Si se implementó en la biblioteca estándar (tendría sentido), probablemente se haría en IterableLike y tendría una implementación completamente imperativa (ver, por ejemplo, el método find )

Puede interrumpir foldLeft con un return (en cuyo caso solo necesita el elemento anterior y no boolean todo el tiempo)

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
}

pero no veo cómo es mejor o incluso idiomático que una implementación imperativa. No estoy seguro de que no lo llamaría imperativo en realidad.

Otra solución podría ser

def isOrdered[A: Ordering](seq: Seq[A]): Boolean = 
  ! seq.sliding(2).exists{s => s.length == 2 && s(0) > s(1)}

Más bien conciso, y tal vez eso podría llamarse idiomático, no estoy seguro. Pero creo que no está muy claro. Además, todos estos métodos probablemente funcionarían mucho peor que la versión imperativa o recursiva de la cola, y no creo que tengan ninguna claridad adicional que pueda comprar eso.

También deberías echarle un vistazo a esta pregunta .

Answer 4

Me voy con esto, que es bastante similar al de Kim Stebel, como una cuestión de hecho.

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

Answer 5

Para detener la iteración, puede usar 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

Answer 6

Por "idiomático", supongo que estás hablando de "Idioms" de McBride y Paterson en su papel Applicative Programming With Effects . : o)

Así es como usaría sus expresiones idiomáticas para verificar si se ordena una colección:

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)

Así es como funciona esto:

Cualquier estructura de datos T[A] donde exista una implementación de Traverse[T] , puede atravesarse con un functor Applicative , o "modismo", o "functor monoidal débilmente laxo". Simplemente sucede que cada Monoid induce tal modismo de forma gratuita (ver la sección 4 del documento).

Un monoide es solo una operación binaria asociativa sobre algún tipo, y un elemento de identidad para esa operación. Estoy definiendo un Semigroup[Lte[A]] (un semigrupo es lo mismo que un monoide, excepto sin el elemento de identidad) cuya operación asociativa rastrea el menor de dos valores y si el valor de la izquierda es menor que el correcto. Y, por supuesto, la Option[Lte[A]] es solo el monoide generado libremente por nuestro semigrupo.

Finalmente, foldMapDefault atraviesa el tipo de colección T en el modismo inducido por el monoide. El resultado b contendrá verdadero si cada valor fue menor que todos los siguientes (es decir, se ordenó la colección), o None si la T no tenía elementos. Dado que una T vacía se ordena por convención, pasamos true como el segundo argumento al fold final de la Option .

Como beneficio adicional, esto funciona para todas las colecciones atravesables. Una demostración

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

Una prueba:

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.

Y así es como haces un recorrido idiomático para detectar si se ordena una colección.

Answer 7

Si divide la Lista en dos partes, y verifica si la última de la primera parte es más baja que la primera de la segunda parte. Si es así, puedes verificar en paralelo para ambas partes. Aquí la idea esquemática, primero sin paralelo:

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

Y ahora con paralelo, y usando splitAt lugar de 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) 
  }
}

Answer 8

mi solución se combina con la solución de missingfaktor y el pedido

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

y puedes usar tu propio método de comparación. P.ej

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

Answer 9

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.