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

From Studia Informatyczne

Spis treści

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. Wszystkie przedstawione tu procedury wyższych rzędów są zdefiniowane w module List.

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>

Procedura fold_left ma też swoją wersję przeznaczoną do przetwarzania dwóch list tej samej długości:

 let rec fold_left2 f a l1 l2 = 
   match (l1, l2) with
     ([], [])         -> a |
     (h1::t1, h2::t2) -> fold_left2 f (f a h1 h2) t1 t2 |
     _                -> failwith "Listy różnej długości";;
 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a = <fun>

Przykład [Iloczyn skalarny wektorów reprezentowanych jako listy]

Procedurę fold_left możemy np. zastosować do obliczania iloczynu skalarnego wektorów reprezentowanych jako listy współrzędnych.

 let iloczyn_skalarny l1 l2 = fold_left2 (fun a x y -> a + x * y) 0 l1 l2;;
 val iloczyn_skalarny : int list -> int list -> int = <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>

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

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]

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 (rev 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.

Podobnie jak fold_left, procedura fold_right również ma swój odpowiednik do przetwarzania dwóch list równocześnie:

 let rec fold_right2 f l1 l2 a = 
   match (l1, l2) with 
     ([], [])         -> a |
     (h1::t1, h2::t2) -> f h1 h2 (fold_right2 f t1 t2 a) |
     _                -> failwith "Listy różnej długości";;
 val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c = <fun>

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>


Przykład [Użycie map]

map abs [6; -9; 4; -2; 0];;
- : int list = [6; 9; 4; 2; 0]

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

Procedura map ma również swój odpowiednik do przetwarzania dwóch list tej samej długości:

 let map2 f l1 l2 = 
   fold_right2 (fun h1 h2 t -> (f h1 h2)::t) l1 l2 [];;
 val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list = <fun>

Przykład [Sumowanie wektorów]

Przykładem zastosowania procedury map2 może być sumowanie wektorów reprezentowanych jako listy tej samej długości:

 let suma_wektorow l1 l2 = map2 (+) l1 l2;;
 val suma_wektorow : int list -> int list -> int list = <fun>

Filter

Ostatni schemat procedur przetwarzających listy, jaki przedstawimy w tym wykładzie, to schemat procedury wybierającej z danej listy interesujące nas elementy. Sprawdzamy pewien warunek i zostawiamy tylko elementy spełniające go. Schemat ten realizuje procedura filter:

let filter p l = 
  fold_right (fun h t -> if p h then h::t else t) l [];;
val filter : ('a -> bool) -> 'a list -> 'a list = <fun>

Procedury filter i map są w pewnym sensie dualne do siebie --- map przekształca elementy, ale nie zmienia ich kolejności, ani nie dokonuje żadnej selekcji, a filter nie zmienia wartości elementów, ale dokonuje selekcji.


Przykład [Sito Eratostenesa]

Procedury filter możemy użyć do zaimplementowania sita Eratostenesa.

let sito l = 
  match l with
    []   -> [] |
    h::t -> filter (fun x -> x mod h <> 0) t;;
val sito : int list -> int list = <fun>

let gen n = 
  let rec pom acc k = if k < 2 then acc else pom (k::acc) (k-1)
  in pom [] n;;
val gen : int -> int list = <fun>

let eratostenes n =
  let rec erat l = if l = [] then [] else (List.hd l)::(erat (sito l))
  in erat (gen n);;
val eratostenes : int -> int list = <fun>

eratostenes 42;;
- : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41]

Podsumowanie

Przedstawiliśmy w tym wykładzie cztery proste procedury wyższych rzędów, które ujmują kilka typowych schematów procedur przetwarzających listy. Zdecydowaną większość procedur przetwarzających listy można wyrazić za pomocą którejś z tych procedur lub połączenia kilku z nich. Zważywszy na to, w jak wielu problemach dane w naturalny sposób mają postać ciągów (tj. list), taka technika programowania ma szerokie zastosowanie. Dzięki zastosowaniu procedur wyższych rzędów nasze programy nie tylko są bardziej zwięzłe, ale też bardziej skupiamy się na rozwiązywanym problemie niż na kodowaniu powtarzalnych schematów procedur.


Ćwiczenia

Ćwiczenia