In Scala what's a functional way to check that an array is monotonic?

Question

I have an array val x : Array[Double] and would like to check as precondition to a function that every x(i) <= x(i+1) for all i. What's the way to do it using functional programming in Scala. I looked for e.g. foldLeft or foldRight but they accumulate rather than visiting every pair of adjacent elements.

In Haskell, you'd `zip` a list with itself so that you get pairs of adjacent elements. Not sure if it's as elegant in Scala. — Bergi, Sep 06 '16 at 06:35
Why plain old "def isMonotonic(...)" with while loop inside is "unelegant"? One don't have to use those inefficient zips/sliding to be "functional". As long as your function is pure, it is OK. Practicality should be the goal, not "elegance". — dveim, Sep 06 '16 at 08:11
OK removed the elegant word .. I was interested in the functional form solution. The reason why functional is elegant to me is a personal thing perhaps but I guess has to do with better communication of intent = elegance — SkyWalker, Sep 06 '16 at 08:15
@Bergi `(vs, vs.view.drop(1)).zipped.forall(_ < _)`. The view just manages indexes, and `zipped` doesn't build anything. — som-snytt, Sep 06 '16 at 08:47

Nyavro · Accepted Answer · 2016-09-06T08:58:12.550

6

Consider this:

def isMonotonic(arr:Array[Int]) = 
   if (arr.isEmpty) true
   else (arr, arr.tail).zipped.forall {case (a,b) => a <= b}

Simplified solution (thanks to @som-snytt):

def isMonotonic(arr:Array[Int]) = 
   (arr, arr.drop(1)).zipped.forall (_ <= _)

edited Sep 06 '16 at 08:58

answered Sep 06 '16 at 06:34

Nyavro

8,806
2
26
33

2

Avoid intermediate collections: `(vs, vs.view.drop(1)).zipped.forall(_ < _)`. – som-snytt Sep 06 '16 at 08:35
Is vs.view.drop(1) equivalent to vs.view.tail? I would prefer the second one – Nyavro Sep 06 '16 at 08:47
Then solution became even more simple, thanks @som-snytt! – Nyavro Sep 06 '16 at 08:59

Yuval Itzchakov · Answer 2 · 2016-09-06T09:18:55.300

4

You can use IterableLike.sliding:

val isMonotonic = 
  Seq(1,2,3,4,5).sliding(2).forall {
    case Seq(x, y) => x < y
    case _ => true
  }

Edit:

Since you're using an Array[Double], you'll need:

val isMonotonic = 
  Array(1d, 2d, 3d, 4d, 5d).sliding(2).forall {
    case Array(x, y) => x < y
    case _ => true
  }

edited Sep 06 '16 at 09:18

answered Sep 06 '16 at 06:34

Yuval Itzchakov

146,575
32
257
321

Maybe rather `case x::y::_`? – Bergi Sep 06 '16 at 06:36
@Bergi Definitely, much more elegant. – Yuval Itzchakov Sep 06 '16 at 06:37
`::_` ? How would that happen? – jwvh Sep 06 '16 at 06:38
@jwvh It would just ignore the tail of the list if it exists, wouldn't it? I see it working in the REPL. – Yuval Itzchakov Sep 06 '16 at 06:39
But that's my question. How could there be any tail? How could there be anything to ignore? – jwvh Sep 06 '16 at 06:40
Nice solution, but you have to process case when Set contains less than 2 items – Nyavro Sep 06 '16 at 06:41
@jwvh It ignores the empty list. I guess one could equally have written `case List(x, y)` – Bergi Sep 06 '16 at 06:42
@Bergi, my point exactly. I think your `List()` suggestion is cleaner and easier to read/understand. – jwvh Sep 06 '16 at 06:44
@jwvh Added it as an additional solution. – Yuval Itzchakov Sep 06 '16 at 06:47
@Nyavro In that case, the iterator doesn't contain any elements (if I interpret [the docs](http://www.scala-lang.org/api/2.11.1/index.html#scala.collection.IterableLike) correctly) and `forAll` would yield `true` – Bergi Sep 06 '16 at 06:49
The problem is in match statement. You should add case _. Try to run on Seq(1) – Nyavro Sep 06 '16 at 06:53
@Bergi He's right. In case the sequence has a single element it blows on the match. – Yuval Itzchakov Sep 06 '16 at 06:56
When I plugin my `val x: Array[Double]` I get the following error `constructor cannot be instantiated to expected type; found : scala.collection.immutable.::[B] required: Array[Double]` – SkyWalker Sep 06 '16 at 07:04
@GiovanniAzua I've added a case for arrays. – Yuval Itzchakov Sep 06 '16 at 07:25
@som-snytt Can you elaborate why using array extractor is bad? – Yuval Itzchakov Sep 06 '16 at 08:45
@som-snytt I tested it in the REPL. – Yuval Itzchakov Sep 06 '16 at 08:54
@som-snytt [No, I don't.](https://gist.github.com/YuvalItzchakov/8922636e2fa8b5b0e060fb6f69adbd0e). This is running Scala 2.11.8 – Yuval Itzchakov Sep 06 '16 at 08:57
@som-snytt I also see [other examples](http://stackoverflow.com/questions/6647166/how-do-i-pattern-match-arrays-in-scala) doing exactly that same? – Yuval Itzchakov Sep 06 '16 at 08:58

score 1 · Answer 3 · answered Sep 06 '16 at 09:16

With a couple of fine answers to choose from, the next question is: Can we make it generic?

This is my shot at it.

def isMonotonic[T](ts: Traversable[T])(implicit ev: Ordering[T]): Boolean = {
  if (ts.size < 2) true
  else if (ev.gt(ts.head, ts.tail.head)) false
  else isMonotonic(ts.tail)
}

Appears to work for the following.

isMonotonic(Array('c','a','z'))             // false
isMonotonic(Vector(3.1, 2.2, 7.7))          // false
isMonotonic(List[Int]())                    // true
isMonotonic(Seq("abc", "bcb", "tz", "xs"))  // true

score 1 · Answer 4 · answered Sep 06 '16 at 10:12

A slightly different approach

def isMonotonic(xs:List[Int]) = xs.sliding(2)
                                  .collectFirst{case List(x,y) if x > y => 1}
                                  .isEmpty

Works on empty and length-one lists because the partial function is never defined on those. Because it's collectFirst, it bails at the first evidence it's not monotonic The xs zip xs.drop(1) idea can be used if preferred

In Scala what's a functional way to check that an array is monotonic?

4 Answers4

Edit: