czesc1.sml

(*
 * Tomasz Zdybel
 * Zadanie domowe 1, czesc 1
 *  structure file
 *)
structure id291585 :> PART_ONE =
struct
  exception NotImplemented

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

  fun sum n =
		if n=1 then 1
		else n+sum(n-1);

  fun fac n =
		if n=1 then 1
		else fac(n-1)*n;

  fun fib n =
		if n<3 then 1
		else fib(n-2)+fib(n-1);

  fun gcd (m,n) =
		if m=n then m
		else if m>n then gcd((m-n),n)
		else gcd(m,(n-m));

  fun max (l:int list) =
		case l of
		nil=>0
		| head::nil=>head
		| head::tail=> if head>max tail then head
		  else max tail;

  fun sumTree (t:int tree) =
		case t of
		Leaf l=>l
		| Node(left,n,right)=> sumTree (left)+n+sumTree(right);

  fun depth (t:'a tree) =
		case t of
		Leaf l=>0
		| Node(left,n,right)=>if depth(left)>depth(right) then depth(left)+1
		  else depth(right)+1;

  fun binSearch (t:int tree) (x:int) =
		case t of
		Leaf l=>l=x
		| Node(left,n,right)=> if x=n then true
		  else if x<n then binSearch left x
		  else binSearch right x;

  fun preorder (t:'a tree) =
		case t of
		Leaf l=>[l]
		| Node (left,n,right)=>[n] @ preorder(left) @ preorder(right);

  fun listAdd [] (b:int list)= b
    		| listAdd (a:int list) [] = a
   		| listAdd (a:int list as heada :: taila) (b:int list as headb :: tailb) =
       		(heada + headb) :: listAdd taila tailb;

  fun insert (m:int) [] = [m]
    		| insert (m:int) (l:int list as head::tail) =
        	if m < head then m :: l
       		else head :: insert m tail;
  fun insort [] = []
    		| insort (l:int list as head :: tail) =
       		insert head (insort tail);
 
  fun compose f g = (fn x => g (f x));

  fun curry f x y = f(x,y);

  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));

  fun ltake _ _ = raise NotImplemented
  fun lall _ _ = raise NotImplemented

  fun lmap f [] = [] 
		| lmap f (head::tail) =
   		(f head)::(lmap f tail);

  fun lrev _ = raise NotImplemented
  fun lzip _ = raise NotImplemented
  fun split _ = raise NotImplemented
  fun cartprod _ _ = raise NotImplemented

end