scala - 列出foldRight总是使用foldLeft吗？

Question

我只是看了List.scala对foldRight()的实现。

  override def reverse: List[A] = {
    var result: List[A] = Nil
    var these = this
    while (!these.isEmpty) {
      result = these.head :: result
      these = these.tail
    }
    result
  }

  override def foldRight[B](z: B)(op: (A, B) => B): B =
    reverse.foldLeft(z)((right, left) => op(left, right))

据我了解，在 foldRight上调用 List会导致在调用 theList.reverse.foldLeft(...)。

是否使用 List.foldRight实现 foldLeft以便利用单个堆栈框架而不是将多个堆栈框架与 foldLeft一起使用？

Answer 1

foldLeft是尾递归的，reverse根本不是递归的:此实现可确保恒定的内存使用率。 foldRight如果未按照foldLeft实现，则不是尾部递归的，这使得它对大量数据不安全。

注意:也许有一些方法可以使foldRight尾递归，但是我能想到的所有方法都需要在列表的末尾附加内容，这意味着要遍历整个列表。如果您仍然要这样做，最好使用foldLeft并反转结果，这将减少整个列表中的完整迭代次数。