Pourquoi foldRight et reduceRight ne sont pas récursifs?

Question

Pourquoi le compilateur ne se traduit pas Scala

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

Java équivalent

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

La question est: Pourquoi foldLeft et reduceLeft sont récursives la queue, mais leur droit counteparts ne sont pas?

Voici des liens qui disent que les droitiers ne sont pas récursifs en queue. Je demande pourquoi c'est ainsi.

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) est un 6 tuple valeur, qui n'a pas le foldRight, mais Array(1, 2, 3, 4, 5, 6) fait.

ArrayLike est un trait avec le sous-classement des séquences indexées accès élément efficace, ce qui signifie qu'il a certaines méthodes optimisées, y compris par exemple foldRight. Chaque tableau est implicitement converti en une sous-classe du trait ArrayLike. De tronc 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) 

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: La méthode bytecode est itérative, ce qui signifie que le compilateur doit avoir appliqué une optimisation d'appel de la queue.

Sans accès élément efficace (soit une méthode apply efficace) le meilleur peut faire est génériquement en utilisant itérateurs et une fonction récursive non-queue pour mettre en œuvre foldRight, ou inverser la collection en construisant un nouveau et faire une foldLeft sur ce (Ce dernier est fait, actuellement). Dans le cas de toutes les séquences avec un accès aléatoire efficace, ce comportement est surchargé et optimisé.

Answer 2

Il s'agit de savoir comment se déroule le pliage. L'opération foldLeft organise

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

comme

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

(qui est 4), tandis que foldRight organise

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

comme

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

(qui est -8). Maintenant, imaginez que vous tirez les numéros 1, 2 et 3 d'un sac et que vous faites le calcul crayon sur papier.

Dans le cas que vous êtes foldRight obligé de le faire comme ceci:

1. Tirez plusieurs n du sac
2. Ecrire "? n -" sur le papier
3. S'il y a des numéros laissés dans le sac, tirer une autre n du sac, sinon aller à 6.
4. Effacer le point d'interrogation et le remplacer par « (n -) »
5. 3. Répétez de
6. Effacer le point d'interrogation et le remplacer par 10
7. Effectuer le calcul

Dans le cas foldLeft, vous peut faire comme ceci:

1. 10 Ecrire sur le papier
2. S'il y a des numéros laissés dans le sac, tirez une autre n du sac, sinon aller à 5.
3. Write " - n "à côté de l'expression que vous avez déjà
4. Répéter de 2.
5. Effectuer le calcul

mais vous ne serait pas, parce que vous pouvez aussi le faire comme ceci:

1. 10 Ecrire sur le papier
2. Tirez un nombre n du sac
3. Soustraire n de la la valeur que vous avez, effacer la valeur et notez la nouvelle valeur à la place
4. Répétition de 2.

Indépendamment du nombre de chiffres présents dans le sac, vous n'avez besoin que d'une valeur écrite sur papier. Tail Call Elimination (TCE) signifie qu'au lieu de construire une grande structure d'appels récursifs sur la pile, vous pouvez sauter et remplacer une valeur accumulée au fur et à mesure. (Par exemple, le calcul exprimé récursive est essentiellement réalisée de manière itérative.)

Comme d'autres l'ont noté, une structure à accès aléatoire comme un ArrayLike permet au foldRight d'être réorganisées en une opération foldLeft, et ainsi devenir admissible à TCE. La description ci-dessus s'applique aux cas où cela est impossible.