Как Вы знаете, когда использовать оставленный сгибу и когда использовать право сгиба?

Олин Шиверс различал их, говоря, что «foldl - это основной итератор списка», а «foldr - это основной оператор рекурсии списка». Если вы посмотрите, как работает foldl:

((1 + 2) + 3) + 4

, вы можете увидеть, как создается аккумулятор (как в итерации с хвостовой рекурсией). В отличие от этого, foldr продолжает:

1 + (2 + (3 + 4))

, где вы можете увидеть переход к базовому случаю 4 и построение результата оттуда.

Итак, я устанавливаю практическое правило: если это выглядит как итерация списка, то она быть простым для записи в хвостовой рекурсивной форме, foldl - это лучший вариант.

Но на самом деле это, вероятно, будет наиболее очевидно из ассоциативности используемых вами операторов. Если они левоассоциативны, используйте foldl. Если они правоассоциативны, используйте foldr.

Другие плакаты дали хорошие ответы, и я не буду повторять то, что они уже сказали. Поскольку в своем вопросе вы привели пример Scala, я приведу конкретный пример Scala. Как уже говорилось в Tricks , foldRight необходимо сохранить n-1 кадров стека, где n - длина вашего списка, а это может легко привести к переполнению стека - и даже хвостовая рекурсия не спасет вас от этого.

A List (1,2,3) .foldRight (0) (_ + _) уменьшится до:

1 + List(2,3).foldRight(0)(_ + _)        // first stack frame
    2 + List(3).foldRight(0)(_ + _)      // second stack frame
        3 + 0                            // third stack frame 
// (I don't remember if the JVM allocates space 
// on the stack for the third frame as well)

, а List (1,2,3) .foldLeft ( 0) (_ + _) уменьшится до:

(((0 + 1) + 2) + 3)

, которое может быть вычислено итеративно, как это сделано в реализации списка List .

В языке со строгой оценкой, таком как Scala, a foldRight может легко взорвать стек для больших списков, в то время как foldLeft нет.

Пример:

scala> List.range(1, 10000).foldLeft(0)(_ + _)
res1: Int = 49995000

scala> List.range(1, 10000).foldRight(0)(_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...

Поэтому мое практическое правило - для операторов, не обладающих определенной ассоциативностью, всегда используйте foldLeft , по крайней мере, в Scala. В противном случае используйте другие советы, приведенные в ответах;).

Также стоит отметить (и я понимаю, что это немного подчеркивает очевидное), что в случае коммутативного оператора они в значительной степени эквивалентны. В этой ситуации лучшим выбором может быть foldl:

foldl: (((1 + 2) + 3) + 4) может вычислять каждую операцию и переносить накопленное значение вперед

foldr: (1 + (2 + (3 + 4))) перед вычислением необходимо открыть стековый фрейм для 1 +? и 2 +? ] 3 + 4 , затем нужно вернуться и произвести вычисления для каждого.

Я недостаточно разбираюсь в функциональных языках или оптимизации компилятора, чтобы сказать, действительно ли это будет иметь значение, но это определенно кажется более понятным использование foldl с коммутативными операторами.