List foldRight Always Using foldLeft?

问题:

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))

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

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

回答1:

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.

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.