为什么foldRight和reduceRight不是尾递归？ [英] Why foldRight and reduceRight are NOT tail recursive?

问题描述

为什么编译器不能翻译Scala？b / b>

 （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; 
 
 $ / code> 

问题是：为什么foldLeft和reduceLeft是尾递归，但是它们的右对角是不是？

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

您如何知道什么时候使用折叠左键以及什么时候使用折叠右键？

foldr与foldl的关系（或foldl'）

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

解决方案

（1，2，3，4，5，6）是一个6值元组，它没有 foldRight ，但数组（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）; 
 
 ... 
 
代码：
 Stack = 6，Locals = 6，Args_size = 5 
 0：iload_1 
 1：iload_2 
 2：if_icmpne 7 
 5：aload_3 
 6：经济学
 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：转到0 
 LineNumberTable：
第68行：
第67行： 6 
 line 69：7 
  

编辑：字节码中的方法是迭代的，这意味着编译器必须应用尾部调用优化。

如果没有高效的元素访问（即高效的 apply 方法）可以通常使用迭代器和非尾递归函数来实现 foldRight ，或者通过构建一个新的函数并执行 foldLeft （后者目前已完成）。在所有序列都具有高效的随机访问的情况下，这种行为被覆盖并优化。

Why compiler does not translate Scala

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

to Java equivalent

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;
}

The question is: Why foldLeft and reduceLeft are tail recursive, but their right counteparts aren't?

Here are links which says that right handed aren't tail recursive. I am asking why it is so.

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

解决方案

(1, 2, 3, 4, 5, 6) is a 6 valued tuple, which doesn't have the foldRight, but Array(1, 2, 3, 4, 5, 6) does.

ArrayLike is a trait subclassing indexed sequences with efficient element access, meaning it has certain methods optimized, including for instance foldRight. Each array is implicitly converted to a subclass of the ArrayLike trait. From Scala trunk:

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

Bytecode:

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

EDIT: The method in bytecode is iterative, meaning that the compiler must have applied a tail call optimization.

Without efficient element access (i.e. an efficient apply method) the best one can do generically is using iterators and a non-tail recursive function to implement foldRight, or reversing the collection by building a new one and doing a foldLeft on that (the latter is done, currently). In the case of all sequences with efficient random access, this behaviour is overridden and optimized.

这篇关于为什么foldRight和reduceRight不是尾递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！