列表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和反转结果,它将在整个列表中涉及更少的完整迭代.