Fold

In functionele programmeertalen is een fold (of reduce) een hogere-ordefunctie waarmee een recursieve datastructuur geanalyseerd kan worden. In veel gevallen wordt een lijst in een bepaalde volgorde doorlopen en wordt gaandeweg een bepaalde waarde berekend. Een fold maakt gebruik van twee zaken: een functie die elementen van de datastructuur combineert en de datastructuur zelf. Een voorbeeld:

fold (+) [1,2,3,4,5]

wat resulteert in 1 + 2 + 3 + 4 + 5 = 15. In dit voorbeeld is '+' een associatieve operatie waardoor het irrelevant is hoe de haakjes geplaatst worden. Als benadering van de werking van fold zou men de komma's in de lijst kunnen vervangen door de meegegeven functie.

foldr en foldl

Doorgaans is de functie niet associatief waardoor de volgorde waarin men de berekening uitvoert er wel toe doet. In lijsten zijn er twee manieren waarop dit kan gebeuren: men begint aan de rechterkant met het plaatsen van de haakjes en voert recursief de berekening uit (een right fold) of men begint aan de linkerkant (een left fold). Vaak gebruikt men ook een initiële waarde om de berekening uit te voeren. Dit kan, afhankelijk van wat men wil berekenen, een neutraal element zijn maar ook een andere waarde. Een voorbeeld van een right fold in Haskell (dit gebeurt met de functie foldr):

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

Deze berekening is gelijk aan (1 + (2 + (3 + (4 + 0)))) = 10. Een voorbeeld van een left fold:

foldl (-) 100 [1,2,3,4]

Dit is gelijk aan ((((100 - 1) - 2) - 3) - 4) = 90.

De functies foldl en foldr kunnen in Haskell als volgt gedefinieerd worden (in Haskell is [] een lege lijst en (x:xs) een lijst met x als eerste element en xs de rest van de lijst):

foldr f z []     = z
     -- als de lijst leeg is dan is de opgeleverde waarde de beginwaarde
foldr f z (x:xs) = f x (foldr f z xs)
     -- anders, pas f toe op het eerste element en het resultaat van foldr op de rest

foldl f z []     = z
     -- als de lijst leeg is dan is de opgeleverde waarde de beginwaarde
foldl f z (x:xs) = foldl f (f z x) xs
     -- anders, bereken een nieuwe beginwaarde door f toe te passen op de beginwaarde en
     -- het eerste element en pas foldl met deze waarde toe op de rest van de lijst

Eén belangrijk punt is dat foldr bij luie evaluatie of normal-order evaluatie direct f toepast op de recursieve aanroep van foldr op de rest van de lijst. Als f een deel van het resultaat kan produceren zonder de recursieve aanroep te gebruiken en als de rest van het resultaat nooit nodig is dan wordt de recursieve aanroep niet uitgevoerd. Op deze manier is foldr in staat om met oneindige lijsten om te gaan. foldl roept zichzelf echter aan met nieuwe parameters totdat het einde van de lijst is bereikt. Deze staartrecursie kan efficiënt gecompileerd worden als een lus maar het kan niet omgaan met oneindige lijsten (dit zal resulteren in een oneindige lus).

Een ander technisch punt is dat de nieuwe initiële waarde bij foldl in zulke programmeertalen niet wordt uitgerekend voordat de recursieve aanroep is uitgevoerd. Dit kan leiden tot stack overflows wanneer het einde van de lijst is bereikt en het een gigantische expressie moet uitrekenen. Om deze reden bezitten zulke programmeertalen ook een strikte versie van foldl die eerst de nieuwe initiële waarde uitrekent voordat de recursieve aanroep kan plaatsvinden. In Haskell is dit foldl' (met apostrof, te vinden in de Data.List bibliotheek). Gecombineerd met de snelheid van staartrecursie zijn zulke 'folds' zeer efficiënt wanneer een luie manier van uitrekenen onmogelijk of ongewenst is.

In Scheme kunnen foldr en foldl geschreven worden als:

(define (foldr f z xs)
  (if (null? xs)
      z
      (f (car xs) (foldr f z (cdr xs)))))

(define (foldl f z xs)
  (if (null? xs)
      z
      (foldl f (f z (car xs)) (cdr xs))))

De C++ Standard Template Library bibliotheek implementeert fold als "accumulate" (in de header <numeric>).

foldl1 en foldr1

In bepaalde situaties wil men foldl of foldr maar is er geen geschikte initiële waarde te bedenken, bijvoorbeeld bij het berekenen van de maximale waarde in de lijst met behulp van een functie die de grootste van z'n twee parameters teruggeeft. Er zijn hiervoor varianten van foldl en foldr die geen initiële waarde gebruiken maar het eerste of laatste element van de lijst als startwaarde gebruiken. In Haskell en in een aantal andere talen heten deze foldl1 en foldr1 waarbij de 1 verwijst naar het feit dat het eerste element (vanaf links of vanaf rechts) als startwaarde wordt gebruikt en ook dat de lijsten waarop ze worden toegepast minimaal één element moeten bevatten.

De functie maximum die het grootste element van een lijst oplevert, zal op deze manier een foutmelding geven wanneer deze wordt toegepast op een lege lijst:

maximum = foldl1 max

Standaardfuncties

Veel standaardfuncties in functionele programmeertalen kunnen worden geschreven met behulp van een foldfunctie:

and = foldr (&&) True (plaatst logische conjunctie tussen de elementen in een lijst booleaanse waarden)

or = foldr (||) False (plaatst logische disjunctie tussen de elementen in een lijst booleaanse waarden)

sum = foldr (+) 0 (optellen, telt elementen van een lijst bij elkaar op)

product = foldr (*) 1 (vermenigvuldigen, vermenigvuldigt de elementen van een lijst met elkaar)

concat = foldr (++) [] (concatenatie, namelijk: concat [[1], [2], [3]] = [1,2,3])

(++) xs ys = foldr (:) ys xs (concatenatie, namelijk: [1,2] ++ [3,4] = [1,2,3,4])

maximum = foldl1 max (levert het grootste element in de lijst)

minimum = foldl1 min (levert het kleinste element in de lijst)

map f = foldr ((:).f) [] (de functie map; zie ook hieronder)

reverse = foldr (\a b -> b ++ [a]) [] (geeft de lijst met de elementen in omgekeerde volgorde)

Een andere benadering

Foldfuncties kunnen worden gezien als een manier om de structurele componenten van een datastructuur te vervangen door functies en waarden. In veel talen is een lijst of een lege lijst (in het Engels nil genoemd) of een lijst die is opgebouwd door een element toe te voegen aan een bestaande lijst.In Haskell wordt het opbouwen van een lijst gedaan met de (:) functie, deze wordt ook wel cons of 'constructor' genoemd omdat er een lijst mee geconstrueerd wordt. In Scheme en Lisp heet deze operator cons. Een voorbeeld hiervan is de lijst [1,2,3,4,5], dit is eigenlijk een makkelijkere notatie voor 1:2:3:4:5:[]. Een lijst wordt opgebouwd door eerst het element 5 toe te voegen aan de lege lijst ([5]), vervolgens wordt 4 toegevoegd aan die lijst ([4,5]), enzovoort.

Men kan een right fold beschouwen als het vervangen van de lege lijst door een specifieke waarde (de initiële waarde die wordt meegegeven aan de foldfunctie) en elke (:) door de meegegeven functie:

De werking van foldl is iets minder natuurlijk maar het heeft wel een regelmatige structuur:

De werking van foldl1 en foldr1 is op deze manier ook te visualiseren:

Naast het feit dat deze afbeeldingen de right en left werking van respectievelijk foldr en foldl weergeven is ook te zien dat foldr (:) [] een identiteitsfunctie voor een lijst is: het uitvoeren van foldr (:) [] l levert dezelfde lijst op voor elke lijst l.

Het foldl-diagram suggereert een manier om de elementen van een lijst in omgekeerde volgorde op te leveren: foldl (flip (:)) []. De functie flip draait de volgorde van de parameters om. Dit is nodig aangezien het element dat toegevoegd moet worden aan de lijst nu de rechterparameter is van de (:) functie.

Op deze manier is ook te zien dat de hogere-ordefunctie map geschreven kan worden met behulp van foldr:

map f = foldr ((:).f) []

waarbij (.) (een punt) de operator voor functie-compositie voorstelt.

Deze aanpak maakt het mogelijk om ook foldfuncties te ontwerpen voor algebraïsche datatypes, zoals bomen. Men schrijft een functie die recursief de constructoren van de datastructuur vervangt door functies en de constante waarden door meegegeven waarden. Dit principe wordt catamorfisme genoemd.