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 costruisce 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'.
Definizione
[modifica | modifica wikitesto]Haskell
[modifica | modifica wikitesto]In Haskell è così definita:
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), mentre invece foldl è definita come
foldl::(a->b->b)->b->[a]->b
foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs
CAML
[modifica | modifica wikitesto]In CAML, foldr è definibile come:
let rec foldr f a lis =
match lis with
[] -> a |
x::xs -> f x (foldr f a xs);;
foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>
Un esempio, sempre in CAML, di utilizzo della funzione foldr è il seguente:
Si vuole suddividere una lista in due liste, una contenente tutti gli elementi maggiori di un certo n, l'altra contenente gli elementi minori o uguali a n.
let split n lis =
let f x (g,l) =
if x > n then (x::g, l) else (g, x::l) in
foldr f ([], []) lis;;
Segue l'output sulla lista [1;2;3;4;5;6]
split 3 [1;2;3;4;5;6];;
. : int list * int list = [4;5;6], [1;2;3]