列表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并反转结果，它涉及到的整个列表中的完整迭代要少得多。