Fold

Fold, anche conosciuta come reduce, accumulate, compress o inject, nella programmazione funzionale è una funzione che itera una funzione arbitraria su una struttura dati in un certo ordine e costruendo un valore di ritorno. Tipicamente una fold, dialoga con due cose: una funzione combinante e una lista di elementi di una struttura dati. La fold poi procede a combinare elementi della struttura dati usando la funzione in modo sistematico.

Le due principali tipologie di fold sono foldr e foldl, dove 'r' ed 'l' stanno, rispettivamente, per 'right' e 'left'.

Foldr

In Haskell viene così definito:

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr f e [] = e

foldr f e (x:xs) = f x (foldr f e xs)

dove f è una funzione binaria di tipo (a -> b -> b)

Foldl

È così definito:

foldl :: (a-> b -> b) -> b -> [a] -> b

foldl f e [] = e

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

Voci correlate

• map
• Omomorfismo