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

Я знаю, что fold-left создает деревья с наклоном влево, а fold-right создает деревья с наклоном вправо, но когда я тянусь к сгибу, я иногда зацикливаюсь на вызывающих головную боль мыслях, пытаясь определить, какой тип сгиба подходит. Обычно я закрываю всю проблему и перехожу к реализации функции сгиба применительно к моей проблеме.

Итак, я хочу знать:

• Какие эмпирические правила определяют, сбрасывать ли карты влево или вправо?
• Как я могу быстро решить, какой тип складки использовать, учитывая мою проблему?

В Scala by Example (PDF) есть пример использования свертки для написания функции под названием flatten, которая объединяет список списков элементов в один список. В этом случае правильное сгибание - правильный выбор (учитывая способ объединения списков), но мне пришлось немного подумать, чтобы прийти к такому выводу.

Поскольку сворачивание - такое обычное явление в (функциональном) программировании, я хотел бы иметь возможность принимать такие решения быстро и уверенно. Итак ... какие-нибудь советы?

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

В этом примере сворачивание с использованием функции аккумулятора 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 - это основной итератор списка», а «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, a foldRightможет легко взорвать стек для больших списков, а a 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 с коммутативными операторами.