Idiomatische Konstruktion, um zu überprüfen, ob eine Sammlung ist bestellt

Durch "Redewendungen", ich nehme an, du redest McBride und Paterson "Idiome" in Ihrem Papier Applicative Programmierung Mit Effekten. :o)

Hier ist, wie Sie verwenden würden, Ihre Idiome zu prüfen, ob eine Sammlung ist bestellt:

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)

Hier ist, wie das funktioniert:

Jede Datenstruktur T[A] wo es existiert eine Implementierung von Traverse[T], können befahren werden, die mit einem Applicative Funktor, oder "idiom", oder "stark lax monoidale functor". Es passiert einfach so, dass jeder Monoid induziert eine solche Ausdrucksweise ist für Sie kostenlos (siehe Abschnitt 4 des Papiers).

Ein monoid ist nur eine assoziative binäre operation über einige Typ, und eine identity-element für die Bedienung. Ich bin die Definition einer Semigroup[Lte[A]] (eine halbgruppe ist dasselbe wie ein monoid, außer ohne die identity-element), dessen assoziative operation tracks der geringere der beiden Werte, und ob der linke Wert kleiner als der Rechte Wert. Und natürlich Option[Lte[A]] ist genau das monoid erzeugt, frei von unseren halbgruppe.

Schließlich foldMapDefault durchläuft die Auflistung Typ T in der Sprache, die durch die monoid. Das Ergebnis b enthält true, wenn jeder Wert war kleiner als alle folgenden (im Sinne der Sammlung bestellt wurde), oder None wenn die T hatte keine Elemente. Da eine leere T sortiert ist, durch Konvention, passieren wir true als zweites argument an die Letzte fold des Option.

Als bonus, das funktioniert für alle passierbar Sammlungen. Eine demo:

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

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.

Und das ist, wie Sie idiomatische traversal zu erkennen, ob eine Sammlung bestellt ist.

Ich werde mit dieser Option, die ist ziemlich ähnlich zu Kim Stebel ist, als eine Angelegenheit von Tatsache.

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

Die rekursive version ist in Ordnung, aber beschränkt auf List (mit begrenzten änderungen, es würde funktionieren gut auf LinearSeq).

Wenn es umgesetzt wurde in der standard-Bibliothek (würde Sinn machen), würde es wohl getan werden in IterableLike und haben eine völlig unerlässlich für die Umsetzung (siehe zum Beispiel Methode find)

Können Sie unterbrechen den foldLeft mit einem return (in diesem Fall benötigen Sie nur den vorhergehenden element und nicht boolean alle zusammen)

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
}

aber ich weiß nicht, wie es besser ist oder sogar idiomatische als ein Imperativ Umsetzung. Ich bin mir nicht sicher, ich würde nicht nennen es zwingend notwendig eigentlich.

Andere Lösung könnte sein,

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

Eher knapp, und vielleicht könnte sein genannt Redewendungen, bin ich mir nicht sicher. Aber ich denke, es ist nicht allzu klar. Außerdem, alle diese Methoden würden wahrscheinlich viel schlimmer als die Imperativ-oder tail-rekursive version, und ich glaube nicht, Sie haben keine zusätzlichen Klarheit, die würden es kaufen.

Außerdem sollten Sie einen Blick auf diese Frage.

Wenn Sie teilen die Liste in zwei Teile, und prüfen, ob der Letzte der erste Teil ist kleiner als der erste des zweiten Teils. Wenn dem so ist, könnte man check-in parallel für beide Teile. Hier der Schaltplan, Idee, erstmal ohne parallele:

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

Und jetzt mit parallel-und mit splitAt statt 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) 
  }
}

meine Lösung kombinieren mit missingfaktor Lösung und Bestellung

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

und Sie können Ihre eigenen Vergleich Methode. E. g.

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