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

Jeden z najczęściej występujących schematów procedur przetwarzających listy polega na tym, że przeglądamy kolejne elementy listy i obliczamy na ich podstawie pewien wynik. W trakcie przeglądania listy przechowujemy wynik pośredni, obliczony dla już przejrzanych elementów. W każdym kroku przeglądamy jeden element listy i uwzględniamy go w wyniku pośrednim. Możemy powiedzieć, że kumulujemy wpływ kolejnych elementów listy na wynik. Po przejrzeniu wszystkich elementów listy mamy gotowy wynik.

W schemacie tym mamy następujące elementy zmienne:

• wynik dla pustej listy,
• procedura kumulująca wpływ kolejnych elementów listy na wynik,
• listę do przetworzenia.

Procedura realizująca powyższy schemat, przeglądająca elementy zgodnie z ich kolejnością na liście, nosi tradycyjną nazwę fold_left i jest zdefiniowana następująco:

let rec fold_left f a l = 
  match l with 
    []   -> a |
    h::t -> fold_left f (f a h) t;;
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

Pierwszym parametrem jest procedura kumulująca wynik. Ma ona dwa argumenty: dotychczas obliczony wynik i kolejny element listy do przetworzenia. Drugi argument to wynik dla pustej listy, a trzeci to lista do przetworzenia.

Zwróćmy uwagę, że w definicji procedury fold_left mamy rekurencję ogonową. Dlatego też procedura ta ma, nie licząc kosztu wielokrotnego zastosowania procedury f oraz wielkości budowanego wyniku, liniowy koszt czasowy i stały koszt pamięciowy.

Oto kilka prostych przykładów.

Przykład [Przykłady zastosowania fold_left]

Poniższe dwie procedury obliczają odpowiednio sumę i iloczyn wszystkich elementów listy:

let sum l = fold_left (+) 0 l;;
val sum : int list -> int = <fun>

let prod l = fold_left ( * ) 1 l;;
val prod : int list -> int = <fun>

Długość listy możemy również obliczyć używając fold_left. Wartości elementów listy nie mają tu znaczenia, tylko sama ich obecność.

let length l = 
  fold_left (fun l _ -> l + 1) 0 l;;
val length : 'a list -> int = <fun>

Jak łatwo się domyślić, jeżeli istnieje procedura fold_left, to powinna być też proceudra fold_right. I faktycznie jest. Różni się ona tym, że elementy listy są przeglądane w odwrotnej kolejności, niż występują na liście, czyli od prawej. Procedura ta jest zdefiniowana następująco:

let rec fold_right f l a = 
  match l with
    []   -> a |
    h::t -> f h (fold_right f t a);;
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

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

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

• elementy listy przetwarzamy od lewej do prawej, lub odwrotnie,

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

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