maasg - 1 year ago 88
Scala Question

# Idiomatic construction to check whether a collection is ordered

With the intention of learning and further to this question, I've remained curious of the idiomatic alternatives to explicit recursion for an algorithm that checks whether a list (or collection) is ordered. (I'm keeping things simple here by using an operator to compare and Int as type; I'd like to look at the algorithm before delving into the generics of it)

The basic recursive version would be (by @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)
}
``````

A poor performing idiomatic way would be:

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

An alternative algorithm using 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
``````

It has the drawback that it will compare for all n elements of the list even if it could stop earlier after finding the first out-of-order element. Is there a way to "stop" fold and therefore making this a better solution?

Any other (elegant) alternatives?

By "idiomatic", I assume you're talking about McBride and Paterson's "Idioms" in their paper Applicative Programming With Effects. :o)

Here's how you would use their idioms to check if a collection is ordered:

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

Here's how this works:

Any data structure `T[A]` where there exists an implementation of `Traverse[T]`, can be traversed with an `Applicative` functor, or "idiom", or "strong lax monoidal functor". It just so happens that every `Monoid` induces such an idiom for free (see section 4 of the paper).

A monoid is just an associative binary operation over some type, and an identity element for that operation. I'm defining a `Semigroup[Lte[A]]` (a semigroup is the same as a monoid, except without the identity element) whose associative operation tracks the lesser of two values and whether the left value is less than the right value. And of course `Option[Lte[A]]` is just the monoid generated freely by our semigroup.

Finally, `foldMapDefault` traverses the collection type `T` in the idiom induced by the monoid. The result `b` will contain true if each value was less than all the following ones (meaning the collection was ordered), or `None` if the `T` had no elements. Since an empty `T` is sorted by convention, we pass `true` as the second argument to the final `fold` of the `Option`.

As a bonus, this works for all traversable collections. A 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
``````

A 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.
``````

And that's how you do idiomatic traversal to detect if a collection is ordered.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download