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

99

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?

Jeff
źródło
1
wygląda podobnie do stackoverflow.com/questions/384797/ ...
Steven Huwig
1
To Q jest bardziej ogólne niż to, które dotyczyło konkretnie Haskella. Lenistwo robi dużą różnicę w odpowiedzi na pytanie.
Chris Conway,
O. Dziwne, jakoś pomyślałem, że widziałem tag Haskella w tym pytaniu, ale chyba nie ...
ephemient

Odpowiedzi:

105

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.

Dario
źródło
6
Cóż, to, co opisałeś, jest w rzeczywistości foldl1i foldr1w Haskell ( foldli foldrprzyjmuje zewnętrzną wartość początkową), a „minusy” Haskella to (:)nie (::), ale poza tym jest to poprawne. Możesz chcieć dodać, że Haskell dodatkowo zapewnia foldl'/, foldl1'które są ścisłymi wariantami foldl/ foldl1, ponieważ leniwa arytmetyka nie zawsze jest pożądana.
ephemient
Przepraszam, myślałem, że widziałem tag „Haskell” w tym pytaniu, ale go tam nie ma. Mój komentarz nie ma większego sensu, jeśli to nie Haskell ...
ephemient
@ephemient Widziałeś to. To „pseudokod w stylu haskell”. :)
laughing_man
Najlepsza odpowiedź, jaką kiedykolwiek widziałem, dotyczy różnicy między fałdami.
AleXoundOS
60

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.

Steven Huwig
źródło
29

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

Flaviu Cipcigan
źródło
13
Było to prawdą wcześniej, ale w obecnych wersjach Scali zmieniono foldRight, aby zastosować foldLeft na odwróconej kopii listy. Na przykład w wersji 2.10.3 github.com/scala/scala/blob/v2.10.3/src/library/scala/… . Wygląda na to, że ta zmiana została wprowadzona na początku 2013 roku - github.com/scala/scala/commit/… .
Dhruv Kapoor
4

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.


źródło
1
Dodatkowe ramki stosu z pewnością będą miały znaczenie w przypadku dużych list. Jeśli ramki stosu przekraczają rozmiar pamięci podręcznej procesora, to błędy w pamięci podręcznej wpłyną na wydajność. O ile lista nie jest podwójnie połączona, trudno jest uczynić foldr funkcją rekurencyjną ogonową, więc powinieneś używać foldl, chyba że jest powód, aby tego nie robić.
A. Levy
4
Leniwa natura Haskella utrudnia tę analizę. Jeśli zwijana funkcja nie jest ścisła w drugim parametrze, foldrmoże być bardziej wydajna niż foldli nie będzie wymagać żadnych dodatkowych ramek stosu.
ephemient
2
Przepraszam, myślałem, że widziałem tag „Haskell” w tym pytaniu, ale go tam nie ma. Mój komentarz nie ma większego sensu, jeśli to nie Haskell ...
ephemient