(* Trevor Linton, HW 4 CS 6100, 00160339 *)

(* Problem 1 *)
let rec fib n =
	if n <= 1 then 1
	else ( fib (n-1) ) + ( fib (n-2) );;

(* Problem 2 *)
let rec fib1 n a b =
	if n <= 1 then b else
	(fib1 (n-1) b (a+b) );;

(* This ran considerably faster, however the
   result was skewed by one from fib *)

(* Problem 3 *)
let rec fac n =
	if n = 0 then 1
	else (n * (fac (n-1)));;

let rec fac1 n ans = 
	if n=0 then ans
	else (fac1 (n-1) (n*ans));;

(* Problem 4 *)
let rec foo n =
	if n=0 then 1 
	else (n - (foo (n-1)));;

let rec foo1 n ans =
	if n=0 then ans
	else (foo1 (n-1) (n-ans));;

(* Problem 5 *)
let rec foo5 x = 
	(l x x 1)
and l u x z =
	if x=0 then z
	else (m u (x-1) (x-1) u z)
and m u v x y z =
	if x=0 then (l u v (y-z))
	else (m u v (x-1) (y-1) z);;

(* Problem 6 *)
type 'a tree = Node of 'a * 'a tree * 'a tree | Leaf;;

let rec sum = function
	[] -> 0
	| i :: l -> i + sum l;;

let rec minlst = function
	  Node (x, Leaf, Leaf)	-> x
	| Node (x, left, right) when sum(x) <= sum(minlst(left)) && sum(x) <= sum(minlst(right)) -> x
	| Node (x, left, right) when sum(minlst(left)) <= sum(x) && sum(minlst(left)) <= sum(minlst(right)) -> minlst(left)
	| Node (x, left, right) when sum(minlst(right)) <= sum(x) && sum(minlst(right)) <= sum(minlst(left)) -> minlst(right)
	| Node (x, left, Leaf)	when sum(x) <= sum(minlst(left)) -> x
	| Node (x, left, Leaf)  when sum(minlst(left)) <= sum(x) -> minlst(left)
	| Node (x, Leaf, right) when sum(x) <= sum(minlst(right)) -> x
	| Node (x, Leaf, right) when sum(minlst(right)) <= sum(x) -> minlst(right)
;;


(* Problem 7 *)



Eval - 
Attempts to use beta reductions to create a unary lambda function from the application of one function to another.

Ctoi -
Defines term inc as a function which increments the number then applies inc to t and the resulting function has 0 applied to it then is evaluated.  The result of it is to print out the number given by a lambda evaluation.

ctoi1 - 
This definition shows how the true operator works, since one and two are passed into the tt operator which has signature \x.\y. x effectively the second arguement is ignored and only the first (one) is evaluated.

succ -
	Essentially it applies the inc lambda function to the incoming value which increases it by one by wrapping it into another E lambda expression resulting in a higher integer.