Какова наиболее эффективная функциональная версия следующего императивного кода?

Question

Я изучаю Scala и хочу узнать, как лучше всего выразить этот императивный паттерн с помощью функциональных возможностей программирования Scala.

def f(l: List[Int]): Boolean = {
  for (e <- l) {
    if (test(e))
      return true
    }
  }
  return false
}

Лучшее, что я могу придумать, это:

l map { e => test(e) } contains true

Но это менее эффективно, так как он вызывает test () для каждого элемента, тогда как императивная версия останавливается на первом элементе, который удовлетворяет test (). Есть ли более идиоматическая методика функционального программирования, которую я могу использовать для того же эффекта? В Scala императивная версия кажется неудобной.

Answer 1

Вы можете использовать существующий метод:

val listWithEvens = List(1,2,3,4)
val listWithoutEvens = List(1,3,5)
def test(e: Int) = e % 2 == 0

listWithEvens.exists(test(_)) // true
listWithoutEvens.exists(test(_)) // false

// alternative
listWithEvens.exists(_ % 2 == 0)  // true 

Если вы не знакомы с _ используемым таким образом, это эквивалентно:

listWithEvens.exists(v => v % 2 == 0)

Answer 2

Итак, вам нужен метод exists (l.exists(test)), который ничего не говорит о том, как вы бы реализовали его. Самая простая реализация не очень эффективна:

def f(l: List[Int]): Boolean = l.foldLeft(false)((flag, n) => flag || test(n))

Проблема в том, что он будет проходить через все l, даже если тестирование остановится, когда flag станет истинным. Теперь большинство функциональных методов итерации (на строгих языках) не прекратят итерацию, пока не завершат всю коллекцию. Те, которые действительно реализованы, в значительной степени реализованы так же, как и вы, так что, в конце концов, вы просто скрываете код такого рода, а не избегаете его.

Однако, если бы мне потребовалось использовать существующие методы и, конечно же, не использовать exists, и, кроме того, быть эффективным, можно сделать что-то вроде этого:

def f(l: List[Int]): Boolean = l.dropWhile(!test(_)).nonEmpty

Answer 3

Конечно, в этом случае нет необходимости (и я действительно ожидаю, что библиотека Scala будет использовать более императивную версию для своих exists - или, по крайней мере, будет map с явным break в ней ) но на List вы можете использовать простую (хвостовую) рекурсивную функцию.

import scala.annotation.tailrec

@tailrec
def exists(l: List[Int], p: (Int) => Boolean): Boolean = l match {
  case Nil => false
  case x :: xs => p(x) || exists(xs, p)
}

Поскольку || оценивает правую сторону только в том случае, если левая сторона равна false, это означает, что вы сломались раньше.

Это, конечно, эффективно, только если ссылка на хвост коллекции дешева.