Co to jest moduł pierwszego rodzaju?
Zadanie 2 (8p.)
Rozważmy sygnaturę dla funkcyjnych kolejek priorytetowych:
module type PQUEUE =
sig
type priority
type 'a t
exception EmptyPQueue
val empty : 'a t
val insert : 'a t -> priority -> 'a -> 'a t
val remove : 'a t -> priority * 'a * 'a t
end
- Zdefiniuj moduł PQueue : PQUEUE, przyjmując typ priority = int. Reprezentacja kolejki
może być dowolna. - Wykorzystaj moduł PQueue do napisania funkcji sortowania list liczb typu int.
- Uogólnij rozwiązanie punktów 1 i 2 definiując funktor,
który dla zadanego modułu OrdType : ORDTYPE zwraca moduł o sygnaturze PQUEUE, gdzie
module type ORDTYPE =
sig
type t
type comparison = LT | EQ | GT
val compare : t -> t -> comparison
end
Zmodyfikuj odpowiednio funkcję sortowania list z p. 2 i przetestuj ją.
Przy pomocy modułów pierwszego rodzaju zdefiniuj funkcję sort, która dla dowolnego
modułu implementującego sygnaturę ORDTYPE dla pewnego typu i dla dowolnej listy elementów
tego typu posortuje listę zgodnie z porządkiem definiowanym przez moduł. Użyj funktora z
poprzedniego punktu. Poza modułami pierwszego rodzaju będzie potrzebne jeszcze jedno
rozszerzenie języka.