Vaje: množice

Ogledali si bomo dve implementaciji podatkovnega tipa množica. V jeziku OCaml množico opišemo z naslednjo signaturo:

type order = Less | Equal | Greater

module type SET =
sig
    type element
    val cmp : element -> element -> order
    type set
    val empty : set
    val member : element -> set -> bool
    val add : element -> set -> set
    val remove : element -> set -> set
    val to_list : set -> element list
end

V množici se vsak element lahko pojavi samo enkrat. Tip elementov, ki jih vsebuje množica, mora biti primerljiv – elemente primerjamo s funkcijo cmp, ki vrne Less, Equal ali Greater. Množica podpira naslednje operacije:

• member e s vrne true, če množica s vsebuje element e,
• add e s doda element e v množico s,
• remove e s izbriše element e iz množice s
• to_list s vrne seznam elementov v množici s (v poljubnem vrstnem redu).

Implementacija s seznamom

Definirajte strukturo IntListSet, ki elemente množice hrani v seznamu. Tip elementov naj bo celo število (int), za primerjavo pa lahko uporabite kar funkcijo ocaml_cmp:

let ocaml_cmp x y =
  let c = Stdlib.compare x y in
  if c < 0 then Less
  else if c > 0 then Greater
  else Equal

Primer uporabe:

# let s = IntListSet.add 2 (IntListSet.add 4 IntListSet.empty) ;;
val s : IntListSet.set = <abstr>
# IntListSet.member 4 s ;;
- : bool = true

Zgledujte se po implementaciji prioritetne vrste MyFirstQueue s predavanj.

Generični ListSet

Definicijo IntListSet spremenite v funktor ListSet, ki sprejme strukturo, ki zadošča signaturi

module type ORDERED =
  sig
    type t
    val cmp : t -> t -> order
  end

ter vrne implementacijo množic s seznami. Nastavek je naslednji:

module ListSet(M : ORDERED) : SET with type element = M.t =
  struct
     ⋮
  end

Primer uporabe:

# module S = ListSet(struct type t = string  let cmp = ocaml_cmp end) ;;
module S :
  sig
    type element = string
    val cmp : element -> element -> order
    type set
    val empty : set
    val member : element -> set -> bool
    val add : element -> set -> set
    val remove : element -> set -> set
    val to_list : set -> element list
    val fold : ('a -> element -> 'a) -> 'a -> set -> 'a
  end
# let s = S.add "foo" (S.add "bar" S.empty) ;;
val s : S.set = <abstr>
# S.member "foo" s ;;
- : bool = true

Zgledujte se po implementaciji prioritetne vrste ListQueue s predavanj.

Primerjava učinkovitosti ListSet in AVLSet

Modul AVLSet implementira funktor, ki tako kot ListSet sprejme strukturo s signaturo ORDERED in vrne implementacijo množic z AVL drevesi, glej ./avlset.ml.

Preverimo, da je AVLSet res učinkovitejši od ListSet. Najprej definiramo dve implementaciji množic celih števil, eno s seznami in eno z AVL drevesi:

module SL = ListSet (struct type t = int let cmp = ocaml_cmp end)
module SA = AVLSet (struct type t = int let cmp = ocaml_cmp end)

Množica {1, 2, ..., n}

Definirajte funkcijo add_list n, ki vrne množico (implementirano s seznami) števil od 1 do n. Primer uporabe:

# SL.to_list (add_list 10) ;;
- : SL.element list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]

Na enak način definirajte še funkcijo add_avl, ki množico implementira z AVL drevesi:

# SA.to_list (add_avl 10) ;;
- : SA.element list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Čas izvajanja

Podana je funkcija time, ki izmeri čas izvajanja dane funkcije f:

let time f =
  let start = Sys.time () in
  f () ;
  let stop = Sys.time () in
  stop -. start

Funkcija f je »thunk«, torej sprejme le argument tipa unit. Čas, ki ga OCaml potrebuje, da sešteje vsa števila od 1 do 10000000:

# time (fun () -> let s = ref 0 in for i = 1 to 10000000 do s := !s + i done; !s) ;;
- : float = 0.17635

Izmerite, koliko časa traja vstavljanje velikega števila elementov v množico. Primerjajte implementaciji SL in SA.

Fold

Funkcija fold sprejme

• funkcijo f dveh argumentov,
• začetno vrednost z in
• množico m = {x₁, x₂, …, xᵢ}

ter izračuna rezultat tako, da s pomočjo f elemente enega za drugim kombinira s trenutno vrednostjo:

f (… (f (f z x₁) x₂) …) xᵢₙ

Primer, kjer je funkcija f kar sešetvane, začetna vrednost z je 0 in množica m je {1,2,3,4}:

# SL.fold ( + ) 0 (add_list 4) ;;
- : int = 10

Signaturi SET dodajte funkcijo fold:

val fold : ('a -> element -> 'a) -> 'a -> set -> 'a

in jo implementirajte v funktorjih ListSet in AVLSet.

Unija, filter in presek

Definirajte funktor SetOps, ki sprejme strukturo s signaturo SET in implementira funkcije union, filter ter intersection. Nastavek za rešitev:

module SetOps(S : SET) =
struct
   let union a b = …
   let filter p a = …
   let intersection a b = …
end

Unijo in presek poznamo, funkcija filter pa sprejme predikat (funkcijo, ki vrača vrednosti tipa bool) in množico, ter novo množico tistih elementov, ki zadoščajo predikatu. Pri definiciji funkcij si pomagajte s funkcijo fold.

Primer:

# module SA_ops = SetOps(SA) ;;
module SA_ops :
  sig
    val union : SA.set -> SA.set -> SA.set
    val filter : (SA.element -> bool) -> SA.set -> SA.set
    val intersection : SA.set -> SA.set -> SA.set
  end
# SA.to_list (SA_ops.filter (fun x -> x > 10) (add_avl 20)) ;;
- : SA.element list = [11; 12; 13; 14; 15; 16; 17; 18; 19; 20]