fold

In der funktionalen Programmierung ist eine Fold eine Funktion höherer Ordnung, die eine rekursive Datenstruktur analysiert und mithilfe einer bestimmten Kombinationsoperation die Ergebnisse der rekursiven Verarbeitung ihrer Bestandteile neu kombiniert und so einen Rückgabewert aufbaut. Falten wird auch als reduzieren, akkumulieren, aggregatieren, komprimieren oder injizieren.
Quelle – Wikipedia

fold :: (a -> b -> b) -> b -> [a] -> b (rechte Faltung)
foldr ersetzt den Listenoperator : durch eine kombinierende Funktion f und [] durch einen Startwert.
foldl arbeitet analog von links, was tail-rekursive Optimierung ermöglicht.
Durch partielle Applikation können Spezialfälle abgeleitet werden (z. B. sum = foldr (+) 0).

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

!VL01_Funktionale_Programmierung, p.107

foldr vs. foldl

Aspekt	`foldr`	`foldl`
Assoziation	rechts → links	links → rechts
Anwendung	`f x (foldr f z xs)`	`foldl f (f z x) xs`
Typisch	für Listen mit unendlichem Rest	für akkumulative Berechnungen
Optimierung	lazy evaluation möglich	tail recursion möglich

Summen

sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + (sum xs)

sum = foldr (+) 0

Ersetzt jedes : durch + und [] durch 0.

Produkt

product :: [Int] -> Int
product [] = 1
product (x:xs) = x * (product xs)

product = foldr (*) 1

Ersetzt : durch * Multiplikation und [] durch 1.

Strukturhaltendes Fold

Wenn man dem Fold die Listenkonstruktoren übergibt, bleibt die Struktur erhalten:

keep = foldr (:) []

→ keep [1,2,3] = [1,2,3]

Map durch Fold

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

Wendet f auf jedes Element an und baut eine neue Liste.

Filter durch Fold

filter p = foldr (\x xs -> if p x then x:xs else xs) []

Selektiert Elemente nach einer Bedingung.

ForAll durch Fold

forAll p l = foldr (\x acc -> p x && acc) True l

Überprüft, ob alle Elemente ein Prädikat erfüllen.

foldl

foldl f z (x:xs) = foldl f (f z x) xs

Ermöglicht lineare, speichereffiziente Akkumulation durch Endrekursion.