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

Question

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

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

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

Есть пример в Scala на примере (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))

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

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

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

Answer 2

Олин Шиверс Дифференцировал их, сказав, что «Foldl - это фундаментальный итератор списка», а «FOLTR - основной оператор рекурсии». Если вы посмотрите на то, как работает FOLFL:

((1 + 2) + 3) + 4

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

1 + (2 + (3 + 4))

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

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

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

Answer 3

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

Answer 4

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

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

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

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