以下命令式代码最有效的函数版本是什么？

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

您可以使用exists方法：

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 变为 true 测试就会停止。现在，大多数函数式迭代方法（在严格的语言中）在完成所有集合之前不会停止迭代。那些实际上的实现方式与您的实现方式非常相似，因此，最终您只是隐藏了此类代码，而不是避免它。

然而，如果我被要求使用现有的方法，当然，不使用 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，则 || 仅评估右侧，这意味着您会提前中断。

当然，只有当引用集合的尾部成本很低时，这才是有效的。