Construction idiomatique pour vérifier si une collection est commandée

Question

Avec l'intention de l'apprentissage et à la suite de cette question, j'ai resté curieux de la idiomatiques alternatives à la récursion explicite à un algorithme qui vérifie si une liste (ou de la collection) est commandée. (Je vais garder les choses simples ici à l'aide d'un opérateur de les comparer et de les Int type; je voudrais regarder l'algorithme avant de plonger dans les génériques de celui-ci)

La base une version récursive serait (par @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)
}

Une mauvaise exécution idiomatiques serait:

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

Un algorithme de remplacement à l'aide de pli:

def isOrdered(l: List[Int]) =
  l.foldLeft((true, None:Option[Int]))((x,y) =>
    (x._1 && x._2.map(_ <= y).getOrElse(true), Some(y)))._1

Il a l'inconvénient qu'il va comparer pour tous les n éléments de la liste, même s'il pouvait s'arrêter plus tôt après avoir trouvé la première de l'élément. Est-il un moyen de "s'arrêter" pli et, par conséquent, ce qui en fait une meilleure solution?

Tout autre (élégant) les solutions de rechange?

Answer 1

Cela se terminera après le premier élément en panne. Il devrait donc bien fonctionner, mais je ne l'ai pas testé. C'est aussi beaucoup plus élégant à mon avis. :)

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

Answer 2

Par "idiomatiques", je suppose que vous parlez de McBride et Paterson "Idiomes" dans leur document de Programmation Applicative Avec des Effets. :o)

Voici comment vous pouvez l'utiliser leurs idiomes de vérifier si une collection est ordonné:

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)

Voici comment cela fonctionne:

Une structure de données T[A] où il existe une mise en œuvre de l' Traverse[T], peut être parcouru avec un Applicative foncteur, ou "idiome", ou "fort lax monoidal foncteur". Il se trouve que chaque Monoid génère un tel idiome pour gratuit, implicitement.

Un monoïde est juste une associatif opération binaire sur un certain type, et un élément de l'identité de cette opération. Je suis à la définition d'un Semigroup (qui est le même comme un monoïde, à l'exception sans que l'identité de l'élément) dont associatif fonctionnement suit le moindre de deux valeurs et si la gauche de la valeur est inférieure à la juste valeur. Et bien sûr, Option[Lte[A]] est juste le monoïde généré gratuitement par nos semigroup.

Enfin, foldMapDefault traverse nos T dans l'idiome généré par le monoïde. Le résultat b contiendra vrai si chaque valeur est inférieure à toutes les suivantes (ce qui signifie la collection a été commandées), et un vide T est classée par la convention, de sorte que nous passons true que le second argument de la finale fold de la Option.

Une démo:

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

Un test:

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.

Et c'est comment vous le faites idiomatiques de la traversée de détecter si une collection est ordonnée.

Answer 3

Je vais avec ceci, qui est assez similaire à celui de Kim Stebel, en fait.

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

Answer 4

Une version récursive est très bien, mais est limitée à List (avec les modifications limitées, il serait bien travailler sur LinearSeq).

Si il a été mis en œuvre dans la bibliothèque standard (du sens), il serait probablement faire dans IterableLike et ont complètement impératif de mise en œuvre (voir par exemple la méthode de find)

Vous pouvez interrompre l' foldLeft avec un return (dans ce cas, vous avez besoin seulement de l'élément précédent, et non booléen tout le long)

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
}

mais je ne vois pas en quoi c'est mieux ou même idiomatiques qu'un impératif de mise en œuvre. Je ne suis pas sûr que je ne dirais pas qu'il est impératif de fait.

Une autre solution pourrait être

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

Plutôt concis, et peut-être que l'on pourrait appeler idiomatiques, je ne suis pas sûr. Mais je pense qu'il n'est pas trop clair. En outre, l'ensemble de ces méthodes serait probablement faire bien pire que de l'impératif ou de queue, une version récursive, et je ne pense pas qu'ils ont tous plus de clarté qui permettrait de les acheter.

Aussi, vous devriez jeter un oeil à cette question.

Answer 5

Pour arrêter l'itération, vous pouvez utiliser 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