列出 foldRight 总是使用 foldLeft? [英] List foldRight Always Using foldLeft?

问题描述

我刚刚查看了 列表.scala 对 foldRight() 的实现.

I just looked at the List.scala’s implementation of 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))

据我所知，在 List 上调用 foldRight 会导致调用 theList.reverse.foldLeft(...).

As I understand it, calling foldRight on a List results in calling theList.reverse.foldLeft(...).

List.foldRight 是否与 foldLeft 一起实现，以便利用单个堆栈帧而不是通过 foldLeft 使用多个堆栈帧?

Is List.foldRight implemented with foldLeft in order to take advantage a single stack frame rather than using multiple stack frames with foldLeft?

推荐答案

foldLeft 是尾递归的，reverse 根本不是递归的:这个实现确保了恒定的内存用法.foldRight，当没有按照 foldLeft 实现时，不是尾递归的，这使得它对大量数据不安全.

foldLeft is tail-recursive, reverse isn't recursive at all: this implementation ensures constant memory usage. foldRight, when not implemented in terms of foldLeft, isn't tail-recursive, which makes it unsafe for large amounts of data.

注意:可能有一些方法可以使 foldRight 尾递归，但我能想到的所有方法都需要在列表的末尾追加内容，这意味着要完全遍历它.如果您无论如何都要这样做，最好使用 foldLeft 并反转结果，它涉及的整个列表的完整迭代要少得多.

Note: there might be ways to make foldRight tail-recursive, but all those I can think of need to append things at the end of a list, which means traverse it in its entirety. If you're going to do that anyway, better use foldLeft and reverse the result, it involves far fewer full iterations on the whole list.

这篇关于列出 foldRight 总是使用 foldLeft?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！