Programowanie funkcyjne/Funktory

Wstęp

Zwykle jedne moduły korzystają z innych modułów. Zgodnie z zasadą ukrywania informacji (ang. information hiding), istotne powinny być jedynie specyfikacje wykorzystywanych modułów, a nie ich konkretne implementacje. Podstawienie dowolnej implementacji o zadanej sygnaturze i spełniającej zadaną specyfikację powinno być akceptowalne z punktu widzenia modułów korzystających z takiej implementacji.

Skoro rozdzieliliśmy pojęcia interfejsu (sygnatury) i implementacji (struktury), to możemy zapisywać moduły korzystające z innych modułów w bardziej abstrakcyjny sposób. Zamiast określać dokładnie z jakiej implementacji korzysta dany moduł, określamy jedynie jej sygnaturę (i przez domniemanie również specyfikację). Otrzymujemy w ten sposób funktory.

Funktory to moduły sparametryzowane. Ich parametrami są struktury o określonych sygnaturach, z których mają one korzystać. Dopiero gdy podstawimy w miejsce parametrów konkretne struktury, otrzymujemy strukturę implementowaną przez funktor.

Zwykłe moduły (struktury) tworzą statyczną sieć powiązań. Natomiast moduły są jak wymienne elementy, klocki, które możemy łączyć na rozmaite sposoby.

Na funktory możemy też patrzeć jak na funkcje na strukturach --- przetwarzają one struktury-parametry w struktury wynikowe. Należy jednak pamiętać, że podstawianie parametrów funktorów dokonuje się w sposób statyczny -- w czasie kompilacji.

Proste funktory

Tak samo jak w przypadku struktur, w przypadku funktorów mamy pojęcie sygnatury. Sygnatura funktora określa sygnaturę parametrów oraz sygnaturę wyniku.

<sygnatura> ::= functor ( <Identyfikator> : <sygnatura> ) -> <sygnatura>
<struktura> ::= functor ( <Identyfikator> : <sygnatura> ) -> <struktura>  |
                <struktura> ( <struktura )

Jeżeli funktor ma więcej niż jeden parametr, to tak jak w przypadku procedur, zapisujemy go jako funktor z pierwszym parametrem, którego wynikiem jest funktor z drugim parametrem itd. Z powyższej składni widać też, że funktory mogą być nie tylko wynikiem, ale i parametrami funktorów, czyli mamy funktory wyższych rzędów. Zajmiemy się nimi dalej.

Przykład [Kolejka priorytetowa]

Przypuśćmy, że chcemy zaimplementować kolejkę priorytetową elementów bliżej nieokreślonego typu. Na elementach kolejki musi być określony porządek liniowy, zgodnie z którym będziemy szeregować elementy w kolejce. Kolejkę zaimplementujemy w postaci funktora. Parametrem funktora będzie struktura określająca typ elementów i porządek liniowy na nich.

type porownanie = Mniejsze | Rowne | Wieksze;;

module type PORZADEK_LINIOWY = 
  sig
    type t                                 (* Typ elementów.    *)
    val porownaj : t -> t -> porownanie    (* Porządek liniowy. *)
  end;;
     

Kolejka priorytetowa powinna mieć sygnaturę postaci:

module type PRI_QUEUE_FUNC = functor (Elem : PORZADEK_LINIOWY) -> 
  sig
    exception EmptyQueue
    type elem = Elem.t                (* Typ elementów.                    *)
    type queue                        (* Typ kolejki.                      *)
    val empty : queue                 (* Pusta kolejka.                    *)
    val put : elem -> queue -> queue  (* Wstawienie do kolejki.            *)
    val min : queue -> elem           (* Element najmniejszy.              *)
    val removemin : queue -> queue    (* Usunięcie elementu najmniejszego. *)
  end;;

Zwróćmy uwagę na to, że typ queue jest abstrakcyjny. Ukrywamy w ten sposób strukturę kolejki. Zwróćmy też uwagę na to, że typ elem jest określony jako Elem.t. Jest to specyficzna konstrukcja. Przy jej zastosowaniu, cokolwiek będzie wiadome o typie Elem.t, będzie również wiadome o typie elem, mimo że w sygnaturze PORZADEK_LINIOWY typ t jest typem abstrakcyjnym. Implementację kolejki priorytetowej możemy zrealizować w następujący sposób:

module PriQueue : PRI_QUEUE_FUNC =
  functor (Elem : PORZADEK_LINIOWY) -> 
  struct
    type elem = Elem.t
    exception EmptyQueue
    type queue = elem list
    let empty = []
    let rec put x q = 
      match q with 
        [] -> [x] |
        h::t -> if Elem.porownaj x h = Mniejsze then 
          x :: q
        else
          h::(put x t)
    let min q =
      match q with 
        [] -> raise EmptyQueue |
        h::_ -> h
    let removemin (q:queue) = 
      match q with 
        [] -> raise EmptyQueue |
        _::t -> t
  end;;

Kolejka priorytetowa liczb całkowitych może być zrealizowana poprzez podstawienie jako argumentu funktora następującej struktury:

module IntOrder = 
  struct
    type t = int
    let porownaj (x:int) (y:int) = 
      if x < y then Mniejsze else
      if x > y then Wieksze else Rowne
  end;;
  
module IntQueue = PriQueue (IntOrder);;

IntQueue.min (IntQueue.put 42 IntQueue.empty);;
- : IntQueue.elem = 42

Zwróćmy uwagę, że nie ograniczamy struktury IntOrder do sygnatury PORZADEK_LINIOWY. Chcemy, aby typ t nie był typem abstrakcyjnym, lecz był równoważny int. Dzięki temu będzie wiadomo, że elementy kolejki są również typu int.

Dla porównania spójrzmy na poniższy przykład. Jest to definicja modułu, którego nie da się używać, gdyż typ elementów jest abstrakcyjny i nie jesteśmy w stanie utworzyć jakiegokolwiek elementu.

module SomeOrder : PORZADEK_LINIOWY = 
  struct
    type t = int
    let porownaj (x:int) (y:int) = 
      if x < y then Mniejsze else
      if x > y then Wieksze else Rowne
  end;;

module SomeQueue = PriQueue (SomeOrder);;

SomeQueue.min (SomeQueue.put 42 SomeQueue.empty);;
This expression has type int but is here used with type SomeQueue.elem = SomeOrder.t

Przykład [Sortowanie]

Innym podstawowym pojęciem związanym z porządkami liniowymi jest sortowanie. Również możemy je zapisać w postaci funktora sparametryzowanego porządkiem liniowym.

module type SORTING = functor (Elem : PORZADEK_LINIOWY) -> 
  sig
    type elem = Elem.t                    (* Typ elementów.                       *)
    val sortuj : elem list -> elem list   (* Procedura sortująca listy elementów. *)
  end;;

Jeden z możliwych algorytmów sortowania to heap-sort. Możemy go zapisać w postaci funktora sparametryzowanego implementacją kolejek priorytetowych.

module HeapSort (PrQ : PRI_QUEUE_FUNC): SORTING = 
  functor (Elem : PORZADEK_LINIOWY) -> 
    struct
      type elem = Elem.t
      module PQ = PrQ (Elem)
      open PQ
      let rec wkladaj l =
        List.fold_left (fun h x -> put x h) empty l
      let rec wyjmuj q a = 
        if q = empty then 
          List.rev a 
        else
          wyjmuj (removemin q) (min q :: a)
      let sortuj l = wyjmuj (wkladaj l) []
    end;;
  
module Sortowanie = HeapSort (PriQueue);;
  
module S = Sortowanie (IntOrder);;
  
S.sortuj [1;7;3;6;5;2;4;8];;
- : S.elem list = [1; 2; 3; 4; 5; 6; 7; 8]

Możliwy jest również taki zapis:

module Sort = HeapSort (PriQueue) (IntOrder);;
 
Sort.sortuj [1;7;3;6;5;2;4;8];;
- : Sort.elem list = [1; 2; 3; 4; 5; 6; 7; 8]

Funktory wyższych rzędów

Tak jak istnieją procedury wyższych rzędów, istnieją również funktory wyższych rzędów. Są to funktory, których parametrami i/lub wynikiem są funktory. Oto przykład, stanowiący kontynuację przykładu z poprzedniego punktu:

Przykład [Mediana]

Jeden ze sposobów wyznaczania mediany ciągu (nie najbardziej efektywny, ale za to prosty) polega na posortowaniu ciągu i wybraniu elementu środkowego. Taki algorytm możemy zapisać w postaci funktora sparametryzowanego algorytmem sortowania i porządkiem liniowym. (Zauważmy, że sortowanie jest tu również funktorem.)

module type MEDIANA = 
  functor (Elem : PORZADEK_LINIOWY) -> 
    sig
      type elem = Elem.t
      exception PustaLista
      val mediana : elem list -> elem
    end;;
  
module Mediana : functor (Sort : SORTING) -> MEDIANA = 
  functor (Sort : SORTING) -> 
    functor (Elem : PORZADEK_LINIOWY) -> 
      struct
        type elem = Elem.t
        exception PustaLista
        module S = Sort (Elem)
        let mediana l = 
          let s = S.sortuj l
          and n = List.length l
          in 
            if n = 0 then 
              raise PustaLista 
            else 
              List.nth s (n / 2)
      end;;
  
module M = Mediana (HeapSort (PriQueue)) (IntOrder);;
  
M.mediana [4;3;5;6;2;1;7];;

Jak widać z powyższego przykładu, jeżeli będziemy zapisywać moduły w postaci funktorów, to będziemy z nich tworzyć łatwo wymienne elementy. Tworząc funktory wyższych rzędów, zwiększamy naszą elastyczność i możemy łączyć rozmaite algorytmy i struktury danych w praktycznie dowolne kombinacje.

Ćwiczenia

Ćwiczenia