Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Control.Print.printDepth := 100;
- (*natural (Naravna števila definiramo tako: Obstaja ničla (ZERO).
- Vsako naravno število ima svojega naslednika (NEXT).
- -----------------------------------------------------------------
- Nič ni naslednik nobenega naravnega števila.
- Če sta dve števili enaki, sta enaka tudi njuna naslednika.)
- datatype natural =
- NEXT of natural
- | ZERO
- *)
- (*fun toInt(a: natural): int (vrne celoštevilsko (int) predstavitev naravnega števila)
- fun toInt(a: natural): int =
- case a of
- NEXT b => toInt(b) +1
- | ZERO => 0
- val test_toInt1 = 0 = toInt(ZERO);
- val test_toInt2 = 1 = toInt(NEXT(ZERO));
- val test_toInt3 = 12 = toInt(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))))))))));*)
- (*fun add(a: natural, b: natural): natural (vrne naravno število, ki ustreza vsoti števil a in b · deluje naj direktno na naravnih številih, brez pretvorbe v int)
- fun add(a: natural, b: natural): natural =
- case a of
- NEXT a => NEXT (add(b,a))
- | ZERO => b
- val test_add1 = ZERO = add(ZERO, ZERO);
- val test_add2 = NEXT(ZERO) = add(NEXT(ZERO), ZERO);
- val test_add3 = NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))) = add(NEXT(NEXT(NEXT(ZERO))), NEXT(NEXT(NEXT(ZERO))));
- val test_add4 = NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))))) = add(NEXT(NEXT(ZERO)), NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))));
- val test_add5 = NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))))) = add(NEXT(NEXT(NEXT(NEXT(NEXT(NEXT(ZERO)))))), NEXT(NEXT(ZERO)));
- val test_add6 = NEXT(ZERO) = add(ZERO, NEXT(ZERO));*)
- (*----------------------------------------------------------------------------------------------------*)
- (* bstree (Binarno iskalno drevo definiramo tako: Obstaja prazno iskalno drevo (lf).
- Obstaja tudi veja (br), za katero poznamo vrednost elementa v njej ter obe poddrevesi (bstree * int * bstree).
- Za poddrevesi velja, da so vsi elementi znotraj levega poddrevesa (strogo) manjši od elementa v veji, vsi elementi desnega poddrevesa pa so (strogo) večji.
- val tree = br (br (br (lf, 2, lf), 7, lf), 9, br (br (lf, 13, lf), 21, br (lf, 25, lf)))
- *)
- datatype bstree =
- br of bstree * int * bstree
- | lf
- val tree = br (br (br (lf, 2, lf), 7, lf), 9, br (br (lf, 13, lf), 21, br (lf, 25, lf)));
- (*fun min(tree: bstree): int option (vrne najmanjši element drevesa, če ta obstaja)
- fun min(tree: bstree): int option =
- case tree of
- br(left, i, _) => if(left = lf) then SOME i else min(left)
- | lf => NONE
- val test_min1 = NONE = min(lf);
- val test_min2 = SOME 5 = min(br(lf, 5, lf));
- val test_min3 = SOME 2 = min(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))));
- val test_min4 = SOME(~3) = min(br(br(br(br(lf, ~3, lf), ~1, lf), 3, lf), 100, lf));
- val test_min5 = SOME 2 = min(br(br(lf, 2, lf), 5, lf));*)
- (*fun max(tree: bstree): int option (vrne največji element drevesa, če ta obstaja)
- fun max(tree: bstree): int option =
- case tree of
- br(_, i, right) => if(right = lf) then SOME i else max(right)
- | lf => NONE
- val test_max1 = NONE = max(lf);
- val test_max2 = SOME 5 = max(br(lf, 5, lf));
- val test_min3 = SOME 25 = max(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))));
- val test_max4 = SOME 100 = max(br(br(br(br(lf, ~3, lf), ~1, lf), 3, lf), 100, lf));
- val test_max5 = SOME 5 = max(br(br(lf, 2, lf), 5, lf));*)
- (*fun contains(tree: bstree, x: int): bool (vrne true, če drevo vsebuje vejo s podano vrednostjo)
- fun contains(tree: bstree, x: int): bool =
- case tree of
- br(left, i, right) => if(x < i) then contains(left, x)
- else if(x > i) then contains(right, x)
- else true
- | lf => false
- val test_contains1 = false = contains(lf, 500)
- val test_contains2 = true = contains(br(lf, 5, lf), 5)
- val test_contains3 = true = contains(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))), 21)
- val test_contains4 = true = contains(br(br(br(br(lf, ~3, lf), ~1, lf), 3, lf), 100, lf), ~3)
- val test_contains5 = false = contains(br(lf, 5, br(lf, 6, lf)), 4)
- val test_contains6 = false = contains(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))), 3)*)
- (*fun countLeaves(tree: bstree): int (vrne število listov (lf) v drevesu)
- fun countLeaves(tree: bstree): int =
- case tree of
- br(left, i, right) => countLeaves(left) + countLeaves(right)
- | lf => 1
- val test_countLeaves1 = 1 = countLeaves(lf)
- val test_countLeaves2 = 2 = countLeaves(br(lf, 5, lf))
- val test_countLeaves3 = 7 = countLeaves(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))))
- val test_countLeaves4 = 5 = countLeaves(br(br(br(br(lf, ~2, lf), ~1, lf), 3, lf), 100, lf))
- val test_countLeaves5 = 3 = countLeaves(br(lf, 5, br(lf, 6, lf))) *)
- (*br (br (br (lf, 2, lf), 7, lf), 9, br (br (lf, 13, lf), 21, br (lf, 25, lf)))
- br (br (lf, 2, lf), 7, lf || br (br (lf, 13, lf), 21, br (lf, 25, lf))
- br (lf, 2, lf || lf || br (lf, 13, lf), || br (lf, 25, lf)
- lf || lf lf ||lf lf || lf *)
- (*fun countBranches(tree: bstree): int (vrne število vej (br) v drevesu)
- fun countBranches(tree: bstree): int =
- case tree of
- br(left, i, right) => countBranches(left) + countBranches(right) +1
- | lf => 0
- val test_countBranches1 = 0 = countBranches(lf)
- val test_countBranches2 = 1 = countBranches(br(lf, 5, lf))
- val test_countBranches3 = 6 = countBranches(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))))
- val test_countBranches4 = 4 = countBranches(br(br(br(br(lf, ~2, lf), ~1, lf), 3, lf), 100, lf))
- val test_countBranches5 = 2 = countBranches(br(lf, 5, br(lf, 6, lf))) *)
- (*fun toList(tree: bstree): int list (vrne seznam urejenih elementov podanega drevesa,
- v seznamu naj bo prvi element min(tree), zadnji pa max(tree)
- · za združevanje seznamov lahko uporabite operator @)
- fun toList(tree: bstree): int list =
- case tree of
- br(left, i, right) => toList(left) @ [i] @ [] @ toList(right)
- | lf => []
- val test_toList1 = [] = toList(lf)
- val test_toList2 = [5] = toList(br(lf, 5, lf))
- val test_toList3 = [2,7,9,13,21,25] = toList(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))))
- val test_toList4 = [~2,~1,3,100] = toList(br(br(br(br(lf, ~2, lf), ~1, lf), 3, lf), 100, lf))
- val test_toList5 = [5,6] = toList(br(lf, 5, br(lf, 6, lf))) *)
- (* fun valid(tree: bstree): bool (vrne true, če je podano drevo veljavno binarno iskalno drevo (glej definicijo zgoraj))
- fun pridobi(tree: bstree): int =
- case tree of
- br(_,i,_) => i
- | lf => 0
- fun valid(tree: bstree): bool =
- case tree of
- br(left, i, right) =>
- if(pridobi(left) >= i andalso i >= pridobi(right)) then false
- else valid(left) andalso valid(right)
- | lf => true
- val test_valid1 = true = valid(lf)
- val test_valid2 = true = valid(br(lf, 5, lf))
- val test_valid3 = true = valid(br(br(br(lf, 2, lf), 7, lf), 9, br(br(lf, 13, lf), 21, br(lf, 25, lf))))
- val test_valid5 = true = valid(br(lf, 5, br(lf, 6, lf)))
- val test_valid4 = false = valid(br(br(br(br(lf, ~3, lf), ~1, lf), 3, lf), 0, lf))
- val test_valid6 = false = valid(br(br(br(lf, 6, lf), 3, lf), 5, lf))
- val test_valid7 = false = valid(br(br(br(lf, 3, lf), 3, lf), 3, lf)) *)
- (*fun oldest(people: {age:int, name:string} list): string option
- (vrne ime najstarejše osebe (če obstaja) v seznamu zapisov oblike {name="ime", age=starost})*)
- fun oldest(people: {age:int, name:string} list): string option =
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement