为什么foldRight和reduceRight不是尾递归？

Question

为什么编译器不能翻译Scala

(1,2,3,4,5,6).foldRight(10)(_ * _)

与Java等效

final int[] intArray = new int[]{1,2,3,4,5,6};
int accumulator = 10;

for(int i = intArray.legth - 1; i >=0; i--) {
  accumulator = intArray[i] * accumulator;
}

问题是:为什么foldLeft和reduceLeft是尾递归的,但它们的右对手不是？

这里有链接说右手不是尾递归.我在问为什么会这样.

你怎么知道何时使用fold-left以及何时使用fold-right？

foldr与foldl(或foldl')的含义

http://programming-scala.labs.oreilly.com/ch08.html

Answer 1

这是折叠如何进行的问题.该foldLeft操作整理

Seq(1, 2, 3).foldLeft(10)(_ - _)

如

(((10 - 1) - 2) - 3)

(foldRight安排时)(即4)

Seq(1, 2, 3).foldRight(10)(_ - _)

如

(1 - (2 - (3 - 10)))

(这是-8).

现在,想象一下你是从袋子里拿出数字1,2和3,然后用铅笔在纸上进行计算.

在foldRight情况下,你不得不做这样的:

1. 从袋子里拉出一个数字n
2. 写" n - ？" 在纸上
3. 如果包里还有号码,请从包中取出另一个n,否则转到6.
4. 删除问号并将其替换为"(n - ？)"
5. 重复3.
6. 擦除问号并将其替换为10
7. 执行计算

在这种foldLeft情况下,您可以这样做:

1. 在纸上写10
2. 如果包里还有号码,请从包中取出另一个n,否则转到5.
3. 在你已有的表达式旁边写上" - n "
4. 重复2.
5. 执行计算

但你不会,因为你也可以这样做:

1. 在纸上写10
2. 从袋子里拉出一个数字n
3. 从您拥有的值中减去n,删除该值并记下新值
4. 重复2.

无论袋子里有多少个数字,你只需要在纸上写下一个值.尾部呼叫消除(TCE)意味着不是在堆栈上构建大型递归调用结构,而是可以随时弹出并替换累积值.(即,递归表达的计算基本上以迭代方式执行.)

正如其他人所指出的那样,诸如a之类的随机访问结构ArrayLike允许将foldRight其重新排列为foldLeft操作,因此符合TCE条件.以上描述适用于不可能的情况.

Answer 2

(1, 2, 3, 4, 5, 6)是一个6值元组,没有foldRight,但Array(1, 2, 3, 4, 5, 6)确实如此.

ArrayLike是一个特征子类化索引序列与有效元素访问,这意味着它有一些优化的方法,包括例如foldRight.每个数组都隐式转换为特征的子类ArrayLike.来自Scala主干:

  @tailrec
  private def foldr[B](start: Int, end: Int, z: B, op: (A, B) => B): B =
    if (start == end) z
    else foldr(start, end - 1, op(this(end - 1), z), op)

字节码:

private static java.lang.Object foldr(scala.collection.IndexedSeqOptimized, int, int, java.lang.Object, scala.Function2);

...

  Code:
   Stack=6, Locals=6, Args_size=5
   0:   iload_1
   1:   iload_2
   2:   if_icmpne   7
   5:   aload_3
   6:   areturn
   7:   aload_0
   8:   iload_2
   9:   iconst_1
   10:  isub
   11:  aload   4
   13:  aload_0
   14:  iload_2
   15:  iconst_1
   16:  isub
   17:  invokeinterface #21,  2; //InterfaceMethod scala/collection/SeqLike.apply:(I)Ljava/lang/Object;
   22:  aload_3
   23:  invokeinterface #72,  3; //InterfaceMethod scala/Function2.apply:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
   28:  astore_3
   29:  istore_2
   30:  astore_0
   31:  goto    0
  LineNumberTable: 
   line 68: 0
   line 67: 6
   line 69: 7

编辑:字节码中的方法是迭代的,这意味着编译器必须应用尾调用优化.

如果没有有效的元素访问(即一种有效的apply方法),最好的方法就是使用迭代器和非尾递归函数来实现foldRight,或者通过构建一个新的函数并对其进行反转foldLeft(后者完成,目前已完成) ).在具有有效随机访问的所有序列的情况下,覆盖并优化该行为.