Idiomatic construction to check whether a collection is ordered

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 1

This will exit after the first element that is out of order. It should thus perform well, but I haven't tested that. It's also a lot more elegant in my opinion. :)

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