确定列表成员资格的函数

Function to determine membership in a list

我需要编写一个包含函数的程序 doesExist: [A](p:A => Boolean) (xs: List[A]) Boolean.

例如doesExist ((x:Int) => x==2) (List(5,1,2,3)) => true

它应该 return true 或 false 取决于是否在列表中找到该元素。

简单地说:

def doesExist[A](p:A => Boolean)(xs: List[A]) = xs.exists(p)

如果不能使用exists:

def doesExist[A](p:A => Boolean)(xs: List[A]) =
  xs.fold(false)((alreadyFound, a) => alreadyFound || p(a))

我想它的要点是不使用列表的内置函数...所以这里有一个使用 foldLeft 的替代方法:

def doesExist[A](p: A => Boolean)(xs: List[A]): Boolean = {
    xs.foldLeft(false)((acc, elem) => acc || p(elem))
}

练习模式匹配可能是一个很好的练习:

def doesExist[A](p:A => Boolean)(xs: List[A]): Boolean = xs match {
    case Nil => false
    case head :: tail => p(head) || doesExist(p)(tail)
}

Scala 2.11.8 标准库是这样做的。

来自LinearSeqOptimized.scala

  override /*IterableLike*/
  def exists(p: A => Boolean): Boolean = {
    var these = this                      // <--- Look, a var!
    while (!these.isEmpty) {
      if (p(these.head)) return true      // <--- Look, a return!
      these = these.tail
    }
    false
  }

换句话说,Scala 使用 while 循环,它会改变指向下一个对象的 var,并在到达所需对象时跳出循环。

我发现,当 comparing answers 回答类似问题时,while 带有某种变异迭代变量是在 Scala 中编写此代码的最有效方法。递归、Streams 等纯函数方法速度较慢——慢了 8 倍(并且仍然没有扫描超过第一个 'true' 元素)。我认为最好的方法是在需要进行线性搜索时使用某种可变迭代器并将其隐藏在一个函数中,该函数为程序的其余部分提供纯函数接口。 Scala 标准库在许多地方为您做到了这一点,因此您可以通过纯函数式接口获得最佳性能。