Functional Programming in Scala: Chapter 2, Exercise 2: isSorted

fpscala-02-02.md

Functional Programming in Scala: Chapter 2, Exercise 2

Problem Statement

Write isSorted, which checks whether an Array[A] is sorted according to a given comparison function cmp(A,A) => Boolean.

Solution

The comparison function must evaluate to true for successive elements of the array.

isSorted(Array(a,b,c,d),cmp) ≡ cmp(a,b) && cmp(b,c) && cmp(c,d)

One way to picture the semantics is to imagine cmp as a mathematical infix operator #. This operator is interpolated between successive elements of the array:

isSorted(Array(a,b,c,d),#) ≡ a # b # c # d

So the usual ascending sort with "less-than-or-equal" is: a ≤ b ≤ c ≤ d.

def isSorted[A](as: Array[A], cmp: (A,A) => Boolean): Boolean = {
  @annotation.tailrec
  def go(n: Int): Boolean = {
    if n+1 >= as.length then true
    else if !cmp(as(n), as(n+1)) then false
    else go(n+1)
  }
  go(0)
}

Code Review

Students looking for an answer to this exercise may find this: fpinscala/answerkey/02.answer.md

There two problems with the linked code:

1. The comparison is inverted. Notice the use of ! in the correct code above, so that the function returns false if the comparison fails for any pair of successive elements.

2. The comparison function is named gt, which implies that the semantics of the function are "greater-than", i.e., gt(x,y) will return true iff x > y. But the semantics of the comparsion function are up to the caller. The function should be given an unopinionated name, such as cmp (for "compare"), as in the correct code given above.

See also: isSorted not as expected