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

Вы можете преобразовать свертку в нотацию инфиксного оператора (напишите между ними):

В этом примере выполняется сворачивание с использованием аккумуляторной функции x

fold x [A, B, C, D]

таким образом равно

A x B x C x D

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

Если у вас есть левоассоциативный оператор, вы установите следующие круглые скобки

((A x B) x C) x D

Здесь используется левый сгиб. Пример (псевдокод в стиле haskell)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

Если ваш оператор является правоассоциативным (правый угол), круглые скобки будут установлены следующим образом:

A x (B x (C x D))

Пример: Cons-Operator

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

В общем, арифметические операторы (большинство операторов) левоассоциативны, поэтому foldl более распространен. Но в остальных случаях весьма полезны инфиксные обозначения + круглые скобки.

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

((1 + 2) + 3) + 4

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

1 + (2 + (3 + 4))

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

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

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

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

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, 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: (((1 + 2) + 3) + 4) может вычислять каждую операцию и переносить накопленное значение вперед

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

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