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_Left

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 x _ -> x + 1) 0 l;;
val length : 'a list -> int = <fun>

Kumulowany wynik może oczywiście być czymś bardziej skomplikowanym niż liczbą. Oto implementacja procedury odwracającej listę rev za pomocą fold_left. Ze względu na wielkość konstruowanego wyniku, procedura ta ma złożoność pamięciową liniową.

let rev l = fold_left (fun a h -> h::a) [] l;;
val rev : 'a list -> 'a list = <fun>

Fold_Right

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>

Zauważmy, że w definicji tej procedury nie występuje rekurencja ogonowa. Tak więc jej koszt pamięciowy (z pominięciem kosztu stosowania procedury f i konstruowania wyniku) jest liniowy, a więc gorszy niż w przypadku procedury fold_left. Dlaczego więc stosuje się oprócz procedury fold_left procedurę fold_right? Po pierwsze, jeżeli koszt pamięciowy związany z konstruowanym wynikiem lub obliczeniami jest przynajmniej liniowy, to różnica między fold_left i fold_right znika. Po drugie, w niektórych obliczeniach dużo prościej jest przetwarzać elementy w kolejności odwrotnej do tej, w jakiej występują na liście. Przykładem mogą być tu opisane dalej procedury map i filter. Oto kilka przykładów zastosowania procedury fold_right. Przykład [Przykłady zastosowania fold_right]

Poniższa procedura konstruuje kopię danej listy (tzn. wynik ma taką samą wartość jak argument, ale pary tworzące listę zajmują inne miejsce w pamięci).

let copy_list l = fold_right (fun h a -> h::a) l [];;
val copy_list : 'a list -> 'a list = <fun>

Oto przykłady procedur z poprzedniego punktu zaimplementowanych tym razem przy użyciu fold_right:

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

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

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

Przykład [Implementacja procedury flatten przy pomocy fold_right]

kkkk

Przypomnijmy sobie jedno z ćwiczeń, polegające na napisaniu procedury flatten, która przekształca listę list elementów w listę elementów, poprzez sklejenie list składowych. Procedurę tę można szczególnie zwięźle i elegancko zaimplementować używając fold_right.

let flatten l = fold_right (@) l [];; 
val flatten : 'a list list -> 'a list = <fun>

flatten [[1;2]; []; [3]; []; [4;5;6]];;
- : int list = [1; 2; 3; 4; 5; 6]

Procedury fold_left i fold_right są najbardziej elementarne spośród procedur, które przedstawiamy w tym wykładzie. Porównując je pod tym kątem, okazuje się, że fold_left jest bardziej elementarna. Można zarówno zdefiniować fold_right za pomocą fold_left, jak i odwrotnie. Jednak definiując fold_left za pomocą fold_right jesteśmy skazani na przynajmniej liniową złożność pamięciową.

Przykład [Implementacja fold_right za pomocą fold_left]

let fold_right f l a = 
  let rev = fold_left (fun a h -> h::a) [] 
  in fold_left (fun x h -> f h x) a l;;
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

Przykład [Implementacja fold_left za pomocą fold_right

let fold_left f a l = 
  fold_right (fun h p -> function x -> p (f x h)) l (fun x -> x) a;;
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

Zwróćmy uwagę, że wartość kumulowana przez fold_right to procedura. Procedura ta przekształca wynik skumulowany przez fold_left na podstawie elementów listy, które nie zostały jeszcze przejrzane przez fold_right, w wynik ostateczny. Kumulowana przez fold_right procedura zajmuje liniową (ze względu na długość listy) pamięć. Tak więc powyższa konstrukcja jest poprawna, ale mniej efektywna niż rekurencyjna, ogonowa implementacja fold_left.

Map

Kolejny często pojawiający się schemat procedur przetwarzających listy polega na tym, że do wszystkich elementów listy stosujemy to samo przekształcenie. Schemat ten został ujęty w postaci procedury map, która stosuje zadaną procedurę do wszystkich elementów danej listy i zwraca listę wyników. Oto implementacja tej procedury za pomocą fold_right:

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

Filter

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