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

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

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

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

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

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

Источник

4 ответа

Решение

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

Этот пример сворачивания с использованием функции аккумулятора 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))

Пример: минусы-оператор

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

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

Источник

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

((1 + 2) + 3) + 4

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

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.StackruError
        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По крайней мере в Скале. В противном случае следуйте другим советам, данным в ответах;).

Источник

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

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

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

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

Источник
Другие вопросы по тегам