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?
Odpowiedzi:
Możesz przenieść fałdę do notacji operatora infix (wpisując pomiędzy):
W tym przykładzie spasuj używając funkcji akumulatora
x
w ten sposób jest równy
Teraz musisz tylko wnioskować o skojarzeniu swojego operatora (umieszczając nawiasy!).
Jeśli masz lewostronny operator, ustawisz nawiasy w ten sposób
Tutaj używasz lewej zakładki . Przykład (pseudokod w stylu haskell)
Jeśli twój operator jest prawostronny ( prawostronny ), nawiasy powinny być ustawione w ten sposób:
Przykład: Cons-Operator
Ogólnie rzecz biorąc, operatory arytmetyczne (większość operatorów) są lewostronne, więc
foldl
są bardziej rozpowszechnione. Ale w innych przypadkach notacja wrostek + nawiasy jest całkiem przydatna.źródło
foldl1
ifoldr1
w Haskell (foldl
ifoldr
przyjmuje zewnętrzną wartość początkową), a „minusy” Haskella to(:)
nie(::)
, ale poza tym jest to poprawne. Możesz chcieć dodać, że Haskell dodatkowo zapewniafoldl'
/,foldl1'
które są ścisłymi wariantamifoldl
/foldl1
, ponieważ leniwa arytmetyka nie zawsze jest pożądana.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:
można zobaczyć, jak budowany jest akumulator (jak w rekurencyjnej iteracji ogonowej). Natomiast foldr postępuje:
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.
źródło
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 ,
foldRight
należy zachowaćn-1
ramki stosu, gdzien
jest 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:podczas gdy
List(1,2,3).foldLeft(0)(_ + _)
zmniejszy się do:które można obliczyć iteracyjnie, tak jak w przypadku implementacji
List
.W ściśle ocenianym języku, takim jak Scala, a
foldRight
może łatwo wysadzić stos dużych list, podczas gdyfoldLeft
nie.Przykład:
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;).źródło
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 przodufoldr:
(1 + (2 + (3 + 4)))
wymaga otwarcia ramki stosu dla1 + ?
i2 + ?
przed obliczeniem3 + 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
foldr
może być bardziej wydajna niżfoldl
i nie będzie wymagać żadnych dodatkowych ramek stosu.