Skąd wiesz, kiedy używać zagięcia w lewo, a kiedy zagięcia w prawo?

Zdaję sobie sprawę, że zagięcie w lewo tworzy drzewa pochylone w lewo, a zagięcie w prawo tworzy drzewa pochylone w prawo, ale kiedy sięgam po fałd, czasami zapadam się w myśl wywołującą ból głowy, próbując określić, który rodzaj fałdu jest odpowiednie. Zwykle kończę rozwijanie całego problemu i przechodzenie przez implementację funkcji zwijania, która dotyczy mojego problemu.

Więc chcę wiedzieć:

• Jakie są praktyczne zasady decydujące o tym, czy spasować w lewo, czy w prawo?
• Jak mogę szybko zdecydować, jakiego rodzaju fałdy użyć, biorąc pod uwagę napotkany problem?

W Scala by Example (PDF) jest przykład użycia zawinięcia do napisania funkcji o nazwie flatten, która łączy listę list elementów w jedną listę. W takim przypadku właściwy wybór jest właściwym wyborem (biorąc pod uwagę sposób łączenia list), ale musiałem się trochę nad tym zastanowić, aby dojść do takiego wniosku.

Ponieważ składanie jest tak powszechną czynnością w programowaniu (funkcjonalnym), chciałbym móc podejmować takie decyzje szybko i pewnie. Więc ... jakieś wskazówki?

Możesz przenieść fałdę do notacji operatora infix (wpisując pomiędzy):

W tym przykładzie spasuj używając funkcji akumulatora x

fold x [A, B, C, D]

w ten sposób jest równy

A x B x C x D

Teraz musisz tylko wnioskować o skojarzeniu swojego operatora (umieszczając nawiasy!).

Jeśli masz lewostronny operator, ustawisz nawiasy w ten sposób

((A x B) x C) x D

Tutaj używasz lewej zakładki . Przykład (pseudokod w stylu haskell)

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

Jeśli twój operator jest prawostronny ( prawostronny ), nawiasy powinny być ustawione w ten sposób:

A x (B x (C x D))

Przykład: Cons-Operator

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

Ogólnie rzecz biorąc, operatory arytmetyczne (większość operatorów) są lewostronne, więc foldlsą bardziej rozpowszechnione. Ale w innych przypadkach notacja wrostek + nawiasy jest całkiem przydatna.

Olin Shivers rozróżnił je, mówiąc: „foldl jest podstawowym iteratorem listy”, a „foldr jest podstawowym operatorem rekursji na liście”. Jeśli spojrzysz, jak działa foldl:

((1 + 2) + 3) + 4

można zobaczyć, jak budowany jest akumulator (jak w rekurencyjnej iteracji ogonowej). Natomiast foldr postępuje:

1 + (2 + (3 + 4))

gdzie można zobaczyć przejście do przypadku podstawowego 4 i zbudować wynik stamtąd.

Przyjmuję więc praktyczną zasadę: jeśli wygląda to na iterację listy, taką, którą można łatwo napisać w formie rekurencyjnej ogonowej, najlepszym rozwiązaniem jest foldl.

Ale tak naprawdę będzie to prawdopodobnie najbardziej oczywiste na podstawie asocjatywności operatorów, których używasz. Jeśli są lewostronne, użyj foldl. Jeśli są prawostronne, użyj foldr.

Inne plakaty dały dobre odpowiedzi i nie powtórzę tego, co już powiedzieli. Ponieważ w swoim pytaniu podałeś przykład Scali, podam konkretny przykład Scali. Jak już powiedział Tricks , foldRightnależy zachować n-1ramki stosu, gdzie njest długość twojej listy, co może łatwo doprowadzić do przepełnienia stosu - i nawet rekurencja ogona nie może cię z tego uratować.

A List(1,2,3).foldRight(0)(_ + _)zmniejszyłoby się do:

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)

podczas gdy List(1,2,3).foldLeft(0)(_ + _)zmniejszy się do:

(((0 + 1) + 2) + 3)

które można obliczyć iteracyjnie, tak jak w przypadku implementacjiList .

W ściśle ocenianym języku, takim jak Scala, a foldRightmoże łatwo wysadzić stos dużych list, podczas gdy foldLeftnie.

Przykład:

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...

Dlatego moja praktyczna zasada jest taka - dla operatorów, które nie mają określonej asocjatywności, zawsze używaj foldLeft, przynajmniej w Scali. W przeciwnym razie skorzystaj z innych porad podanych w odpowiedziach;).

Warto również zauważyć (i zdaję sobie sprawę, że jest to trochę oczywiste), w przypadku operatora przemiennego te dwa są prawie równoważne. W tej sytuacji foldl może być lepszym wyborem:

foldl: (((1 + 2) + 3) + 4)może obliczyć każdą operację i przenieść skumulowaną wartość do przodu

foldr: (1 + (2 + (3 + 4)))wymaga otwarcia ramki stosu dla 1 + ?i 2 + ?przed obliczeniem 3 + 4, a następnie musi wrócić i wykonać obliczenia dla każdego.

Nie jestem wystarczającym ekspertem od języków funkcjonalnych lub optymalizacji kompilatora, aby powiedzieć, czy to rzeczywiście coś zmieni, ale z pewnością bardziej przejrzyste wydaje się użycie foldl z operatorami przemiennymi.