zadanie1.sml

(*LOGIKA
  zadanie 1
*)

structure id291408 :> PART_ONE=
struct
  exception NotImplemented

datatype 'a tree =
    Leaf of 'a
  | Node of 'a tree * 'a * 'a tree

(*0.1. Funkcje liczb całkowitych.*)
fun sum n =
    if n=1 then 1
    else n + sum (n-1);
    
fun fac n =
    if n=1 then 1
    else n * fac (n-1);

fun fib n =
    if n=0 orelse n=1 then 1
    else fib (n-1)+fib (n-2);
    
fun gcd(a,b) =
    if a=b then a
    else 
        if a>b then gcd (a-b,b)
        else gcd (a,b-a);
        
fun max (head::tail) = if head > max tail then head else max tail
|   max (nil) = 0;

(* 0.2. Funkcje na drzewach binarnych *)
fun sumTree (Leaf n) = n
  |   sumTree (Node (left, n, right)) = (sumTree left) + n + (sumTree right);

fun depth (Leaf n) = 0
|   depth (Node (l,n,r)) = if depth r > depth l then 1+depth r else 1+depth l;

fun binSearch (Leaf t) x = if t=x then true else false
|   binSearch (Node (l,t,p)) x= 
        if t=x then true else 
        if x<t then binSearch l x 
        else binSearch p x;

fun preorder (Leaf t) = [t]
|   preorder (Node (l,t,p))= [t] @ preorder l @ preorder p;


(* 0.3. Funkcje na listach liczb całkowitych. *)
fun listAdd (a::at) (b::bt) = [a+b] @ listAdd at bt
|   listAdd (nil) (b::bt) = [b] @ listAdd nil bt
|   listAdd (a::at) (nil) = [a] @ listAdd at nil
|   listAdd (nil) (nil) =   [];

fun insert  el (a::at) = if el <= a then [el] @ [a] @ at else [a] @ insert el at
|   insert  el (nil) = [el];

fun insort (a::at) = insert a (insort at)
|   insort (nil) = [];

(* 0.4. Funkcje wyższego rzędu. *)
fun compose f g = fn(x)=>g(f(x));
 
fun curry f a b= f(a,b);

fun uncurry f(a,b)= f a b;

fun multifun f n = 
  if n=1 then fn(x) => f(x) 
  else fn(x)=>f(multifun f (n-1) x);

(* 5. Funkcje na liście ’a list *)
fun ltake (l::lt) n = if n>0 then [l] @ ltake lt (n-1) else []
|   ltake (nil) n = [];

fun lall f (l::lt)  = if f l then true andalso lall f lt else false
|   lall f (nil)    = true;

fun lmap f (l::lt)  = [f l] @ lmap f lt
|   lmap f (nil)    = [];

fun lrev (l::lt)  = lrev lt @ [l]
|   lrev (nil)    = [];

fun lzip ((a::at),(b::bt))  = [(a,b)] @ lzip (at,bt)
|   lzip ((nil),(b::bt)) = []
|   lzip ((a::at),(nil)) = []
|   lzip ((nil),(nil)) = [];

fun even (l::l2::lt) = [l2] @ even lt
|   even (l::nil)= []
|   even (nil) = [];

fun odd (l::l2::lt) = [l] @ odd lt
|   odd (l::nil)= [l]
|   odd (nil) = [];

fun split l = (odd l, even l);

fun cartprod (S::St) (T::Tt) = [(S,T)] @ cartprod [S] Tt @ cartprod St (T::Tt)
|   cartprod (nil) (T::Tt)= []
|   cartprod (S::St) (nil)= []
|   cartprod (nil) (nil)= [];

end