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 narazie w stanie definiować złożonych danych. Zajmiemy się tym w poniższym wykładzie. Zajmiemy się również metodyką tworzenia nowych typów danych.

Pojęcie typu danych jest zapewne dobrze znane Czytelnikowi z innych języków programowania. Spróbujmy jednak, dla porządku, krótko scharakteryzować to pojęcie. Typ danych to zbiór wartości wraz z zestawem podstawowych operacji na tych wartościach.

W każdym języku programowania dostępna jest pewna liczba wbudowanych typów danych, takich jak liczby całkowite, wartości logiczne itp. Są one nazywane typami prostymi. Oprócz typów prostych mamy typy złożone, które zawierają w sobie prostsze typy. W tym wykładzie poznamy różne konstrukcje pozwalające na tworzenie rozmaitych typów złożonych.

Typy wbudowane

Poznaliśmy już kilka podstawowych typów danych wbudowanych w język Ocaml wraz z operacjami na nich. Są to: bool, int, float, char i string.

W Ocamlu środowisko przyporządkowuje każdej nazwie stałej jej wartość, która jest określonego typu. Dotyczy to również nazwanych procedur i w ich przypadku oznacza, że wiadomo jakiego typu są argumenty i wynik. W szczególności operacje arytmetyczne na liczbach całkowitych i zmiennopozycyjnych muszą mieć różne nazwy, gdyż ich argumenty są różnych typów. Operacje arytmetyczne na liczbach całkowitych zapisujemy w klasyczny sposób: +, *, itd., a operacje na liczbach zmiennopozycyjnych mają dodaną w nazwie kropkę: +., *. itd. Niestety, zapewne na początku często będą się zdarzać błedy wynikające z mylenia tych operacji.

Konstruktory

Konstruktory to szczególnego rodzaju operacje tworzące wartości określonych typów złożonych. Jednak konstruktor to nie tylko procedura tworząca złożoną wartość, to coś więcej. Dodatkowo są one odwracalne, tzn. z ich wyniku można jednoznacznie odtworzyć ich argumenty. Dzięki temu konstruktory nie tylko służą do tworzenia wartości typów złożonych, ale również do rozbijania ich na tworzące je wartości typów prostszych.

Formalnie, konstruktory (wartości określonego typu) mają następujące własności:

• są one różnowartościowe,
• różne konstruktory wartości tego samego typu mają różne wartości, tzn. przeciwdziedziny różnych konstruktorów są rozłączne,
• wszystkie konstruktory wartości danego typu są łącznie "na", tzn. każdą wartość danego typu można skonstruować,
• każdą wartość danego typu można przedstawić w postaci wyrażenia złożonego z konstruktorów i stałych innych typów.

Na razie nie znamy jeszcze żadnych konstruktorów. Zostaną one przedstawione dalej, wraz z kolejnymi typami złożonymi. Wówczas zobaczymy przykłady ich użycia.

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". Do budowy wzorców możemy używać konstruktorów i identyfikatorów. Wzorce pojawiają się w takich kontekstach, że zawsze dopasowywana jest do nich wartość pewnego wyrażenia. Identyfikatory występujące we wzorcach są nazwami nowych stałych wprowadzanych do środowiska. Jeśli wartość wyrażenia dopasowywanego do wzorca "pasuje", to występującym we wzorcu identyfikatorom przypisywane są w środowisku wartości odpowiadających im składowych dopasowywanej wartości. 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 wartości złożonych typów, jednak ich zastosowanie nie ogranicza się tylko do tego.

Przedstawiając kolejne typy złożone będziemy przedstawiać również towarzyszące im konstruktory i wzorce. Istnieje jednak kilka podstawowych wzorców, które mogą być używane dla wartości dowolnego typu:

<wzorzec> ::= <identyfikator> | _ | <stała> | ...

• identyfikator -- pasuje do każdej wartości, nazwie przyporządkowywana jest dopasowywana wartość,
• _ -- tak jak identyfikator, tylko nie wprowadza żadnej nowej nazwy,
• stała (np. liczbowa) -- pasuje tylko do samej siebie.

Wzorca _ używamy wówczas, gdy interesuje nas sam fakt, że wartość pasuje do wzorca, a nie chcemy wprowadzać do środowiska nowych nazw.

Wzorców możemy używać w wyrażeniach match ... with ... oraz w definicjach procedur (zarówno nazwanych, jak i $\lambda$-abstrakcji):

<definicja> ::= let <wzorzec> = <wyrażenie> |
                let [rec] <identyfikator> {<wzorzec>}* = <wyrażenie> 
<wyrażenie> ::= match <wyrażenie> with { <wzorzec> -> <wyrażenie> | }* <wzorzec> -> <wyrażenie>  |
                function { <wzorzec> -> <wyrażenie> | }* <wzorzec> -> <wyrażenie> 

Najprostsze zastosowanie wzorców to definicje stałych. Po lewej stronie = możemy mieć zamiast identyfikatora wzorzec. Wartość wyrażenia po prawej stronie = jest dopasowywana do wzorca, a wszystkie identyfikatory, którym w ten sposób są przypisywane wartości, trafiają do środowiska.

Przykład [Wzorce w definicjach stałych]

3;;
- : int = 3
 
let _ = 3;;
- : int = 3
 
let a = 42;;
val a : int = 42

W definicjach procedur nazwa procedury musi być identyfikatorem, ale parametry formalne mogą być wzorcami. Wówczas, w momencie wywołania procedury wartości argumentów są dopasowywane do parametrów formalnych. Wszystkie identyfikatory, którym w ten sposób są przypisywane wartości, trafiają do tymczasowego środowiska powstającego dla obliczenia wartości procedury.

Przykład [Wzorce jako argumenty procedur]

let f 6 9 = 42;;
val f : int -> int -> int
 
f 6 9;;
- : int = 42
 
let p x _ = x + 1;;
val p : int -> 'a -> int = <fun>
 
p 6 9;;
- : int = 7

W wyrażeniach match ... with ... wartość wyrażenia występującego po match jest dopasowywana do kolejnych wzorców. Wzorzec, do którego ta wartość pasuje, wskazuje równocześnie wyrażenie, którego wartość jest wartością całego wyrażenia match ... with .... Jeśli dopasowywana wartość pasuje do kilku wzorców, to wybierany jest pierwszy z nich. Jeżeli nie pasuje ona do żadnego z wzorców, to zgłaszany jest błąd (wyjątek).

Podobnie działa dopasowywanie wzorców w $\lambda$-abstrakcjach. Argument procedury jest dopasowywany do kolejnych wzorców. Wzorzec, do którego wartość argumentu pasuje wskazuje równocześnie wyrażenie, którego wartość jest wynikiem procedury. Jeśli wartość argumentu pasuje do kilku wzorców, to wybierany jest pierwszy z nich. Jeżeli nie pasuje ona do żadnego z wzorców, to zgłaszany jest błąd (wyjątek).

Przykład [Konstrukcja match-with]

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);;

Wyrażenie match-with jest tylko lukrem syntaktycznym rozwijanym do zastosowania odpowiedniej $\lambda$-abstrakcji. Ilustruje to poniższy przykład.

Przykład [Rozwinięcie match-with]

Konstrukcja match-with z poprzedniego przykładu jest rozwijana w następujący sposób:

let rec silnia x =
  (function 
    1 -> 1 |
    x -> x * silnia (x-1)
  ) x;;

Produkty kartezjańskie

Produkt kartezjański jako typ jest dokładnie tym, czym jest w matematyce. Jest to zbiór par, lub ogólniej $n$-tek wartości prostszych typów. Produkt kartezjański typów $t_1,\dots ,t_n$ jest oznaczany przez $t_1*\dots *t_n$. Każdemu typowi produktowemu towarzyszy jeden konstruktor postaci: $(x_1,\dots ,x_n)$. Wartością takiego konstruktora jest $n$-tka podanych wartości. Na wartościach produktów kartezjańskich jest określona równość. Dwie $n$-tki są są równe, jeśli ich odpowiadające sobie współrzędne są równe.

<wyrażenie> ::= ( [ <wyrażenie> { , <wyrażenie> }* ] ) 
<wzorzec>   ::= ( [ <wzorzec> { , <wzorzec> }* ] )

Przykład [Produkty kartezjańskie]

(1, 2, 3);;
- : int * int * int = (1, 2, 3)
 
(42, (6.9, "ala"));;
- : int * (float * string) = (42, (6.9, "ala"))
 
let (x, s) = (4.5, "ala");;
val x : float = 4.5
val s : string = "ala"
 
let fib n =
  let rec fibpom n =
    if n = 0 then
      (0, 1)
    else
      let (a, b) = fibpom (n - 1)
      in (b, a + b)
  in
    let (a, b) = fibpom n
    in a;;
val fib : int -> int = <fun>
 
let para x y = (x, y);;
val para : 'a -> 'b -> 'a * 'b = <fun>

let rzut_x (x, _) = x;;
val rzut_x : 'a * 'b -> 'a = <fun>

let rzut_y (_, y) = y;;
val rzut_y : 'a * 'b -> 'b = <fun>

Produkt kartezjański nie jest łączny, tzn. poniższe wyrażenia są różnych typów:

(2, 3, 4);;
- : int * int * int = (2, 3, 4)
 
(2, (3, 4));;
- : int * (int * int) = (2, (3, 4))
 
((2, 3), 4);;
- : (int * int) * int = ((2, 3), 4)

Jednoelementowe $n$-tki wartości typu $t$ to po prostu wartości typu $t$, $(x)=x$. Istnieje "jedynka" produktu kartezjańskiego (odpowiednik typu void), typ unit. Jedyną wartością tego typu jest (). Jednak t * unit to inny typ niż t.

Listy

Listy to ciągi elementów tego samego typu (skończone lub nieskończone, ale od pewnego miejsca okresowe). Typ listy elementów typu t oznaczamy przez t list. Pierwszy element listy przyjęło się nazywać głową, a listę złożoną z wszystkich pozostałych elementów listy przyjęło się nazywać ogonem. Tak więc każda niepusta lista (tak jak wąż ;-) składa się z głowy i ogona.

Typowi listowemu towarzyszą dwa konstruktory: h::t i []. [] to konstruktor listy pustej, a h::t tworzy listę, której głową jest h, a ogonem jest t.

Chcąc podać listę $n$ elementową nie musimy pisać: $x_1::(x_2::\dots ::(x_n::[])\dots )$, lecz możemy użyć skrótu notacyjnego: $[x_1;x_2;\dots ;x_n]$. Dostępna jest też operacja sklejania list @. Należy pamiętać, że operacje :: i [] obliczane są w czasie stałym, natomiast @ w czasie proporcjonalnym do długości pierwszego argumentu.

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]

[];;
- : 'a list = []
 
1::2::3::[];;
- : int list = [1; 2; 3]
 
[1; 2; 3; 4];;
- : int list = [1; 2; 3; 4]
 
[1;2;3] @ [4;5;6];;
- : int list = [1; 2; 3; 4; 5; 6]
 
["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);;

Możliwe jest definiowanie list nieskończonych. Należy jednak zdawać sobie sprawę, że listy są implementowane jako wskaźnikowe listy jednokierunkowe. Dlatego też lista nieskończona może mieć co najwyżej postać cyklu z "ogonkiem". Poniższy przykład pokazuje jak definiować listy nieskończone. Pokazuje on również, że nie tylko procedury mogą być obiektami definiowanymi rekurencyjnie.

Przykład [Definicje list nieskończonych]

let rec jedynki = 1::jedynki;;
val jedynki : int list = [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; ...]
 
let rec cykl = 1 :: 0 :: -1 :: 0 :: cykl;;
val cykl : int list = [1; 0; -1; 0; 1; 0; -1; 0; ...]
 
[1;2;3] @ cykl;;
- : int list = [1; 2; 3; 1; 0; -1; 0; 1; 0; -1; 0; ...]
 
cykl @ [1;2;3];;
Stack overflow during evaluation (looping recursion?).

Moduł List zawiera wiele poręcznych procedur operujących na listach. O modułach będziemy mówić dokładniej w jednym z wykładów. W tej chwili wystarczy nam wiedzieć, że aby korzystać z pojęć zdefiniowanych w module List, wystarczy wprowadzić polecenie open List;; lub przed każdą nazwą pojęcia dodać przedrostek postaci List. Moduł ten implementuje m.in. następujące operacje:

• length -- oblicza długość listy (uwaga: działa w czasie proporcjonalnym do długości listy),
• hd -- zwraca głowę (niepustej) listy,
• tl -- zwraca ogon (niepustej) listy,
• rev -- oblicza listę złożoną z tych samych elementów, ale w odwrotnej kolejności (uwaga: działa w czasie proporcjonalnym do długości listy),
• nth -- zwraca element z podanej pozycji na liście (głowa ma numer 0, uwaga: działa w czasie proporcjonalnym do numeru pozycji plus 1),
• append -- sklejanie list, działa tak jak @, ale nie jest zapisywane infiksowo, tylko tak, jak zwykła procedura.

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"]

List.rev ["To"; "ci"; "dopiero"; "lista"];;
- : string list = ["lista"; "dopiero"; "ci"; "To"]

nth ["To"; "ci"; "dopiero"; "lista"] 2;;
- : string = "dopiero"

List.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 krótszej nazwy. Niektóre typy danych można wprowadzić tylko poprzez ich deklarację. Są to te typy, których deklaracje wprowadzają nowe konstruktory.

Możliwe jest też zdefiniowanie typów sparametryzowanych, tzn. takich, w których typy niektórych ich składowych są podawane jako parametry typu. Elementy struktury danych określone jako parametry mogą być dowolnego typu, ale wszystkie elementy określone przez ten sam parametr muszą być (w danej wartości) tego samego typu. (Uważny czytelnik zapewne domyśla się, że przykładem typu sparametryzowanego jest lista. Parametrem typu listowego jest typ elementów listy.) Parametry typu podajemy zwyczajowo przed nazwą typu sparametryzowanego, np. int list.

<jednostka kompilacji> ::= <deklaracja typu> 
<deklaracja typu>      ::= type <identyfikator> = <typ> | type <parametr typowy> <identyfikator> = <typ> | 
                           type ( <parametr typowy> {, <parametr typowy>}* ) <identyfikator> = <typ> 
<typ>                  ::= <identyfikator> | <typ> <identyfikator> | ( <typ> {, <typ>}* ) <identyfikator> | 
                           <typ> { * <typ> }* | ( <typ> ) | ...
<parametr typowy>      ::= '<identyfikator>

Przykład [Deklaracje typów]

type p = int * float;;
type p = int * float
 
type 'a lista = 'a list;;
type 'a lista = 'a list
 
type ('a, 'b) para = 'a * 'b;;
type ('a, 'b) para = 'a * 'b
 
type 'a t = ('a, 'a) para * ('a list) list;;
type 'a t = ('a, 'a) para * 'a list list

Podstawowym zastosowaniem deklaracji typów (oprócz wprowadzania typów, które wymagają zadeklarowania) jest definiowanie typów złożonych, które występują w interfejsach procedur. Wówczas można podać, iż oczekujemy, że dany argument powinien być określonego typu. W ogólności można dla dowolnego wzorca lub wyrażenia podać typ, jakiego oczekujemy.

<wyrażenie> ::= ( <wyrażenie> : <typ> )
<wzorzec>   ::= ( <wzorzec> : <typ> )

Przykład [Specyfikacja typów]

type point = float * float;;
type point = float * float
 
type vector = point;;
type vector = point
 
let (p:point) = (2.0, 3.0);;
val p : point = (2., 3.)
 
let shift ((x, y): point) ((xo, yo): vector) = 
  ((x +. xo, y +. yo) : point);;
val shift : point -> vector -> point = <fun>
 
shift p p;;
- : point = (4., 6.)

Rekordy

Typy rekordowe są podobne do produktów kartezjańskich. Rekord odpowiada $n$-tce, ale współrzędne (tzw. pola rekordu) są identyfikowane raczej po nazwie, a nie wg. pozycji w $n$-tce. Typy rekordowe występują w wielu językach programowania -- w C i C++ są nazywane strukturami. Typy rekordowe wprowadza się deklarując typ postaci:

<typ> ::= { <identyfikator> : <typ> { ; <identyfikator> : <typ> }* }

Identyfikatory to nazwy pól rekordów. 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 rekordu musimy podać wartości wszystkich pól (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 innych językach programowania, podając nazwę pola po kropce.

<wyrażenie> ::= <wyrażenie> . <identyfikator>

Przykład [Rekordy]

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

Uwaga

Ze względu na przysłanianie nazw, należy unikać sytuacji, gdy dwa pola różnych typów rekordowych mają takie same nazwy. Wówczas będziemy mogli korzystać tylko z tego pola, które zostało zdefiniowane jako ostatnie.

Warianty

W Ocamlu istnieje również odpowiednik unii -- typy wariantowe, zwane też typami algebraicznymi. Deklarujemy je w następujący sposób:

<typ>     ::= <wariant> { | <wariant> }* 
<wariant> ::= <Identyfikator> [ of <typ> ]

Uwaga

Przez <Identyfikator> oznaczamy identyfikatory rozpoczynające się wielką literą. Natomiast <identyfikator> oznacza identyfikatory rozpoczynające się małą literą.

Jak zobaczymy za chwilę, rozróżnienie to jest konieczne dla odróżnienia we wzorcach nazw konstruktorów od nazw wprowadzanych stałych.

Każdy zadeklarowany wariant wprowadza konstruktor o podanej nazwie. Konstruktor ten może być bezparametrowy lub może mieć argumenty. Formalnie konstruktor taki może mieć co najwyżej jeden argument, ale zawsze może to być argument odpowiedniego typu produktowego. Konstruktorów typów wariantowych używamy w następujący sposób:

<wyrażenie> ::= <Identyfikator> [ <wyrażenie> ] 
<wzorzec>   ::= <Identyfikator> [ <wzorzec> ]

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 parametry konstruktora muszą być sobie równe.

Przykład [Typy wariantowe]

type znak = Dodatni | Ujemny | Zero;;
type znak = Dodatni | Ujemny | Zero
  
let nieujemny x =
  match x with
    Ujemny -> false |
    _      -> true;;
val nieujemny : znak -> bool = <fun>
  
let ujemny x = 
  x = Ujemny;;
val ujemny : znak -> bool = <fun>
 
type zespolone =
  Prostokatny of float * float |
  Biegunowy of float * float ;;
type zespolone = Prostokatny of float * float | Biegunowy of float * float
  
let modul =
  function
    Prostokatny (x, y) -> sqrt (square x +. square y) |
    Biegunowy (r, _)   -> r;;
val modul : zespolone -> float = <fun>

Deklaracje typów wariantowych mogą być rekurencyjne, co pozwala na konstruowanie drzew.

Przykład [Deklaracja drzew]

type drzewo =
  Puste |
  Wezel of int * drzewo * drzewo;;
type drzewo = Puste | Wezel of int * drzewo * drzewo

Podobnie jak w przypadku list, możemy tworzyć "nieskończone" drzewa poprzez ich zacyklenie.

Przykład [Zacyklone drzewa]

let rec t = Wezel (42, t, Puste);;
val t : drzewo = Wezel (42, Wezel (42, (...), Puste),Puste)

Deklaracje typów wariantowych mogą być sparametryzowane. Jest to szczególnie przydatne wówczas, gdy nie chcemy do końca określać typu składowych elementów.

Przykład [Sparametryzowane deklaracje typów]

type 'a lista = Pusta | Pelna of 'a * 'a lista;;
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 ...

Aliasy we wzorcach

Czasami, gdy używamy złożonych wzorców, chcemy zarówno uchwycić złożoną wartość, jak i jej elementy. Możemy to zrobić za pomocą konstrukcji as.

<wzorzec> ::= <wzorzec> as <identyfikator>      

Dopasowywana wartość jest przypisywana identyfikatorowi po prawej stronie as oraz jest dopasowywana do wzorca po lewej stronie.

Przykład [Użycie as we wzorcach]

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ący sposó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ść podnoszonego wyjątku (typu exn). Jeśli obliczenie dowolnego podwyrażenia nie udaje 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;;
exception Dzielenie_przez_zero of float
 
let dziel x y =
  if y = 0.0 then
    raise (Dzielenie_przez_zero y)
  else x /. y;;
val dziel : float -> float -> float = <fun>
 
let odwrotnosc x =
  try
    dziel 1.0 x
  with
    Dzielenie_przez_zero _ -> 0.0;;
val odwrotnosc : float -> float = <fun>
 
odwrotnosc 42.;;
- : float = 0.0238095238095238082
 
odwrotnosc 0.0;;
- : float = 0.

Standardowo zdefiniowany jest wyjątek Failure of string oraz procedura:

let failwith s =
  raise (Failure s);;

Pamiętajmy, że 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.

Uwaga

W niektórych źródłach wyjątki są opisane jako konstrukcja imperatywna. Proszę jednak zwrócić uwagę, że nie odwołują się one do takich pojęć, jak zmienne, obiekty, stany, czy przypisanie.

Dlatego też wyjątki są tu przedstawione jako mechanizm funkcyjny.

Przykłady ciekawych struktur danych

Kolejki FIFO

Kolejka FIFO (ang. first in, first out) to taka kolejka, do której możemy wkładać elementy na koniec i wyjmować elementy z początku. Dodatkowo możemy podglądać jaki element jest pierwszy w kolejce. Kolejkę fifo reprezentujemy jako trójkę:

• listę, którą będziemy nazywać "przednią",
• listę, którą będziemy nazywać "tylną" i
• liczba elementów w kolejce.

Lista przednia

$[x_1;\dots ;x_k]$

, lista tylna

$[y_1;\dots ;y_l]$

reprezentują kolejkę zawierającą

$k+l$

elementów:

$x_1,\dots ,x_k,y_l,\dots ,y_1$

. Tak więc każdy element w kolejce występuje na jednej z list, wszystkie elementy z listy przedniej poprzedzają elementy z listy tylnej, elementy na liście przedniej występują zgodnie z kolejnością w kolejce, a na liście tylnej w odwrotnej kolejności. Dodatkowo zakładamy, że jeżeli lista przednia jest pusta, to tylna też musi być pusta. Wyjmując element z kolejki, wyjmujemy go z listy przedniej, a wkładając, wkładamy do tylnej. Gdy zabraknie elementów do wyjmowania, "przelewamy" elementy z listy tylnej do przedniej, odwracając ich kolejność na liście.

type 'a kolejka = {front: 'a list; back: 'a list; size: int};;
type 'a kolejka = { front : 'a list; back : 'a list; size : int; }
  
let empty_queue = {front=[]; back=[]; size=0};;
val empty_queue : 'a kolejka = {front = []; back = []; size = 0}
  
let size q = q.size;;
val size : 'a kolejka -> int = <fun>
  
let balance q = 
  match q with
    {front=[]; back=[]}        -> q |
    {front=[]; back=b; size=s} -> {front=List.rev b; back=[]; size=s} | 
    _                          -> q;;
val balance : 'a kolejka -> 'a kolejka = <fun>
  
let put {front=f; back=b; size=n} x =
  balance {front=f; back=x::b; size=n+1};; 
val put : 'a kolejka -> 'a -> 'a kolejka = <fun>
  
let first q = 
  match q with
    {front=[]}   -> failwith "Pusta kolejka" |
    {front=x::_} ->  x;;
val first : 'a kolejka -> 'a = <fun>
  
let remove q =
  match q with
    {front=_::f} -> balance {front=f; back=q.back; size=q.size-1}  |
    _            -> empty_queue;;
val remove : 'a kolejka -> 'a kolejka = <fun>

Operacja balance zapewnia, że jeżeli kolejka nie jest pusta, to jej lista przednia nie jest pusta. Zanalizujmy koszt operacji na kolejkach (zakładając, że pamiętamy jedną kolejkę na raz). Pomijając koszt procedury balance, wszystkie operacje na kolejce mają koszt stały. Pokażemy, że koszt zamortyzowany procedury balance jest też stały.

Jako funkcję amortyzacji przyjmujemy długość listy tylnej. Dla pustej kolejki funkcja amortyzacji jest równa 0. Procedura put ma koszt rzeczywisty stały i powoduje zwiększenie funkcji amortyzacji o 1, co daje stały koszt zamortyzowany. Procedura remove może mieć koszt rzeczywisty liniowy ze względu na odwracanie elementów z listy tylnej. Jednak równocześnie zmniejsza ona funkcję amortyzacji do 0, czyli o tyle, ile trwa odwracanie listy. Tak więc koszt zamortyzowany procedury remove jest stały.

Zbiory skończone jako drzewa BST

Poniżej przedstawiamy implementację drzew BST. Typ reprezentujący drzewa binarne możemy zadeklarować nastepująco:

type 'a finset = Empty | Node of ('a  * 'a finset * 'a finset);;
type 'a finset = Empty | Node of ('a * 'a finset * 'a finset)

Zwróćmy uwagę, że jest to sparametryzowana deklaracja rekurencyjna. Czymkolwiek by był parametr `a, wszystkie węzły drzewa muszą zawierać wartości tego samego typu.

(* Wyjątek podnoszony, gdy badamy wartość spoza dziedziny. *)
exception Undefined;;
exception Undefined

(* Pusty zbiór to puste drzewo *)
let empty_finset = Empty;;
val empty_finset : 'a 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;;
val find : 'a finset -> 'a -> 'a finset = <fun>

(* Predykat charakterystyczny zbioru. *)
let member s e = not (find s e = Empty);;
val member : 'a finset -> 'a -> bool = <fun>

(* 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);;
val insert : 'a finset -> 'a -> 'a finset = <fun>

(* Najmniejszy element *)
let rec min s =
  match s with
    Node (e, Empty, _) -> e |
    Node (_, l, _)     -> min l |
    Empty              -> raise Undefined;; 
val min : 'a finset -> 'a = <fun>

(* Największy  element *)
let rec max s =
  match s with
    Node (e, _, Empty) -> e |
    Node (_, _, r)     -> max r |
    Empty              -> raise Undefined;;
val max : 'a finset -> 'a = <fun>

(* 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);;
val remove : 'a finset -> 'a -> 'a finset = <fun>

Ćwiczenia

Ćwiczenia