Pliați
Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . |
Fold , cunoscut și sub denumirea de reducere , acumulare , comprimare sau injectare , în programarea funcțională este o funcție care repetă o funcție arbitrară asupra unei structuri de date într-o anumită ordine și construiește o valoare de returnare. În mod obișnuit, este vorba despre două lucruri: o funcție de combinare și o listă de elemente ale unei structuri de date. Pliul continuă apoi să combine elemente ale structurii datelor folosind funcția într-un mod sistematic.
Cele două tipuri principale de pliuri sunt foldr și foldl , unde „r” și „l” reprezintă „dreapta” și respectiv „stânga”.
Definiție
Haskell
În Haskell este definit astfel:
foldr::(a->b->b)->b->[a]->b
foldr fe [] = e
foldr fe (x:xs) = fx (foldr fe xs)
unde f este o funcție binară de tip (a -> b -> b), în timp ce foldl este definit ca
foldl::(a->b->b)->b->[a]->b
foldl fe [] = e
foldl fe (x:xs) = foldl f (fex) xs
CAML
În CAML , foldr poate fi definit ca:
let rec foldr fa lis =
match lis with
[] -> a |
x::xs -> fx (foldr fa xs);;
foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>
Un exemplu, din nou în CAML, de utilizare a funcției foldr este următorul:
Vrem să împărțim o listă în două liste, una conținând toate elementele mai mari decât un anumit n, cealaltă conținând elementele mai mici sau egale cu n.
let split n lis =
let fx (g,l) =
if x > n then (x::g, l) else (g, x::l) in
foldr f ([], []) lis;;
Ieșirea de pe listă urmează [1;2;3;4;5;6]
split 3 [1;2;3;4;5;6];;
. : int list * int list = [4;5;6], [1;2;3]