[an error occurred while processing this directive]

(* 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;




[an error occurred while processing this directive] 06-Sep-2006, 15:34:54 CEST [an error occurred while processing this directive]