scala - 为什么 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 是尾递归的，但它们的右对应部分不是？

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

How do you know when to use fold-left and when to use fold-right?

Implications of foldr vs. foldl (or foldl')

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

Answer 1

(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 来反转集合对此(后者已完成，目前)。在所有序列都具有高效随机访问的情况下，此行为将被覆盖和优化。