Check if two adjoined elements are ordered using reduceLeft

user_15436170 0
Viewed 106

I have an exercise to check if two adjoined elements are ordered using sliding,map,reduceLeft. For example:

val seq1 = Seq(1,2,2,4)
isOrdered(seq1)(_ < _) == false
isOrdered(seq1)(_ <= _) == true


def isOrdered[A](seq: Seq[A])(leq: (A,A) => Boolean): Boolean = { 

}

honestly I don't know what to start with.

scala functional-programming
3 Answers

"using sliding,map,reduce"

def isOrdered[A](seq: Seq[A])(pred: (A,A) => Boolean): Boolean =
  seq.sliding(2)
     .map{case Seq(a,b) => pred(a,b)}
     .reduce(_ && _)

Note: Not safe for sequences smaller than 2 elements.

user_49931280

One approach includes forall, where leq: (A,A) => Boolean must hold for each and every element,

def isOrdered[A](seq: Seq[A])(leq: (A,A) => Boolean): Boolean = {
  seq.sliding(2).forall { case(Seq(l,r)) => leq(l,r) }
}

Thus for val seq1 = Seq(1,2,2,4),

scala> isOrdered(seq1)(_<_)
val res5: Boolean = false

scala> isOrdered(seq1)(_<=_)
val res6: Boolean = true
user_133906730

Here's how you can do it using those three operations:

def isOrdered[A](seq: Seq[A])(leq: (A, A) => Boolean): Boolean =
  seq
    .sliding(2)
    .map { case e1 :: e2 :: Nil => leq(e1, e2) }
    .reduceLeft(_ && _)

First we divide the sequence into groups of two consecutive elements using sliding. Then we apply leq on each pair (in other words, we map each two-element list into result of leq on those two elements). Lastly, we reduce the result sequence of Booleans into a single Boolean with a logical AND, meaning that our predicate needs to hold for all values.

val seq1 = Seq(1, 2, 2, 4)

val less: (Int, Int) => Boolean = _ < _
val lessOrEqual: (Int, Int) => Boolean = _ <= _

isOrdered(seq1)(less) // false
isOrdered(seq1)(lessOrEqual) // true

There are some unsafety concerns here:

  1. If you have a one-element sequence, the sliding operation will produce an iterator over a single-list element, and the pattern matching will fail.
  2. If you have an empty sequence, reduce will explode.
user_55992980
Related