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

Wstęp

Istnieje zestaw standardowych procedur wyższych rzędów specjalnie przeznaczonych do przetwarzania list. Będą one tematem tego wykładu. Większość procedur przetwarzających listy jest budowana według kilku powtarzających się schematów. Ujmując te schematy w postaci procedur wyższych rzędów uzyskamy procedury wyższych rzędów, o których jest mowa.

Fold

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 [];;