title: Fold
text: # 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]
  
  