Programowanie funkcyjne/Procedury wyższych rzędów i listy

Procedury wyższych rzędów i listy

Funkcje przetwarzające listy często mają ten sam schemat. Spróbujmy ująć ten schemat w postaci procedur wyższych rzędów. Najczęściej przeglądamy kolejne elementy listy i obliczamy na ich podstawie pewien wynik. W schemacie tym mamy następujące elementy zmienne:

• elementy listy przetwarzamy od lewej do prawej, lub odwrotnie,
• wynik dla pustej listy,
• wynik dla nie pustej listy, jako funkcja głowy i wyniku obliczonego dla ogona.

W zależności od kierunku przetwarzania listy, schemat ten możemy ująć w postaci następujących dwóch procedur:

let rec foldr f l a = 
  match l with
    []   -> a |
    h::t -> f h (foldr f t a);;
  
let rec foldl f a l = 
  match l with 
    []   -> a |
    h::t -> foldl f (f a h) t;;
  
let fold = foldl;;        
     

Oto kilka prostych zastosowań:

let sum l = fold (+) 0 l;;
let prod l = fold ( * ) 1 l;;
     

Inny schemat, to przetwarzanie wszystkich elementów listy, element po elemencie.

let map f l = 
  foldr 
    (fun h t -> (f h)::t) 
    l 
    [];;
     

Kolejny częsty schemat, to selekcja elementów listy --- sprawdzamy pewien warunek i zostawiamy tylko elementy spełniające go.

let filter p l = 
  foldr (fun h t -> if p h then h::t else t) l [];;