Почему foldRight и reduRight НЕ являются хвостовой рекурсией?

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 и reduLeft являются хвостовой рекурсией, а их правые аналоги - нет?

Вот ссылки, которые говорят, что правша не является хвостовой рекурсивом. Я спрашиваю, почему это так.

Откуда вы знаете, когда использовать сложение влево и когда использовать сложение вправо?

Значение фолд против фолд (или фолд ')

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

Answer 1

Вопрос в том, как происходит сворачивание. Операция foldLeft организует

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

в

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

(то есть 4), а foldRight устраивает

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.

Независимо от того, сколько чисел в сумке, вам нужно иметь только одно значение, написанное на бумаге. Исключение Tail Call (TCE) означает, что вместо построения большой структуры рекурсивных вызовов в стеке, вы можете выскочить и заменить накопленное значение по мере продвижения. (То есть рекурсивно выраженные вычисления по существу выполняются итеративным способом.)

Как уже отмечалось, структура произвольного доступа, такая как ArrayLike, позволяет переставить foldRight в операцию foldLeft и, таким образом, получить право на TCE. Приведенное выше описание действительно для случаев, когда это невозможно.

Answer 2

(1, 2, 3, 4, 5, 6) - это 6-значный кортеж, который не имеет foldRight, но Array(1, 2, 3, 4, 5, 6) имеет.

ArrayLike - это индексированные последовательности подклассов признаков с эффективным доступом к элементам, то есть оптимизированы определенные методы, в том числе, например, foldRight. Каждый массив неявно преобразуется в подкласс черты ArrayLike. Из багажника Скала:

  @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

РЕДАКТИРОВАТЬ: метод в байт-коде является итеративным, что означает, что компилятор должен был применить оптимизацию хвостового вызова.

Без эффективного доступа к элементу (т. Е. Эффективного apply метода) лучшее, что можно сделать в общем случае, - это использовать итераторы и некурочную рекурсивную функцию для реализации foldRight, или реверсировать коллекцию путем создания новой и выполнения foldLeft на этом (последнее уже сделано). В случае всех последовательностей с эффективным произвольным доступом это поведение переопределяется и оптимизируется.