Verschillen tussen foldl en foldr

Opmerking van de redactie: Dit artikel is een reproductie van een baanbrekende uitleg over de verschillen tussen foldr en foldl, zowel in de strikte als de luie (lazy) versies. Omdat deze tekst sinds het eerste verschijnen op hasura/graphql-engine!2933 op 26 september 2019 consistent wordt gebruikt om nieuwkomers te onderwijzen, vinden we dat deze bewaard moet blijven in de blog. Onze dank gaat uit naar Alexis King voor haar toestemming om dit te doen.

Om te beginnen moet je begrijpen dat foldl en foldr geen folds zijn die "van links" en "van rechts" gaan. Zowel foldl als foldr doorlopen de structuur in dezelfde volgorde, wat in het geval van lijsten betekent: van links naar rechts. Het verschil zit in de associativiteit van de fold.

foldl versus foldr geïllustreerd

De beste manier om dit te begrijpen is met een illustratie. Wanneer je schrijft:

foldl (<0xE2><0xA8><0x82>) v [e0, e1, e2, ..., en−1, en]

voer je de volgende berekening uit:

(... (((v <0xE2><0xA8><0x82> e0) <0xE2><0xA8><0x82> e1) <0xE2><0xA8><0x82> e2) <0xE2><0xA8><0x82> ... <0xE2><0xA8><0x82> en−1) <0xE2><0xA8><0x82> en

In contrast hiermee, wanneer je schrijft:

foldr (<0xE2><0xA8><0x82>) v [e0, e1, e2, ..., en−1, en]

voer je deze berekening uit:

e0 <0xE2><0xA8><0x82> (e1 <0xE2><0xA8><0x82> (e2 <0xE2><0xA8><0x82> ... <0xE2><0xA8><0x82> (en−1 <0xE2><0xA8><0x82> (en <0xE2><0xA8><0x82> v)) ... ))

Zie je het verschil? In beide expressies verschijnen de elementen van de lijst in dezelfde volgorde — van links naar rechts — maar de groepering verandert. Bij foldl zijn de toepassingen van (<0xE2><0xA8><0x82>) links-associatief, terwijl ze bij foldr rechts-associatief zijn.

foldl versus foldr in een strikte context

De vraag is: hoe beïnvloedt dit verschil daadwerkelijk het gedrag van een programma? Laten we beginnen met wat het verschil zou zijn in een strikte taal. In een strikte taal verloopt de evaluatievolgorde altijd van "binnen naar buiten", beginnend bij de meest diep geneste expressie.

Laten we dit eerst bekijken in de context van foldl. Stel dat we deze expressie schrijven:

foldl (+) 0 [1, 2, 3, 4]

Op basis van de bovenstaande illustratie weten we dat deze expressie gelijkstaat aan:

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

Als we van binnen naar buiten reduceren, krijgen we de volgende volgorde:

foldl (+) 0 [1, 2, 3, 4]
= (((0 + 1) + 2) + 3) + 4
= (( 1      + 2) + 3) + 4
= (  3           + 3) + 4
=    6                + 4
=   10

Als we daarentegen foldr hadden gebruikt, zouden we hetzelfde resultaat krijgen (aangezien (+) een associatieve, commutatieve operatie is), maar met een iets andere reductievolgorde:

foldr (+) 0 [1, 2, 3, 4]
= 1 + (2 + (3 + (4 + 0)))
= 1 + (2 + (3 +      4 ))
= 1 + (2 +           7  )
= 1 +                9
= 10

Wat is het praktische verschil tussen deze twee? Let op het volgende detail: bij foldl hebben we alleen het eerste element van de lijst nodig om te beginnen met reduceren, maar bij foldr moeten we aan het einde van de lijst beginnen en "achteruit" reduceren¹. Praktisch gezien betekent dit dat foldl staart-recursief (tail-recursive) kan zijn en de lijst in constante ruimte reduceert terwijl deze deze doorloopt, terwijl foldr dat niet kan: om een lijst van lengte $n$ met foldr te reduceren, moet je $n$ stack frames aanmaken voordat er enige reductie kan beginnen.

¹ Dit is waarom foldr soms wordt beschreven als "folden vanaf rechts", ook al doorloopt het de lijst van links naar rechts. Zoals we zullen zien, geldt dit echter niet in luie (lazy) talen!

foldl in een luie context

Maar hoe zit het in luie talen, zoals Haskell? In een luie taal verloopt de evaluatievolgorde niet van "binnen naar buiten" zoals in strikte talen, maar juist van "buiten naar binnen", waarbij expressies pas worden geëvalueerd wanneer hun resultaten worden gevraagd.

In een strikte taal wordt foldl (+) 0 [1, 2, 3, 4] niet daadwerkelijk omgezet in de expressie (((0 + 1) + 2) + 3) + 4; zoals eerder vermeld, wordt het geïmplementeerd als een staart-recursieve loop. Maar in Haskell wordt het in feite wel uitgebreid tot die expressie voordat er enige reductie begint — elke toepassing van (+) wordt lui opgeschort in een thunk.

Als we thunks expliciet aanduiden met ⟨⟩ haken, ziet de thunk waar we mee eindigen er zo uit:

⟨⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ + 4⟩

Deze thunks worden pas geforceerd wanneer de buitenste thunk wordt geëvalueerd, wat ervoor zorgt dat (+) wordt toegepast op de argumenten ⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ en 4. Omdat (+) strikt is in beide argumenten, zal het de volgende thunk forceren, die op zijn beurt (+) toepast op ⟨⟨0 + 1⟩ + 2⟩ en 3, enzovoort tot de hele thunk-boom is gereduceerd.

Het resultaat is hetzelfde, maar vanuit een praktisch oogpunt is dit erg slecht. In plaats van de lijst in constante ruimte te reduceren, zoals we deden in de strikte taal, creëren we nu een thunk die lineair is aan de grootte van de invoerlijst! Dat is zelfs nog erger dan het lijkt: in een strikte taal neemt de invoerlijst ruimte in beslag die lineair is aan zijn eigen grootte, dus ons totale ruimteverbruik voor het produceren/consumeren van de lijst zou simpelweg een constante factor toename zijn. In een luie taal is de lijst zelf echter meer als een stream, die daadwerkelijk constante ruimte kan gebruiken als de hele stream niet volledig in het geheugen is gerealiseerd. Door de luie foldl te gebruiken, zijn we mogelijk gegaan van een algoritme met constante ruimte naar een algoritme met lineaire ruimte, wat onwenselijk is.

Wat we willen, is het gedrag van de strikte foldl terugkrijgen: een accumulator efficiënt bijwerken terwijl we de lijst doorlopen, zonder thunks op te bouwen. Daarom hebben we een striktere versie van foldl nodig, en dat is precies wat foldl' is. foldl' stelt een eis aan de ⟨0 + 1⟩ thunk voordat hij naar het volgende element van de lijst gaat, zodat hij in plaats van een grotere ⟨⟨0 + 1⟩ + 2⟩ thunk simpelweg een ⟨1 + 2⟩ thunk bouwt. foldl' blijft de lijst in constante ruimte doorlopen en bouwt nooit een thunk die groter is dan een enkele toepassing van (+).

foldr in een luie context

Maar hoe zit het met foldr? Onthoud dat foldr in een strikte taal al ruimte nodig had die lineair was aan de grootte van de invoerlijst, omdat het fundamenteel het laatste element in de lijst nodig had voordat het kon beginnen met reduceren. Indien we een luie foldr overwegen met een strikte operatie zoals (+), is dit nog steeds waar — maar op een interessant andere manier dan bij foldl.

Bij foldl eindigden we met het incrementeel opbouwen van thunks terwijl we de lijst doorliepen, wat leidde tot een zeer grote, geneste thunk. Maar bij foldr gebeurt dat niet. Waarom? Overweeg de expansie nog eens kort:

foldr (+) 0 [1, 2, 3, 4] = 1 + (2 + (3 + (4 + 0)))

Om te zien hoe we bij deze expansie komen, schrijven we deze expliciet inductief op:

foldr (+) 0 [1, 2, 3, 4]
= 1 + foldr (+) 0 [2, 3, 4]
= 1 + (2 + foldr (+) 0 [3, 4])
= 1 + (2 + (3 + foldr (+) 0 [4]))
= 1 + (2 + (3 + (4 + foldr (+) 0 [])))
= 1 + (2 + (3 + (4 + 0)))

Dit maakt de recursieve aanroepen naar foldr explicieter. In een strikte taal moeten we, zodra we foldr aanroepen, het resultaat eisen, waardoor we de hele lijst moeten doorlopen. Maar hier wordt het interessant: in een luie taal kunnen we simpelweg het volgende resultaat teruggeven, met een opgeschorte thunk:

foldr (+) 0 [1, 2, 3, 4] = 1 + ⟨foldr (+) 0 [2, 3, 4]⟩

Dit lijkt misschien irrelevant, want zodra dat resultaat geforceerd wordt, zal ⟨foldr (+) 0 [2, 3, 4]⟩ door (+) worden geforceerd en krijgen we dezelfde reductievolgorde als voorheen. Maar let op: dit is alleen waar omdat (+) een strikte operatie is. Wat als we in plaats daarvan een luie operatie zouden gebruiken, zoals (:)? In dat geval zouden we de volgende expansie krijgen:

foldr (:) [] [1, 2, 3, 4] = 1 : ⟨foldr (:) [] [2, 3, 4]⟩

En raad eens? Dat resultaat is al in weak-head normal form (WHNF)! De evaluatie stopt hier dus simpelweg totdat de rest van het resultaat expliciet wordt gevraagd door iets anders. In dit specifieke geval is dit een zinloze operatie, aangezien foldr (:) [] gewoon een ingewikkelde identiteitsfunctie voor lijsten is, maar we kunnen ons een iets complexere functie voorstellen, zoals een functie die elk element in een lijst verdubbelt:

let f x xs = (x * 2) : xs
in foldr f [] [1, 2, 3, 4]

Dit zal expanderen naar:

foldr f [] [1, 2, 3, 4] = ⟨1 * 2⟩ : ⟨foldr f [] [2, 3, 4]⟩

...en opnieuw zal het daar stoppen, omdat het al in WHNF is. Hoe is dit nuttig? Nou, wat als we niet het hele resultaat van de lijst zouden consumeren, zoals hier:

sum (take 2 (foldr f [] [1, 2, 3, 4]))

Omdat take 2 alleen de eerste twee elementen van de lijst teruggeeft, zal sum (wanneer het de lijst en de waarden forceert om ze bij elkaar op te tellen) nooit zelfs maar de thunk ⟨foldr f [] [3, 4]⟩ evalueren, en zal de lijst slechts gedeeltelijk worden doorlopen.

Wat zijn de implicaties hiervan? Het betekent dat foldr mogelijk werk kan besparen als de reducerende functie lui is in zijn tweede argument en de resultaatlijst niet volledig wordt geconsumeerd. In feite kan foldr op deze manier opereren op oneindige lijsten, terwijl foldl dat niet kan. Het betekent ook dat foldr mogelijk onderhevig is aan meer list fusion dan foldl, hoewel dat een geheel andere discussie is.

foldl versus foldr in een luie context: samenvattend

Kort samengevat is dit wat ik tot nu toe heb gezegd:

• In een luie taal is foldl op lijsten slecht omdat het te lui is en grote thunks opbouwt. Gebruik in plaats daarvan foldl' om de thunks incrementeel te forceren en de lijst in constante ruimte te consumeren.
• In een luie taal is foldr op lijsten goed omdat het lui is; als de reducerende functie lui is in zijn tweede argument, kan het werk besparen.

Deze twee zaken lijken misschien tegenstrijdig. Waarom is foldl slecht omdat het te lui is, terwijl foldr goed is omdat het lui is?

Om het verschil te begrijpen, expanderen we foldl inductief zoals we deden met foldr:

foldl (+) 0 [1, 2, 3, 4]
= foldl (+) (0 + 1) [2, 3, 4]
= foldl (+) ((0 + 1) + 2) [3, 4]
= foldl (+) (((0 + 1) + 2) + 3) [4]
= foldl (+) ((((0 + 1) + 2) + 3) + 4) []
= ((((0 + 1) + 2) + 3) + 4)

Zie je het verschil? Bij foldr werd de recursieve aanroep weggeduwd naar een "blad" van de resulterende expressieboom, maar bij foldl is de recursieve aanroep altijd de wortel. Dit is overigens waarom foldl staart-recursief is — dit is precies wat staart-recursie is! — maar het betekent ook dat het onmogelijk lui kan zijn, aangezien het nooit in WHNF zal zijn totdat de volledige lijst is doorlopen.

Dit geeft ons een algemene vuistregel voor het gebruik van foldl en foldr op lijsten:

1. Wanneer de accumulatiefunctie strikt is, gebruik dan foldl' om de lijst in constante ruimte te consumeren, aangezien de hele lijst sowieso moet worden doorlopen.
2. Wanneer de accumulatiefunctie lui is in zijn tweede argument, gebruik dan foldr om het werk incrementeel uit te voeren om streaming en werkbesparing te verbeteren.
3. Gebruik nooit foldl of foldr'; ze zijn op lijsten altijd slechter.

In jouw geval is de accumulatiefunctie die je toepast Map.delete, wat strikt is, dus zou je foldl' moeten gebruiken.

Dat gezegd hebbende, is dit vaak een micro-optimalisatie. Als de lijst niet groot is, maakt het meestal niet echt uit. Het is echter een goede gewoonte om aan te leren en het is de moeite waard om te begrijpen, aangezien het een uitstekend voorbeeld is van laziness in de praktijk.

Addendum: foldl en foldr op andere datastructuren

Als laatste opmerking vraag je je misschien af: als foldl en foldr' zo nutteloos zijn, waarom bestaan ze dan überhaupt? Waarom niet gewoon foldl' en foldr?

Het antwoord is dat alles wat ik zojuist heb gezegd alleen geldt voor lijsten. Dit gedrag treedt op omdat (:) fundamenteel een rechts-associatieve operatie is, waardoor het "resterende" deel van de lijst zich aan de rechterkant bevindt. Maar als we snoc lists hadden, zoals deze:

data SnocList a = Nil | Snoc (SnocList a) a

...dan zouden onze lijsten links-associatief zijn, en zouden we foldr' willen gebruiken in situaties waarin we foldl' gebruiken op gewone lijsten, en foldl waar we foldr gebruiken op gewone lijsten. Een beetje verwarrend, nietwaar?

Gewone cons lijsten en snoc lijsten zijn in feite de twee extremen van foldl versus foldr, maar in de praktijk zijn andere datastructuren een stuk minder eenduidig. Neem bijvoorbeeld een boom:

data Tree a = Leaf | Branch (Tree a) a (Tree a)

In dat geval bevinden sommige elementen zich links en andere rechts, en is noch foldl noch foldr duidelijk superieur. Als je in dat geval echt om prestaties geeft, zijn foldMap en foldMap' meestal je beste gok, aangezien zij geen specifieke associativiteit van aanroepen naar (<>) voorschrijven. (Hoewel foldMap' pas beschikbaar is vanaf base-4.13.0.0, wat beschikbaar is vanaf GHC 8.8.1. Maar in werkelijkheid maakt dat waarschijnlijk niet uit.)