Institute of Computer Science
Faculty of Engineering, Christian-Albrechts-University of Kiel
| Computer-Aided Program
Development Institute of Computer Science Faculty of Engineering, Christian-Albrechts-University of Kiel |
|
| KIEL - Examples |
(* FIRST RELEASE *)
fun fac1 (n : int) : int =
if n = 0 then 1
else n * fac1(n-1);
fun facaux (n : int, res : int) : int =
if n = 0 then res
else facaux(n-1,n*res);
fun fac2 (n : int) : int =
facaux(n,1);
fun fib (n : int) : int =
if n <= 1 then 1
else fib(n-1) + fib(n-2);
fun succ (n : int) : int =
if n = 0 then 1
else succ(succ(n-1)-1) + 1;
fun morris (x : int, y : int) : int =
if x <= 0 then 1
else morris(x-1,morris(x-y,y));
fun iseven (n : int) : bool =
if n = 0 then true
else isodd(n-1)
and isodd (n : int) : bool =
if n = 0 then false
else iseven(n-1);
fun pow (x : int, n : int) : int =
if n = 0 then 1
else x * pow(x,n-1);
fun quad (x : int) : int =
x * x;
fun qpow (x : int, n : int) : int =
if n = 0 then 1
else if n mod 2 = 0 then quad(qpow(x,n div 2))
else quad(qpow(x,n div 2)) * x;
fun le (s : int list, n : int) : int list =
if null(s) then nil
else if hd(s) < n then hd(s) :: le(tl(s),n)
else le(tl(s),n);
fun eq (s : int list, n : int) : int list =
if null(s) then nil
else if hd(s) = n then hd(s) :: eq(tl(s),n)
else eq(tl(s),n);
fun gr (s : int list, n : int) : int list =
if null(s) then nil
else if hd(s) > n then hd(s) :: gr(tl(s),n)
else gr(tl(s),n);
fun qsort (s : int list) : int list =
if null(s) then s
else qsort(le(s,hd(s))) @ eq(s,hd(s)) @ qsort(gr(s,hd(s)));
fun insort (y : int, w : int list) : int list =
if null(w) then [y]
else if y <= hd(w) then y :: w
else hd(w) :: insort(y,tl(w));
fun sort (s : int list) : int list =
if null(s) then s
else insort(hd(s),sort(tl(s)));
fun rest (s : string) : string =
substring(s,1,size(s)-1);
fun lp (p : string, s : string) : bool =
if size(p) <= size(s) then substring(s,0,size(p)) = p
else false;
fun patmat (s : string, p : string) : int =
if s = "" then 10000
else if lp(p,s) then 1
else patmat(rest(s),p) + 1;
fun listsucc (s : int list) : int list =
if null(s) then s
else (hd(s)+1) :: listsucc(tl(s));
fun patmatlist (s : string, p : string) : int list =
if s = "" then nil
else if lp(p,s) then 1 :: listsucc(patmatlist(rest(s),p))
else listsucc(patmatlist(rest(s),p));
fun isqrt1 (n : int) : int =
if n = 0 then 0
else if (isqrt1(n-1)+1) * (isqrt1(n-1)+1) <= n
then isqrt1(n-1) +1
else isqrt1(n-1);
fun isqrtaux (x : int, n : int) : int =
if (x+1) * (x+1) <= n then x + 1
else x;
fun isqrt2 (n : int) : int =
if n = 0 then 0
else isqrtaux(isqrt2(n-1),n);
fun divides (a : int, b : int) : bool =
if a = 0 then b = 0
else b mod a = 0;
fun primesaux (a : int, b : int) : bool =
if a > b then true
else not(divides(a,b+1)) andalso primesaux(a+1,b);
fun isprim (a : int) : bool =
if a <= 1 then false
else primesaux(2,a-1);
fun primeslist (n : int) : int list =
if n <= 0 then nil
else if isprim(n) then primeslist(n-1) @ [n]
else primeslist(n-1);
(* SECOND RELEASE INCLUDING DATATYPES AND PATTERN MATCHING *)
datatype intpair = mk of int * int;
fun p1 (mk(a,b) : intpair) : int = a;
fun p2 (mk(a,b) : intpair) : int = b;
fun H (mk(a,b) : intpair) : intpair = mk(b,a+b);
fun F (n : int) : intpair =
if n = 0 then mk(1,1)
else H(F(n-1));
fun fib (n : int) : int = p1(F(n));
datatype stree = empty | mk of stree * int * stree;
fun left (mk(l,x,r) : stree) : stree = l;
fun right (mk(l,x,r) : stree) : stree = r;
fun node (mk(l,x,r) : stree) : int = x;
fun isempty (empty : stree) : bool =
true
| isempty (mk(l,x,r) : stree) : bool =
false;
datatype pair = mk of int * int;
datatype pairlist = empty | append of pair * pairlist;
fun mult (mk(a,b) : pair) : int = a * b;
fun mkpl (s : int list, t : int list) : pairlist =
if null(s) then empty
else append( mk(hd(s),hd(t)) , mkpl(tl(s),tl(t)) );
fun map ( empty : pairlist) : int list = []
| map (append(p,s) : pairlist) : int list = mult(p) :: map(s);
fun reduce (s : int list) : int =
if null(s) then 0
else hd(s) + reduce(tl(s));
fun scalar (s : int list, t : int list) : int =
reduce(map(mkpl(s,t)));
datatype res = none | intres of int;
fun succ (none : res) : res = none
| succ (intres(x) : res) : res = intres(x+1);
fun rest (s : string) : string =
substring(s,1,size(s)-1);
fun lp (p : string, s : string) : bool =
if size(p) <= size(s) then substring(s,0,size(p)) = p
else false;
fun patmat (s : string, p : string) : res =
if s = "" then none
else if lp(p,s) then intres(1)
else succ(patmat(rest(s),p));
(* THIRD RELEASE INCLUDING TUPLES AND LOCAL DECLARATIONS *)
fun isqrt (n : int) : int =
if n = 0 then 0
else let val (x : int) = isqrt(n-1) + 1
in if x * x <= n then x
else x - 1
end;
fun minlist ([x] : int list): int =
x
| minlist (x::xs : int list) : int =
let val (m : int) = minlist(xs)
in if x > m then m
else x
end;
fun merge ([] : int list, t : int list) : int list =
t
| merge (s : int list, [] : int list): int list =
s
| merge (x::xs : int list, y::yt : int list): int list =
if x <= y then x :: merge(xs,y::yt)
else y :: merge(x::xs,yt);
fun split ([] : int list) : int list * int list =
([],[])
| split ([x] : int list) : int list * int list =
([x],[])
| split (x::y::ys : int list) : int list * int list =
let val (u : int list, v : int list) = split(ys)
in (x::u,y::v)
end;
fun mergesort (s : int list) : int list =
if length(s) <= 1 then s
else let val (u : int list, v : int list) = split(s)
in merge(mergesort(u),mergesort(v))
end;