Write isSorted
, which checks whether an Array[A]
is sorted
according to a given comparison function cmp(A,A) => Boolean
.
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)
}
Students looking for an answer to this exercise may find this: fpinscala/answerkey/02.answer.md
There two problems with the linked code:
-
The comparison is inverted. Notice the use of
!
in the correct code above, so that the function returnsfalse
if the comparison fails for any pair of successive elements. -
The comparison function is named
gt
, which implies that the semantics of the function are "greater-than", i.e.,gt(x,y)
will returntrue
iffx > y
. But the semantics of the comparsion function are up to the caller. The function should be given an unopinionated name, such ascmp
(for "compare"), as in the correct code given above.
See also: isSorted not as expected