maasg - 4 months ago 32

Scala Question

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?

Answer

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.