Scala: How do I use foldLeft with a generic array?

问题:

I've this method:

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
    val sorted = for (it <- as.sliding(2))
      yield {
        if (it.length == 2) ordered.apply(it(0), it(1))
        else true
      }

    sorted.find(!_).isEmpty
}

What I'd like to do is use foldLeftand apply the binary operator. However, foldLeft requires an initial value and I don't know what initial value I can provide without knowing the real type of A.

回答1:

I think what you're doing can be simplified.

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
  if (as.size < 2)
    true
  else
    as.sliding(2).find(x => !ordered(x(0),x(1))).isEmpty
}

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

scala> isSorted( Array(2), {(a:Int,b:Int) => a < b} )
res42: Boolean = true

scala> isSorted( Array(2,4), {(a:Int,b:Int) => a < b} )
res43: Boolean = true

scala> isSorted( Array(2,4,5), {(a:Int,b:Int) => a < b} )
res44: Boolean = true

scala> isSorted( Array(2,14,5), {(a:Int,b:Int) => a < b} )
res45: Boolean = false

Or, perhaps a little more concisely (but not necessarily easier to understand):

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
  if (as.size < 2)
    true
  else
    !as.sliding(2).exists(x => ordered(x(1),x(0)))
}

UPDATE

OK, I think I've got the concise prize nailed.

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean =
  as.isEmpty || as.init.corresponds(as.tail)(ordered)

回答2:

For initial value for foldLeft you could use head of your input array. However foldLeft is not a good choise to check if array is sorted, since you should terminate method when first unsorted element found but foldLeft will traverse whole array

Edit:

I would use the combination of zip with tail and exists:

isSorted(...) = 
   if (as.isEmpty) true
   else !as.zip(as.tail).exists { case (a,b) => !ordered(a,b)}

回答3:

Adding to the other answers, you probably do not want to iterate through the entire array, but rather terminate the moment you find an unordered pair. So, how about this?

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
  var sorted = true
  val ita = as.sliding(2)
  while (sorted && ita.hasNext) {
    val it = ita.next
    sorted = if (it.size > 1) ordered(it(0), it(1)) else true
  }
  sorted
}

val a = Array(1, 3, 2, 4, 5)
val b = Array(1, 2, 3, 4, 5)

isSorted[Int](a, _ < _) // returns false
isSorted[Int](b, _ < _) // returns true