5. laboratorijske vaje

Tip unit

Je primerljiv tip, s katerim lahko predstavimo le eno vrednost (). Nanjo lahko gledamo kot na prazno terko.

• "terka" z dvema elementoma (a, b) oz. {1=a, 2=b}
• "terka" z enim elementom {1=a} (zapis oklepaji ne gre — (a))
• "terka" z nič elementi () oz. {}

Funkcija print : string -> unit izpiše na standardni izhod podani niz, vrednost samega izraza njene aplikacije je (). V SML funkcije vedno vračajo neko vrednost. Poleg tega vedno sprejema natanko en argument.

Zapis f () ne pomeni "klic" (aplikacija) funkcije z nič argumenti ampak za enim samim (), ki je tipa unit.

Funkcije v povezavi z tipom unit:

• ignore : 'a -> unit: funkcija sprejme karkoli in vrne ()

• before : 'a * unit -> 'a: in-fiksni "operator", ki ignorira desno stran (izraz na desni more biti tipa unit).
  Primer

  - 3 before print "a\n" before print "b\n" before print "c\n";
  a
  b
  c
  val it = 3 : int
  

Mutacije

Mutacije so tipa 'a ref.

• ustvarjanje reference, funkcija ref : 'a -> 'a ref
• dereferenciranje, operator ! : 'a ref -> 'a
• prirejanje, in-fiksni operator := 'a ref * a -> unit

- val a = ref [1];
val a = ref [1] : int list ref

- fun f x = x :: !a;
val f = fn : int -> int list

- f 3;
val it = [3,1] : int list

- a := [];
val it = () : unit

- f 3;
val it = [3] : int list


- fun faktoriela n =
    let
      val n = ref n
      val i = ref 1
    in
      while !n > 0 do (i := !i * !n; n := !n - 1);
      !i
    end;

- faktoriela 10;
val it = 3628800 : int

"Mutacije niso rekurzivne!" (int list ref $\neq$ int ref list ref)

Mutirani seznami

Implementiraj funkcijo val bubbleSort = fn : int array -> unit.
Funkcija sprejme mutacijo int array, glej modul Array. Njena funkcionalnost je sortiranje podane table z uporabo algoritma BubbleSort. Pomagaj si z rezervirano besedo while.

fun swap (a, i, j) =
    let val temp = Array.sub (a, i)
    in (Array.update (a, i, Array.sub (a, j)); Array.update (a, j, temp)) end;

fun bubbleSort a =
    let val n = ref (Array.length a)
        val i = ref 0
        val swapped = ref true
    in
    while (!swapped) do (
        swapped := false;
        i := 1;
        while (!i < !n) do (
            (if Array.sub (a, !i - 1) > Array.sub (a, !i)
            then (swap (a, !i - 1, !i);
                swapped := true)
            else ()); i := !i + 1))
    end;

val sez = Array.fromList [5, 2, ~3, 1, 0, 4];
bubbleSort sez;
sez;

Zanka while

Spodnja programa sta si med seboj ekvivalentna.

val n = ref 10;
val i = ref 0;

while (!n > 0) do
    (i := !i + !n; n := !n-1);
(* n = 0, i = 55 *)

val n = ref 10;
val i = ref 0;

let fun myWhile () =
    if (!n > 0)
    then (i := !i + !n; n := !n-1; myWhile ())
    else ()
in myWhile () end;
(* n = 0, i = 55 *)

Moduli

Primer modula za delo s kompleksnimi števili.

signature COMPLEX =
sig
    type complex

    val complex : Real.real -> Real.real -> complex
    val i : complex
    val re : complex -> Real.real
    val im : complex -> Real.real

    val neg : complex -> complex
    val inv : complex -> complex

    val * : complex * complex -> complex
    val + : complex * complex -> complex

    val toString: complex -> String.string
end;

structure Complex :> COMPLEX =
struct
    type complex = Real.real * Real.real

    fun complex a b = (a, b)

    val i : complex = (0.0, 1.0)
    fun re ((a, b) : complex) = a
    fun im ((a, b) : complex) = b

    fun neg ((a, b) : complex) = let open Real in (~ a, ~ b) end
    fun inv ((a, b) : complex) = let open Real val s = a * a + b * b in (a / s, ~ b / s) end

    fun conj ((a, b) : complex) = (a, Real.~ b)

    fun op* ((a1, b1) : complex, (a2, b2) : complex) = let open Real in (a1 * a2 - b1 * b2, a1 * b2 + a2 * b1) end
    fun op+ ((a1, b1) : complex, (a2, b2) : complex) = let open Real in (a1 + a2, b1 + b2) end

    fun toString ((a, b) : complex) = Real.toString a ^ " + " ^ Real.toString b ^ "i"
end;

Dodatki

• open <ime strukture> elemente strukture da v globalno (lokalno) okolje.
• local <lokalne definicije> in <uporaba le teh> end lokalni del strukture

Funktorji

Primer funktorja za zgoščene množice. SML implementacijo najdete tukaj.

signature KEY =
sig
    type key
    val sameKey : key -> key -> bool
end;

signature SET =
sig
    structure Key : KEY
    type item
    type set
    val mkEmpty : unit -> set
    val toList : set -> item list
    val add : set -> item -> unit
    val subtract : set -> item -> unit
    val member : set -> item -> bool
    val isEmpty : set -> bool
    val fold : (item * 'b -> 'b) -> 'b -> set -> 'b
end;


functor ListSetFn (K : KEY) : SET where type item = K.key =
struct
    structure Key = K
    type item = K.key
    type set = item list ref
    fun mkEmpty () : set = ref []
    fun toList s = !s
    fun member s e = List.exists (K.sameKey e) (!s)
    fun add s e = if member s e then () else (s := e :: !s)
    fun subtract s e = s := (List.filter (not o K.sameKey e) (!s))
    fun isEmpty s = null (!s)
    fun fold f z s = List.foldl f z (!s)
end;


structure ListSetSet = ListSetFn (type key = int fun sameKey x y = x = y)

Funktorji + curying

signature MONOID =
sig
    type t
    val e : t
    val + : t * t -> t
end;

signature GROUP =
sig
    type t
    val e : t
    val * : t * t -> t
    val inv : t -> t
end;

signature RING =
sig
    type t
    val + : t * t -> t
    val zero : t
    val neg : t -> t
    val * : t * t -> t
    val one : t
end;

S pomočjo naslednjega funktorja lahko grupo G in mondid M združimo v kolobar.

(* funsig MKRING (structure G: GROUP structure M: MONOID where type t = G.t) = RING *)
functor MakeRing (G: GROUP) (M: MONOID where type t = G.t) : RING =
struct
    type t = G.t
    fun op+ (a, b) = G.* (a, b)
    val zero = G.e
    fun neg a = G.inv a
    fun op* (a, b) = M.+ (a, b)
    val one = M.e
end

structure Z13 : GROUP =
struct
    type t = int;
    val e = 0;
    fun op * (a, b) =  (a + b mod 13);
    fun inv a = ~a mod 13;
end;

structure Zm13 : MONOID =
struct
    type t = int;
    val e = 1;
    fun op + (a, b) =  (a * b mod 13);
end;

(* delno apliciran funktor *)
functor MakeRingP = MakeRing (Z13)

structure Z = Zm13;
structure R13 = MakeRing (Z13) (Zm13)
structure R13 = MakeRingP (Zm13)

Naloge za oddajo

(NE SPREMNINJAJTE PODPISOV!)

Modul Rational

V programskem jeziku SML implementirajte naslednji modul (programski vmesnik) za delo z racionalnimi števili. Vaša struktura naj se imenuje Rational in naj definira podatkovni tip (datatype) rational (ki je lahko bodisi celo število bodisi ulomek).

Ulomki naj sledijo naslednjim pravilom:

1. Imenovalec je vedno strogo večji od 1.
2. Vsak ulomek je okrajšan.

V oddani datoteki implementirajte le strukturo Rational, ki ustreza podpisu RATIONAL. Modul naj ne bo popisan, dana datoteka pa popisa ne vsebuje.

signature RATIONAL =
sig
    (* Definirajte podatkovni tip rational, ki podpira preverjanje enakosti. *)
    eqtype rational

    (* Definirajte izjemo, ki se kliče pri delu z neveljavnimi ulomki - deljenju z nič. *)
    exception BadRational

    (* Vrne racionalno število, ki je rezultat deljenja dveh podanih celih števil. *)
    val makeRational: int * int -> rational

    (* Vrne nasprotno vrednost podanega števila. *)
    val neg: rational -> rational

    (* Vrne obratno vrednost podanega števila. *)
    val inv: rational -> rational

    (* Funkcije za seštevanje in množenje. Rezultat vsake operacije naj sledi postavljenim pravilom. *)
    val add: rational * rational -> rational
    val mul: rational * rational -> rational

    (* Vrne niz, ki ustreza podanemu številu.
        Če je število celo, naj vrne niz oblike "x" oz. "~x".
        Če je število ulomek, naj vrne niz oblike "x/y" oz. "~x/y". *)
    val toString: rational -> string
end

Primeri.

structure Rational : RATIONAL
- structure Rational :> RATIONAL = Rational;
structure Rational : RATIONAL
- open Rational;
opening Rational
  eqtype rational
  exception BadRational
  val makeRational : int * int -> rational
  val neg : rational -> rational
  val inv : rational -> rational
  val add : rational * rational -> rational
  val mul : rational * rational -> rational
  val toString : rational -> string
- val r = add (makeRational (14, ~12),  makeRational (6, 10));
val r = - : rational
- toString r;
val it = "~17/30" : string

Funktor SetFn

Implementirajte tudi funktor SetFn, ki ustreza podpisu SETFN. Funktor vrača modul, ki je podpisan s podpisom SET, ki ima razkrito definicijo podatkovnega tipa type.

signature EQ =
sig
    type t
    val eq : t -> t -> bool
end

signature SET =
sig
    (* podatkovni tip za elemente množice *)
    type item

    (* podatkovni tip množico *)
    type set

    (* prazna množica *)
    val empty : set

    (* vrne množico s samo podanim elementom *)
    val singleton : item -> set

    (* unija množic *)
    val union : set -> set -> set

    (* razlika množic (prva - druga) *)
    val difference : set -> set -> set

    (* a je prva množica podmnožica druge *)
    val subset : set -> set -> bool
end

funsig SETFN (Eq : EQ) = SET

Primeri.

- functor SetFn : SETFN = SetFn;
functor SetFn(Eq: sig
                    type t
                    val eq : t -> t -> bool
                  end) :
             sig
               type item
               type set
               val empty : set
               val singleton : item -> set
               val union : set -> set -> set
               val difference : set -> set -> set
               val subset : set -> set -> bool
             end
- structure S = SetFn (type t = int fun eq x y = x = y);
structure S : SET
- S.empty;
val it = - : S.set
- S.singleton;
val it = fn : S.item -> S.set
- val s3 = S.singleton 3;
val s3 = - : S.set
- val s4 = S.singleton 4;
val s4 = - : S.set
- S.subset s4 (S.union s3 s4);
val it = true : bool

Če pozenete rešeno nalogo skozi iterpreter dobite (oz. nekaj podobnega):

[opening 05.sml]
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[library $SMLNJ-BASIS/(basis.cm):basis-common.cm is stable]
[autoloading done]
structure Rational :
  sig
    datatype rational = Frac of int * int | Whole of int
    exception BadRational
    val makeRational : int * int -> rational
    val neg : rational -> rational
    val inv : rational -> rational
    val add : rational * rational -> rational
    val mul : rational * rational -> rational
    val toString : rational -> string
  end
signature EQ =
  sig
    type t
    val eq : t -> t -> bool
  end
signature SET =
  sig
    type item
    type set
    val empty : set
    val singleton : item -> set
    val union : set -> set -> set
    val difference : set -> set -> set
    val subset : set -> set -> bool
  end
[autoloading]
[autoloading done]
functor SetFn(Eq: sig
                    type t
                    val eq : t -> t -> bool
                  end) :
             sig
               type item = Eq.t
               type set
               val empty : set
               val singleton : item -> set
               val union : set -> set -> set
               val difference : set -> set -> set
               val subset : set -> set -> bool
             end

Oddajte eno datoteko z imenom 05.sml.