Scala: как использовать foldLeft с общим массивом?

У меня есть этот метод:

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
}

Что я хотел бы сделать, так это использовать foldLeft и применить бинарный оператор. Однако foldLeft требует начального значения, и я не знаю, какое начальное значение я могу предоставить, не зная реального типа A.


arrays generics scala foldleft
person Abhijit Sarkar    schedule 23.01.2016    source источник
comment
Взгляните на это: stackoverflow.com/a/7852918/1153435   -  person Eduardo    schedule 23.01.2016
comment
@ Эдуардо уже сделал. В этой ветке нет единого мнения, что делать для взлома. Некоторые говорят, что break — это лучшее, что есть в Scala после нарезки хлеба, другие считают, что это зло, поскольку под капотом генерируется исключение.   -  person Abhijit Sarkar    schedule 23.01.2016
comment
Вы пробовали reduceLeft?   -  person Jus12    schedule 23.01.2016
comment
@ Jus12 да, и это не работает. Подписи не совпадают. reduceLeft[B >: A](op: (B, T) => B): B, в моем случае бинарная операция (A, A) => Boolean   -  person Abhijit Sarkar    schedule 23.01.2016
comment
Да, я думаю, что единственный способ сделать эту подпись правильной — это использовать что-то вроде aggregate(true)((b,x) => b && ordered(x(0),x(1)), (_ && _)).   -  person jwvh    schedule 23.01.2016

Ответы (3)


arrow_upward
2
arrow_downward

Я думаю, то, что вы делаете, можно упростить.

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

Или, возможно, немного более лаконично (но не обязательно легче для понимания):

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)))
}

ОБНОВЛЕНИЕ

Хорошо, я думаю, что у меня есть краткий приз прибит.

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean =
  as.isEmpty || as.init.corresponds(as.tail)(ordered)
person jwvh    schedule 23.01.2016
comment
Говоря о лаконичности и лени, и о заимствовании вашей идеи, я мог бы сделать - (as.isEmpty) || as.view.sliding(2).find(it => !ordered(it(0), it(1))).isEmpty - person Abhijit Sarkar; 23.01.2016
comment
Да, действительно, хотя тест isEmpty пропустит одноэлементный массив. - person jwvh; 23.01.2016
comment
Тьфу да, я хотел использовать as.size < 2, но каким-то образом получил isEmpty. - person Abhijit Sarkar; 23.01.2016
comment
Знаете, после просмотра я не уверен, что view приносит много пользы. sliding() создает итератор. Действительно ли перебор представления лучше/быстрее? - person jwvh; 23.01.2016
comment
Нет, это не так, и использование представления, как в моем комментарии, фактически приводит к ошибке SI-6709. . Итератор в порядке, или мне нужно использовать as.toIndexedSeq.view.sliding. Хороший улов. - person Abhijit Sarkar; 23.01.2016
comment
find работает лениво? (или он все еще перебирает весь массив?) - person Jus12; 23.01.2016
comment
Многие методы сбора данных, возвращающие логическое значение или Option использовать ленивый алгоритм или алгоритм раннего завершения. - person jwvh; 23.01.2016

arrow_upward
1
arrow_downward

Для начального значения для foldLeft вы можете использовать заголовок вашего входного массива. Однако foldLeft не является хорошим выбором для проверки того, отсортирован ли массив, поскольку вы должны завершить метод, когда будет найден первый несортированный элемент, но foldLeft будет проходить весь массив

Изменить:

Я бы использовал комбинацию zip с хвостом и существует:

isSorted(...) = 
   if (as.isEmpty) true
   else !as.zip(as.tail).exists { case (a,b) => !ordered(a,b)}
person Nyavro    schedule 23.01.2016
comment
Я не могу использовать голову, если массив пуст. Если мне нужно поставить if-else, я пишу больше кода. Что касается обхода, что вы предлагаете использовать? - person Abhijit Sarkar; 23.01.2016
comment
И я ищу более лаконичное решение, отсюда и вопрос. - person Abhijit Sarkar; 23.01.2016
comment
zip ленивый? В противном случае это решение является кратким, но все же проходит через весь массив. - person Abhijit Sarkar; 23.01.2016
comment
Хорошая точка зрения. zip тут не ленивый, так что view нужно применять перед заархивированием - person Nyavro; 23.01.2016
comment
Спасибо. Я проголосовал за ваш ответ, но принял ответ @jwvh, потому что он основан на моем исходном решении. - person Abhijit Sarkar; 23.01.2016

arrow_upward
1
arrow_downward

Добавляя к другим ответам, вы, вероятно, не хотите перебирать весь массив, а завершаете работу в тот момент, когда находите неупорядоченную пару. Итак, как насчет этого?

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
person Jus12    schedule 23.01.2016