Why foldRight and reduceRight are NOT tail recursive?

Question

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

Answer 1

It's a question of how the folding proceeds. The foldLeft operation arranges

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

as

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

(which is 4) while foldRight arranges

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

as

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

(which is -8).

Now, imagine you're pulling the numbers 1, 2, and 3 from a bag and making the calculation pencil-on-paper.

In the foldRight case you're forced to do it like this:

1. Pull a number n from the bag
2. Write "n - ?" on the paper
3. If there are numbers left in the bag, pull another n from the bag, else go to 6.
4. Erase the question mark and replace it with "(n - ?)"
5. Repeat from 3.
6. Erase the question mark and replace it with 10
7. Perform the calculation

In the foldLeft case, you can do it like this:

1. Write 10 on the paper
2. If there are numbers left in the bag, pull another n from the bag, else go to 5.
3. Write " - n" beside the expression you already have
4. Repeat from 2.
5. Perform the calculation

but you wouldn't, because you can also do it like this:

1. Write 10 on the paper
2. Pull a number n from the bag
3. Subtract n from the value you have, erase the value and write down the new value instead
4. Repeat from 2.

Regardless of how many numbers there are in the bag, you only need to have one value written on paper. Tail Call Elimination (TCE) means that instead of building a large structure of recursive calls on the stack, you can pop off and replace an accumulated value as you go along. (I.e., the recursively expressed computation is essentially performed in an iterative manner.)

As others have noted, a random-access structure such as an ArrayLike allows the foldRight to be rearranged into a foldLeft operation, and so become eligible for TCE. The description above does hold for cases where this is impossible.

Answer 2

(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.