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

Question

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

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

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

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

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

Answer 1

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

Этот пример фолда с использованием функции аккумулятора 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 является более распространенным. Но в других случаях инфиксная нотация + скобки весьма полезны.

Answer 2

Олин Шиверс дифференцировал их, сказав, что "foldl - это фундаментальный итератор списка" и "foldr - фундаментальный оператор рекурсии списка". Если вы посмотрите, как работает foldl:

((1 + 2) + 3) + 4

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

1 + (2 + (3 + 4))

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

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

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

Answer 3

Другие постеры дали хорошие ответы, и я не буду повторять то, что они уже сказали. Поскольку вы привели пример 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, 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. В противном случае следуйте другим советам, данным в ответах;).

Answer 4

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

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

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

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