{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "residential-answer",
   "metadata": {},
   "source": [
    "# Množice\n",
    "\n",
    "Ogledali si bomo dve implementaciji podatkovnega tipa [množica](https://en.wikipedia.org/wiki/Set_(abstract_data_type)). V jeziku OCaml množico opišemo z naslednjo signaturo:\n",
    "<a id='module_set_cell'></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "moving-highway",
   "metadata": {},
   "outputs": [],
   "source": [
    "type order = Less | Equal | Greater\n",
    "\n",
    "module type SET =\n",
    "sig\n",
    "    type element\n",
    "    val cmp : element -> element -> order\n",
    "    type set\n",
    "    val empty : set\n",
    "    val member : element -> set -> bool\n",
    "    val add : element -> set -> set\n",
    "    val remove : element -> set -> set\n",
    "    val to_list : set -> element list\n",
    "    val fold : ('a -> element -> 'a) -> 'a -> set -> 'a\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "looking-burst",
   "metadata": {},
   "source": [
    "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:\n",
    "\n",
    "* `member e s` vrne `true`, če množica `s` vsebuje element `e`,\n",
    "* `add e s` doda element `e` v množico `s`,\n",
    "* `remove e s` izbriše element `e` iz množice `s`\n",
    "* `to_list s` vrne seznam elementov v množici `s` (v poljubnem vrstnem redu).\n",
    "\n",
    "\n",
    "## Implementacija s seznamom\n",
    "\n",
    "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`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "three-device",
   "metadata": {},
   "outputs": [],
   "source": [
    "let ocaml_cmp x y =\n",
    "    let c = Stdlib.compare x y in\n",
    "    if c < 0 then Less\n",
    "    else if c > 0 then Greater\n",
    "    else Equal"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ordered-tours",
   "metadata": {},
   "source": [
    "Primer uporabe:\n",
    "\n",
    "    # let s = IntListSet.add 2 (IntListSet.add 4 IntListSet.empty) ;;\n",
    "    val s : IntListSet.set = <abstr>\n",
    "    # IntListSet.member 4 s ;;\n",
    "    - : bool = true\n",
    "\n",
    "Zgledujte se po implementaciji prioritetne vrste `MyFirstQueue` s predavanj.\n",
    "<a id='IntListSet'></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cellular-daisy",
   "metadata": {},
   "outputs": [],
   "source": [
    "module IntListSet : SET with type element = int =\n",
    "struct\n",
    "    (* dopolni *)\n",
    "end\n",
    "\n",
    "let s = IntListSet.add 2 (IntListSet.add 4 IntListSet.empty) ;;\n",
    "IntListSet.member 4 s ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "impaired-listing",
   "metadata": {},
   "source": [
    "## Generični `ListSet`\n",
    "\n",
    "Definicijo `IntListSet` spremenite v funktor `ListSet`, ki sprejme strukturo, ki zadošča signaturi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "sound-disposal",
   "metadata": {},
   "outputs": [],
   "source": [
    "module type ORDERED =\n",
    "    sig\n",
    "        type t\n",
    "        val cmp : t -> t -> order\n",
    "    end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sporting-render",
   "metadata": {},
   "source": [
    "ter vrne implementacijo množic s seznami. Nastavek je naslednji:\n",
    "\n",
    "    module ListSet(M : ORDERED) : SET with type element = M.t =\n",
    "      struct\n",
    "         ⋮\n",
    "      end\n",
    "\n",
    "Primer uporabe:\n",
    "\n",
    "    # module S = ListSet(struct type t = string  let cmp = ocaml_cmp end) ;;\n",
    "    module S :\n",
    "      sig\n",
    "        type element = string\n",
    "        val cmp : element -> element -> order\n",
    "        type set\n",
    "        val empty : set\n",
    "        val member : element -> set -> bool\n",
    "        val add : element -> set -> set\n",
    "        val remove : element -> set -> set\n",
    "        val to_list : set -> element list\n",
    "        val fold : ('a -> element -> 'a) -> 'a -> set -> 'a\n",
    "      end\n",
    "    # let s = S.add \"foo\" (S.add \"bar\" S.empty) ;;\n",
    "    val s : S.set = <abstr>\n",
    "    # S.member \"foo\" s ;;\n",
    "    - : bool = true\n",
    "\n",
    "Zgledujte se po implementaciji prioritetne vrste `ListQueue` s predavanj.\n",
    "<a id='ListSet'></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "neural-interstate",
   "metadata": {},
   "outputs": [],
   "source": [
    "module ListSet(M : ORDERED) : SET with type element = M.t =\n",
    "struct\n",
    "    (* dopolni *)\n",
    "end\n",
    "  \n",
    "module S = ListSet(struct type t = string  let cmp = ocaml_cmp end) ;;\n",
    "let s = S.add \"foo\" (S.add \"bar\" S.empty) ;;\n",
    "S.member \"foo\" s ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "imposed-netscape",
   "metadata": {},
   "source": [
    "## Primerjava učinkovitosti `ListSet` in `AVLSet`\n",
    "\n",
    "Modul `AVLSet` implementira funktor, ki tako kot `ListSet` sprejme strukturo s signaturo `ORDERED` in vrne\n",
    "implementacijo množic z AVL drevesi, glej datoteko `avlset.ml`.\n",
    "<a id='AVLSet'></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "complicated-incentive",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* datoteka avlset.ml *)\n",
    "module AVLSet(M : ORDERED) : SET with type element = M.t =\n",
    "  struct\n",
    "    type element = M.t\n",
    "    let cmp = M.cmp\n",
    "\n",
    "    type set = Empty | Node of element * int * set * set\n",
    "\n",
    "    let empty = Empty\n",
    "\n",
    "    let height = function\n",
    "      | Empty -> 0\n",
    "      | Node (_, h, _, _) -> h\n",
    "\n",
    "    let leaf v = Node (v, 1, Empty, Empty)\n",
    "\n",
    "    let node (v, l, r) = Node (v, 1 + max (height l) (height r), l, r)\n",
    "\n",
    "    let rec member x = function\n",
    "      | Empty -> false\n",
    "      | Node (y, _, l, r) ->\n",
    "         begin\n",
    "           match cmp x y with\n",
    "           | Equal -> true\n",
    "           | Less -> member x l\n",
    "           | Greater -> member x r\n",
    "         end\n",
    "\n",
    "    let rec to_list = function\n",
    "      | Empty -> []\n",
    "      | Node (x, _, l, r) -> to_list l @ [x] @ to_list r\n",
    "\n",
    "    let rotateLeft = function\n",
    "      | Node (x, _, a, Node (y, _, b, c)) -> node (y, node (x, a, b), c)\n",
    "      | t -> t\n",
    "\n",
    "    (* alternativni zapis s case *)\n",
    "    let rotateRight = function\n",
    "      | Node (y, _, Node (x, _, a, b), c) -> node (x, a, node (y, b, c))\n",
    "      | t -> t\n",
    "\n",
    "    let imbalance = function\n",
    "      | Empty -> 0\n",
    "      | Node (_, _, l, r) -> height l - height r\n",
    "\n",
    "    let balance = function\n",
    "      | Empty -> Empty\n",
    "      | Node (x, _, l, r) as t ->\n",
    "         begin\n",
    "           match imbalance t with\n",
    "           | 2 ->\n",
    "              (match imbalance l with\n",
    "               | -1 -> rotateRight (node (x, rotateLeft l, r))\n",
    "               | _ -> rotateRight t)\n",
    "           | -2 ->\n",
    "              (match imbalance r with\n",
    "               | 1 -> rotateLeft (node (x, l, rotateRight r))\n",
    "               | _ -> rotateLeft t)\n",
    "           | _ -> t\n",
    "         end\n",
    "\n",
    "    let rec add x = function\n",
    "      | Empty -> leaf x\n",
    "      | Node (y, _, l, r) as t ->\n",
    "         begin\n",
    "           match cmp x y with\n",
    "           | Equal -> t\n",
    "           | Less -> balance (node (y, add x l, r))\n",
    "           | Greater -> balance (node (y, l, add x r))\n",
    "         end\n",
    "\n",
    "    let rec remove x = function\n",
    "      | Empty -> Empty\n",
    "      | Node (y, _, l, r) ->\n",
    "         let rec removeSuccessor = function\n",
    "           | Empty -> assert false\n",
    "           | Node (x, _, Empty, r) -> (r, x)\n",
    "           | Node (x, _, l, r) ->\n",
    "              let (l', y) = removeSuccessor l in\n",
    "              (balance (node (x, l', r)), y)\n",
    "         in\n",
    "         match cmp x y with\n",
    "         | Less -> balance (node (y, remove x l, r))\n",
    "         | Greater -> balance (node (y, l, remove x r))\n",
    "         | Equal ->\n",
    "            begin match (l, r) with\n",
    "            | (_, Empty) -> l\n",
    "            | (Empty, _) -> r\n",
    "            | _ ->\n",
    "               let (r', y') = removeSuccessor r in\n",
    "               balance (node (y', l, r'))\n",
    "            end\n",
    "\n",
    "    let rec fold f x = function\n",
    "      | Empty -> x\n",
    "      | Node (y, _, l, r) -> fold f (f (fold f x l) y) r\n",
    "\n",
    "  end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "appointed-voltage",
   "metadata": {},
   "source": [
    "Preverimo, da je `AVLSet` res učinkovitejši od `ListSet`. Najprej definiramo dve\n",
    "implementaciji množic celih števil, eno s seznami in eno z AVL drevesi:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "compact-southwest",
   "metadata": {},
   "outputs": [],
   "source": [
    "module SL = ListSet (struct type t = int let cmp = ocaml_cmp end)\n",
    "module SA = AVLSet (struct type t = int let cmp = ocaml_cmp end)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "auburn-glossary",
   "metadata": {},
   "source": [
    "### Množica `{1, 2, ..., n}`\n",
    "\n",
    "Definirajte funkcijo `add_list n`, ki vrne množico (implementirano s seznami) števil od `1` do `n`. Primer uporabe:\n",
    "\n",
    "    # SL.to_list (add_list 10) ;;\n",
    "    - : SL.element list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "combined-wednesday",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* let rec add_list = … *)\n",
    "SL.to_list (add_list 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dangerous-program",
   "metadata": {},
   "source": [
    "Na enak način definirajte še funkcijo `add_avl`, ki množico implementira z AVL drevesi:\n",
    "\n",
    "    # SA.to_list (add_avl 10) ;;\n",
    "    - : SA.element list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "incorporated-mounting",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* let rec add_avl = … *)\n",
    "SA.to_list (add_avl 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "geographic-neighborhood",
   "metadata": {},
   "source": [
    "### Čas izvajanja\n",
    "\n",
    "Podana je funkcija `time`, ki izmeri čas izvajanja dane funkcije `f`:\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "wanted-tonight",
   "metadata": {},
   "outputs": [],
   "source": [
    "let time f =\n",
    "    let start = Sys.time () in\n",
    "    f () ;\n",
    "    let stop = Sys.time () in\n",
    "    stop -. start"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "executed-waterproof",
   "metadata": {},
   "source": [
    "Funkcija `f` je »thunk«, torej sprejme le argument tipa `unit`. Čas, ki ga OCaml potrebuje, da sešteje vsa števila od 1 do 10000000:\n",
    "\n",
    "    # time (fun () -> let s = ref 0 in for i = 1 to 10000000 do s := !s + i done; !s) ;;\n",
    "    - : float = 0.17635\n",
    "\n",
    "Izmerite, koliko časa traja vstavljanje velikega števila elementov v množico.\n",
    "Primerjajte implementaciji `SL` in `SA`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "distant-clock",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* time (fun () -> … ) ;;\n",
    "time … *)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "weighted-history",
   "metadata": {},
   "source": [
    "## Fold\n",
    "\n",
    "Funkcija `fold` sprejme\n",
    "\n",
    "* funkcijo `f` dveh argumentov,\n",
    "* začetno vrednost `z` in\n",
    "* množico `m = {x₁, x₂, …, xᵢ}`\n",
    "\n",
    "ter izračuna rezultat tako, da s pomočjo `f` elemente enega za drugim kombinira s trenutno vrednostjo:\n",
    "\n",
    "    f (… (f (f z x₁) x₂) …) xᵢₙ\n",
    "\n",
    "Primer, kjer je funkcija `f` kar sešetvane, začetna vrednost `z` je `0` in množica `m` je `{1,2,3,4}`:\n",
    "\n",
    "    # SL.fold ( + ) 0 (add_list 4) ;;\n",
    "    - : int = 10\n",
    "\n",
    "Signaturi [`SET`](#module_set_cell) dodajte funkcijo `fold`:\n",
    "\n",
    "    val fold : ('a -> element -> 'a) -> 'a -> set -> 'a\n",
    "\n",
    "in jo implementirajte v funktorjih [`ListSet`](#ListSet) in [`AVLSet`](#AVLSet)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "composed-wealth",
   "metadata": {},
   "source": [
    "## Unija, filter in presek\n",
    "\n",
    "Definirajte funktor `SetOps`, ki sprejme strukturo s signaturo `SET` in\n",
    "implementira funkcije `union`, `filter` ter `intersection`. Nastavek za rešitev:\n",
    "\n",
    "    module SetOps(S : SET) =\n",
    "    struct\n",
    "       let union a b = …\n",
    "       let filter p a = …\n",
    "       let intersection a b = …\n",
    "    end\n",
    "\n",
    "Unijo in presek poznamo, funkcija `filter` pa sprejme predikat (funkcijo, ki\n",
    "vrača vrednosti tipa `bool`) in množico, ter novo množico tistih elementov, ki\n",
    "zadoščajo predikatu. Pri definiciji funkcij si pomagajte s funkcijo `fold`.\n",
    "\n",
    "Primer:\n",
    "\n",
    "    # module SA_ops = SetOps(SA) ;;\n",
    "    module SA_ops :\n",
    "      sig\n",
    "        val union : SA.set -> SA.set -> SA.set\n",
    "        val filter : (SA.element -> bool) -> SA.set -> SA.set\n",
    "        val intersection : SA.set -> SA.set -> SA.set\n",
    "      end\n",
    "    # SA.to_list (SA_ops.filter (fun x -> x > 10) (add_avl 20)) ;;\n",
    "    - : SA.element list = [11; 12; 13; 14; 15; 16; 17; 18; 19; 20]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "headed-synthetic",
   "metadata": {},
   "outputs": [],
   "source": [
    "module SetOps(S : SET) =\n",
    "  struct\n",
    "    (* dopolni *)\n",
    "  end\n",
    "\n",
    "module SA_ops = SetOps(SA)\n",
    ";;\n",
    "SA.to_list (SA_ops.filter (fun x -> x > 10) (add_avl 20))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml default",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.08.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}