czesc1.sml

(*
 * Zadanie domowe 1, czesc 1
 *  structure file
 *)
structure id283224 :> 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 sum (n-1) + n
  
  fun fac n = 
  if n = 2 then 2
  else fac(n-1)*n

  fun fib n =
  if n = 0 then 1
  else if n = 1 then 1
  else fib(n-1)+fib(n-2)
  
  fun gcd (n,m) = 
  if n = m then n
  else if n>m then gcd(n-m,m)
  else gcd(n,m-n)
  
  fun max (l:int list) =
	case l of
		nil => 0
		| head :: tail =>
			if tail = [] orelse head > max tail then head
			else max tail

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

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

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

  fun preorder (t:'a tree) =
    case t of
		Leaf left => [left]
		| Node(left,value,right) => [value] @ preorder left @ preorder right;
    
  fun listAdd (a:int list) [] = a
	| listAdd [] (b:int list) = b
    | 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 (l:int list) =
    case l of
		nil => nil
		| head :: tail => insert head (insort tail)

  fun compose f g  = (fn x => g (f x))
  
  fun curry x y z = x (y,z)
  
  fun uncurry f (x,y) = f x y
  
  fun multifun f n = 
    if n = 1 then (fn x => f x)
    else (fn x =>f ( (multifun f (n-1)) x ))

  fun ltake _ 0 = []
    |ltake [] _ = []
    |ltake (head::tail) n = head::(ltake tail (n-1))

  fun lall _ [] = true
    |lall f (head::tail)= if (f head) then (lall f tail) else false

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

  fun lrev [] = []
    |lrev (head::tail) = (lrev tail) @ [head]

  fun lzip ([],_) = []
    |lzip (_,[]) = []
    |lzip ((heada::taila),(headb::tailb)) = (heada,headb)::(lzip (taila,tailb))

  fun split [] = ([],[])
    |split [x] = ([x],[])
    |split (head1::head2::tail) = 
		let val (a,b) = split tail
        in ((head1::a),(head2::b)) end
  
  fun cartprod _ [] =[]
    |cartprod [] _ = []
    |cartprod (heada::taila) (headb::tailb) = 
		(heada,headb)::cartprod(heada,tailb) @ cartprod(taila,(headb::tailb))

end