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 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

Haskell

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

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]

Voci correlate

• Map (funzione)
• Omomorfismo