Programowanie funkcyjne/Struktury danych
Wstęp
Jak dotąd, definiowane przez nas pojęcia to wyłącznie stałe kilku wbudowanych typów i procedury. O ile możemy definiować złożone procedury, to nie jesteśmy w stanie definiować złożonych danych. Zajmiemy się tym dzisiaj. Zajmiemy się również metodyką tworzenia nowych typów danych. Co to jest typ danych? Jest to zbiór wartości wraz z zestawem podstawowych operacji na tych wartościach. Typy dostępne w danym języku programowania tworzą dziedzinę algorytmiczną.
Typy wbudowane
Poznaliśmy już kilka podstawowych typów danych wbudowanych w język Ocaml bool, int, float, char i string wraz z operacjami na nich. W Ocamlu z nazwy procedury, a więc też i operacji arytmetycznej, muszą wynikać oczekiwania co do typów argumentów. Dlatego też operacje arytmetyczne +, *, itd. dotyczą liczb całkowitych, a operacje na liczbach zmiennopozycyjnych mają postać +., *., ...
Wzorce
Zanim przedstawimy sposoby konstruowania złożonych typów danych, wprowadzimy pojęcie wzorca. Co to jest wzorzec? Wzorzec jest to rodzaj "wyrażenia" zawierającego wprowadzane nowe nazwy wartości. Podana wartość jest dopasowywana do wzorca i jeśli pasuje to występujące we wzorcu nazwy uzyskują jako wartości odpowiednie składowe dopasowywanego wyrażenia. Identyfikatory występujące we wzorcu nie mogą się powtarzać, gdyż każde wystąpienie identyfikatora odpowiada za inny fragment dopasowywanej wartości. Wzorce będą stanowić podstawowy mechanizm dekompozycji złożonych wartości, jednak ich zastosowanie nie ogranicza się tylko do tego.
Podstawowe wzorce, to:
<wzorzec> ::= <identyfikator> | _ | <stała> | ...
- identyfikator - pasuje do każdej wartości, nazwie przyporządkowywana jest dana wartość,
- _ - tak jak zmienna, tylko nie wprowadza żadnej nowej nazwy,
- stała (np. liczbowa) - pasuje tylko do samej siebie.
Wzorców możemy używać w konstrukcji match-with oraz w definicjach procedur, zarówno procedur nazwanych, jak i -abstrakcji:
<wyrażenie> ::= match <wyrażenie> with { <wzorzec> -> <wyrażenie> | }*
<wzorzec> -> <wyrażenie>
<definicja> ::= let rec <identyfikator> <wzorzec> + = <wyrażenie>
<definicja> ::= let <wzorzec> <wzorzec> + = <wyrażenie>
<wyrażenie> ::= function { <wzorzec> -> <wyrażenie> | }*
<wzorzec> -> <wyrażenie>
Jeśli wartość (lub wartości argumentów) pasuje do kilku wzorców, to wybierany jest pierwszy z nich. Jeżeli żaden z wzorców nie pasuje do wartości, to zgłaszany jest błąd (wyjątek).
Przykład [Konstrukcja match-with]
3;; - : int = 3 let _ = 3;; - : int = 3
let rec silnia = function 1 -> 1 | x -> x * silnia (x - 1);;
let rec silnia x = match x with 1 -> 1 | x -> x * silnia (x-1);;
Konstrukcja match-with jest tylko lukrem syntaktycznym rozwijanym do zastosowania odpowiedniej -abstrakcji.
Przykład [Rozwinięcie konstrukcji match-with]
let rec silnia x = (function 1 -> 1 | x -> x * silnia (x-1) ) x;;
Produkty kartezjańskie
Typ postaci , to produkt kartezjański. Jego elementy możemy tworzyć za pomocą konstruktora postaci. Konstruktor, to nie procedura, to coś więcej. Nie tylko działa jak procedura tworząca złożone wartości, ale jest równocześnie wzorcem pozwalającym wyłuskiwać ze złożonych wartości ich składowe elementy. Konstruktory są:
- różnowartościowe,
- różne konstruktory tego samego typu mają różne wartości,
- wszystkie konstruktory danego typu są łącznie "na",
- każdą wartość danego typu można przedstawić w postaci wyrażenia złożonego z konstruktorów i stałych innych typów.
Tak więc konstruktory mają funkcje odwrotne i dzięki temu można ich używać do budowy wzorców. Na wartościach produktów kartezjańskich jest określona równość. Dwie
-tki są są równe, jeśli ich odpowiadające sobie współrzędne są równe. Istnieje "jedynka" produktu kartezjańskiego (odpowiednik typu void), typ unit. Jedyną wartością tego typu jest ().
<wyrażenie> ::= ( [ <wyrażenie> { , <wyrażenie> }* ] )
<wzorzec> ::= ( [ <wzorzec> { , <wzorzec> }* ] )
(1, 2, 3);; let (x, s) = (4.5, "ala");; let para x y = (x, y);; let rzut_x (x, _) = x;; let rzut_y (_, y) = y;;
Listy
Listy to skończone ciągi elementów tego samego typu. Konstruktory: i , przy czym ten ostatni jest równoważny . Dostępna jest też operacja sklejania list @. Operacje :: i [] obliczają się w czasie stałym, natomiast @ w czasie proporcjonalnym do długości pierwszegoargumentu. Na listach jest określona równość. Dwie listy są równe, jeżeli są równej długości i odpowiadające sobie elementy są równe.
Przykład [Listy]
[1; 2; 3; 4];; - : int list = [1; 2; 3; 4] ["To"; "ci"; "dopiero"; "lista"];; - : string list = ["To"; "ci"; "dopiero"; "lista"] let rec length l = match l with [] -> 0 | _::t -> 1 + length t;; let rec sumuj l = match l with [] -> 0 | h::t -> h + sumuj t;; let rec listapar2paralist = function [] -> ([], []) | (x, y)::t -> let (l1, l2) = listapar2paralist t in (x :: l1, y :: l2);;
Moduł List zawiera wiele poręcznych procedur operujących nalistach.
open List;; length ["To"; "ci"; "dopiero"; "lista"];; - : int = 4 hd ["To"; "ci"; "dopiero"; "lista"];; - : string = "To" tl ["To"; "ci"; "dopiero"; "lista"];; - : string list = ["ci"; "dopiero"; "lista"] rev ["To"; "ci"; "dopiero"; "lista"];; - : string list = ["lista"; "dopiero"; "ci"; "To"] nth ["To"; "ci"; "dopiero"; "lista"] 2;; - : string = "dopiero" append [1; 2; 3] [4; 5];; - : int list = [1; 2; 3; 4; 5]
Deklaracje typów
Zwykle kompilator Ocamla sam jest w stanie wywnioskować jakiego typu są wyrażenia. Istnieje jednak możliwość nazywania typów i określania jakiego typu się spodziewamy. Wówczas kompilator sprawdza czy dane wyrażenie faktycznie jest takiego typu, jak chcieliśmy, a zamiast pełnego rozwinięcia typu może używać podanej przez nas nazwy. Niektóre typy danych, można wprowadzić tylko poprzez ich deklarację. Są to te typy, których deklaracje wprowadzają nowe konstruktory.
<jednostka kompilacji> ::= <deklaracja typu>
<deklaracja typu> ::= type <identyfikator> = <typ>
<typ> ::= int | float | char | string | unit |
<identyfikator> | <typ> list |
<typ> { * <typ> }* | ( <typ> ) | ...
Rekordy
Typy rekordowe wprowadza się deklarując typ postaci:
<typ> ::= { <identyfikator> : <typ> { ; <identyfikator> : <typ> }* }
Konstruktor wartości rekordowych ma postać:
<wyrażenie> ::= { <identyfikator> = <wyrażenie>
{ ; <identyfikator> = <wyrażenie> }* }
<wzorzec> ::= { <identyfikator> = <wzorzec>
{ ; <identyfikator> = <wzorzec> }* }
Używając takiego konstruktora do budowy wartości musimy podać wartości wszystkich pól rekordu (w dowolnej kolejności), natomiast używając go jako wzorca, możemy podać tylko interesujące nas pola. Do pojedynczych pól rekordów możemy się również odwoływać tak, jak w Pascalu, podając nazwę pola po kropce.
<wyrażenie> ::= <wyrażenie> . <identyfikator>
type ułamek = { licznik : int ; mianownik : int };;
type ulamek = { licznik : int; mianownik : int; }
let q = {licznik = 3; mianownik = 4\};;
val q : ulamek = {licznik = 3; mianownik = 4}
let {licznik = a ; mianownik = b} = q;;
val a : int = 3
val b : int = 4
let {licznik = c} = q;;
val c : int = 3
q.licznik;;
- : int = 3
Warianty
W Ocamlu istnieje również odpowiednik unii --- typy wariantowe, zwane też algebraicznymi. Deklarujemy je w następujący sposób:
<typ> ::= <wariant> { | <wariant> }*
<wariant> ::= <Identyfikator> [ of <typ> ]
Każdy zadeklarowany wariant wprowadza konstruktor o podanej nazwie. Konstruktor ten może być bezparametrowy, lub może mieć argumenty.
W Ocamlu identyfikatory rozpoczynające się wielką literą są nazwami konstruktorów, a małą nazwami wartości. Jest to konieczne ze względu na składnię wzorców. Konstruktorów typów wariantowych używamy w następujący sposób:
<wyrażenie> ::= <Identyfikator> [ <wyrażenie> ] <wzorzec> ::= <Identyfikator> [ <wzorzec> ]
Deklaracje typów wariantowych mogą być rekurencyjne, co pozwala na konstruowanie drzew. Przypomina to zdefiniowanie w Pascalu typu wskaźnikowego do typu, który jest definiowany dalej i w którym można korzystać z danego typu wskaźnikowego.
Przykład [Typy wariantowe]
type znak = Dodatni | Ujemny | Zero;; let nieujemny x = match x with Ujemny -> false | _ -> true;; type zespolone = Prostokątny of float * float | Biegunowy of float * float ;; let moduł = function Prostokątny (x, y) -> sqrt (square x +. square y) | Biegunowy (r, _) -> r;; type drzewo = Puste | Wezel of int * drzewo * drzewo;;
Deklaracje typów mogą być sparametryzowane. Jest to szczególnie przydatne wówczas, gdy nie chcemy do końca określać typu składowych elementów. Parametry typowe zapisujemy poprzedzając je apostrofem.
Przykład [Sparametryzowane deklaracje typów]
type 'a lista = Pusta | Pelna of 'a * 'a lista;;
Pelna (4, Pusta);;
- : int lista = Pelna (4, Pusta)
Pelna ("ala", Pelna("ula", Pusta));;
- : string lista = Pelna ("ala", Pelna ("ula", Pusta))
Pelna (4, Pelna ("ula", Pusta));;
error ...
Na typach wariantowych jest określona równość. Dwie wartości są równe, jeśli są wynikiem tego samego konstruktora, a jeżeli jest to konstruktor sparametryzowany, to dodatkowo odpowiadające sobie parametry konstruktora muszą być sobie równe.
Aliasy we wzorcach
Czasami, gdy używamy złożonych wzorców, chcemy równocześnie uchwycić złożoną wartość, jak i jej elementy. Możemy to zrobić za pomocą konstrukcji as.
<wzorzec> ::= <wzorzec> as <identyfikator>
let (x, y) as para = (2, 3);; val x : int = 2 val y : int = 3 val para : int * int = (2, 3) let (h::t) as lista = [1; 2; 3; 4];; val h : int = 1 val t : int list = [2; 3; 4] val lista : int list = [1; 2; 3; 4]
Wyjątki
Czasami chcemy zaprogramować w postaci procedur funkcje częściowe. W jaki sposób możemy to zrobić? Jaki powinien być wynik dla punktów spoza dziedziny? Możemy użyć tu mechanizmu wyjątków. W języku istnieje specjalny typ wariantowy exn.Jest to nietypowy typ, gdyż można na bieżąco rozszerzać zestaw wariantów tworzących ten typ. Wartości tego typu niosą informację o wyjątkowych sytuacjach uniemożliwiających wykonanie obliczeń. Nowe warianty typu exn możemy deklarować w następującysposób:
<jednostka kompilacji> ::= <deklaracja wyjątku> | ... <deklaracja wyjątku> ::= exception <wariant>
Z wyjątkami można robić dwie podstawowe rzeczy: podnosić i przechwytywać. Podniesienie wyjątku, to wyrażenie, którego obliczenie "nie udaje się", a porażce tej towarzyszy wartość podnoszonegowyjątku (typu exn).Jeśli obliczenie dowolnego podwyrażenia nie daje się na skutek podniesienia wyjątku, to tak samo nie udaje się obliczenie całego wyrażenia. Tak więc wyjątek, to rodzaj propagującego się "błędu w obliczeniach".Podniesienie wyjątku ma następującą postać, przy czym argument operacji raise musi być typu exn:
<wyrażenie> ::= raise <wyrażenie>
Przechwycenie wyjątku to konstrukcja odwrotna do jego podniesienia. Możemy spróbować obliczyć wartość danego wyrażenia, licząc się z możliwością podniesienia wyjątku. Jeśli w danym wyrażeniu zostanie podniesiony wyjątek, to możemy go przechwycić i podać, jaka powinna być wartość całego wyrażenia w takim przypadku.
<wyrażenie> ::= try <wyrażenie> with { <wzorzec> - } <wyrażenie> | }*
<wzorzec> -> <wyrażenie>
Przykład [Wyjątki]
exception Dzielenie_przez_zero of float;; let dziel x y = if y = 0.0 then raise (Dzielenie_przez_zero y) else x /. y;; let odwrotnosc x = try dziel 1.0 x with Dzielenie_przez_zero _ -> 0.0;;
Standardowo zdefiniowany jest wyjątek Failure of string oraz procedura:
let failwith s = raise (Failure s);;
Należy odróżniać wartości typu exn od podniesienia wyjątku.
Dzielenie_przez_zero 4.5;; - : exn = Dzielenie_przez_zero 4.5 raise (Dzielenie_przez_zero 4.5);; Exception: Dzielenie_przez_zero 4.5.
Przykłady ciekawych struktur danych
Kolejki fifo
[[[Uzupełnić o całkowicie funkcyjne kolejki.]]] Kolejkę fifo reprezentujemy jako trójkę: listę przednią, listę tylną i rozmiar. Trójka postaci reprezentuje kolejkę . Dodatkowo zakładamy, że jeżeli pierwsza lista jest pusta, to druga też musi być pusta. Elementy wyjmujemy z pierwszej połówki, a wkładamy do drugiej. Gdy zabraknie elementów do wyjmowania, to "przelewamy" elementy z jednej połówki do drugiej, odwracając ich kolejność.
type 'a kolejka = {front: 'a list; back: 'a list; size: int};;
let empty_queue = {front=[]; back=[]; size=0};;
let size q = q.size;;
let balance q =
match q with
{front=[]; back=[]} -> q |
{front=[]; back=b; size=s} -> {front=rev b; back=[]; size=s} |
_ -> q;;
let put {front=f; back=b; size=n} x =
balance {front=f; back=x::b; size=n+1};;
let first q =
match q with
{front=[]} -> failwith "Pusta kolejka" |
{front=x::_} -> x;;
let remove q =
match q with
{front=_::f} -> balance {front=f; back=q.back; size=q.size-1} |
_ -> empty_queue;;
Zanalizujmy koszt zamortyzowany operacji (zakładając, że pamiętamy jedną kolejkę na raz). Funkcja amortyzacji to długość drugiej listy składowej. Procedury empty, size i first mają koszt stały i nie zmieniają funkcji amortyzacji. Dla pustej kolejki funkcja amortyzacji jest równa 0. Procedura put ma koszt stały i powoduje zwiększeniefunkcji amortyzacji o 1, co daje stały koszt zamortyzowany. Procedura remove może mieć koszt liniowy, ze względu naodwracanie elementów na liście. Jednak ta ostatnia wykonuje tyle kroków, o ile zmniejsza funkcję amortyzacji. Tak więc koszt zamortyzowany procedury remove jest stały.
Zbiory skończone jako drzewa BST
Drzewa binarne możemy zadeklarować tak:
type 'a finset = Empty | Node of ('a * 'a finset * 'a finset);;
Zwróćmy uwagę, że jest to sparametryzowana deklaracja rekurencyjna. Czymkolwiek by jednak nie był parametr `a, to wszystkie węzły drzewa muszą zawierać wartości tego samego typu.
(* Wyjątek podnoszony, gdy badamy wartość spoza dziedziny. *) exception Undefined;; (* Pusty zbiór to puste drzewo *) let empty_finset = Empty;; (* Znajdź poddrzewo o zadanym kluczu *) (* (jeśli nie ma, to wynikiem jest puste drzewo). *) let rec find s e = match s with Empty -> Empty | Node (k, l, r) -> if e = k then s else if e < k then find l e else find r e;; (* Predykat charakterystyczny zbioru. *) let member s e = not (find s e = Empty);; (* Wstawienie elementu do zbioru *) let rec insert s e = match s with Empty -> Node (e, Empty, Empty) | Node (k, l, r) -> if e = k then s else if e < k then Node (k, insert l e, r) else Node (k, l, insert r e);; (* Najmniejszy element *) let rec min s = match s with Node (e, Empty, _) -> e | Node (_, l, _) -> min l | Empty -> raise Undefined;; (* Największy element *) let rec max s = match s with Node (e, _, Empty) -> e | Node (_, _, r) -> max r | Empty -> raise Undefined;; (* Usunięcie elementu z listy *) let rec remove s e = match s with Empty -> s | Node (k, l, r) -> if e = k then match (l, r) with (Empty, Empty) -> Empty | (Empty, _) -> let m = min r in Node (m, l, remove r m) | _ -> let m = max l in Node (m, remove l m, r) else if e < k then Node (k, remove l e, r) else Node (k, l, remove r e);;
