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 tym 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.

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. Konstruktory, to szczególnego rodzaju operacje, które są odwracalne, tzn. z ich wyniku można jednoznacznie odtworzyć ich argumenty. Przykłady konstruktorów przedstawimy dalej. 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 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]

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

Typ postaci $t_{1} * \dots * t_{n}$ , to produkt kartezjański. Jego elementy możemy tworzyć za pomocą konstruktora postaci $(x_{1}, \dots, x_{n})$ . 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

n

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

Uwaga

Wartości (1, 2, 3), ((1, 2), 3) i (1, (2, 3)) są różnych typów.

Listy

Listy to skończone ciągi elementów tego samego typu. Konstruktory: $h : : t$ i $[x_{1}; x_{2}; \dots; x_{n}]$ , przy czym ten ostatni jest równoważny $x_{1} : : (x_{2} : : \dots : : (x_{n} : : []) \dots)$ . 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

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, które zostało zdefiniowane jako ostatnie.

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.

Uwaga

<Identyfikator> to identyfikator rozpoczynający się wielką literą.

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.

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. Uważam więc, że wyjątki, tak jak są one zrealizowane w Ocamlu, są mechanizmem funkcyjnym.

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 $([x_{1}; \dots; x_{k}], [y_{1}; \dots; y_{l}], k + l)$ reprezentuje kolejkę $x_{1}, \dots, x_{k}, y_{l}, \dots, y_{1}$ . 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);;

Laboratoria i ćwiczenia

Laboratoria i ćwiczenia do wykładu

Programowanie funkcyjne/Struktury danych

Spis treści

Wstęp

Typy wbudowane

Wzorce

Produkty kartezjańskie

Listy

Deklaracje typów

Rekordy

Warianty

Aliasy we wzorcach

Wyjątki

Przykłady ciekawych struktur danych

Kolejki fifo

Zbiory skończone jako drzewa BST

Laboratoria i ćwiczenia

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia