I'm trying to solve the following problem and cannot find any solutions, could you please help with this:

Implement a higher order function that checks if an Array[A] is sorted given a comparison function as an argument:

def isSorted[A](as: Array[A], comparison: (A, A) => Boolean): Boolean

Ensure that your implementation is tail recursive, and use an appropriate annotation.

1. Example1:

   isSorted[Int](Array(1, 2, 3), (x, y) => x <= y)
   

   should be true

2. Example2:

   isSorted[Int](Array(2, 2, 2), (x, y) => x == y)
   

   should be true

3. Example3:

   isSorted[Int](Array(2, 2, 2), (x, y) => x < y)
   

   should be false

def isSorted[A](as: Array[A], comparison: (A, A) => Boolean): Boolean = {
  @scala.annotation.tailrec
  def iterator(as: Array[A], a: Int, b: Int): Boolean =
    if (as.size == 0 || as.size == 1)
      true
    else if (b   1 < as.size)
      if (comparison(as(a), as(b)))
        iterator(as, b, b   1) 
      else
        false
    else
      true

  iterator(as, 0, 1)
}

CodePudding user response：

1. How would you solve it without the extra constraints? You would have to check that

• For all indices i in the range 0 until arr.size - 1
• the condition comparison(arr(i), arr(i 1)) holds.

That is:

def isSorted[A](arr: Array[A])(cmp: (A, A) => Boolean) =
  (0 until (arr.size - 1)).forall(i => cmp(arr(i), arr(i   1)))

2. Now, where's the iteration/recursion hidden? It's inside of the forall method for the range. So, reimplement the forall on your own, obeying the constraints of the task:

def rangeForall(r: Range, p: Int => Boolean): Boolean = {
  @annotation.tailrec
  def rec(idx: Int): Boolean = 
    if (idx >= r.end) {
      true
    } else if (p(idx)) {
      rec(idx   1)
    } else {
      false
    }
  rec(r.start)
}

Note how it can be tested separately, and that it requires neither nested functions nor generics or anything like that.

Use that instead of the built-in forall:

def isSorted[A](as: Array[A])(cmp: (A, A) => Boolean) =
  rangeForall(0 until (as.size - 1), i => cmp(as(i), as(i   1)))

Sanity check:

println(isSorted(Array(1, 2, 3))(_ <= _)) // true
println(isSorted(Array(2, 2, 2))(_ == _)) // true
println(isSorted(Array(2, 2, 2))(_ < _)) // false

Note that the function signature has two argument lists: this is necessary so that the type parameter is inferred from the array only, before the type checker gets to the second argument list. In this way, you don't have to write out the [Int] every time.

CodePudding user response：

Short and sweet.

@annotation.tailrec
def isSorted[A](as: Seq[A], comparison: (A,A)=>Boolean): Boolean = as match {
  case Seq() => true
  case Seq(_) => true
  case a :b :z => if (comparison(a,b)) isSorted(b :z, comparison)
                  else false
}