let booland : bool*bool -> bool = function (x,y) -> match (x,y) with
      (false, false) -> false |
       (true, false) -> false | (* one case less *)
      (true, true)  -> true ;;

let rec sumseq: int -> int = function n ->if n =1 then 1 
                                       else n+ (sumseq (n-1)) ;;
     (* summing first n integers *)

 let rec power : int*int -> int = function (a,b) -> if b = 0 then 1
                                                else a*power(a,b-1) ;;

let rec sumseqexp: int*int -> int = function (n,t)  -> if n =1 then 1 
                                       else power(n,t) + (sumseqexp(n-1, t)) ;;

 let rec mysum : int*int -> int = function (a,b) -> if b = 0 then a
  
                                 else succ ( mysum (a, pred (b))) ;;

 exception Input_type of string ;;

 let rec fact n = match (n <0) with
     true -> raise (Input_type "factorial not defined for negative") | 

      false -> if n = 0 then 1 else n*fact(n-1) ;;


  let rec ifib (n, x, fib1, fib2) = if x = n then fib1 else
                                      ifib(n, x+1, fib2, fib1+fib2) ;;
 


   let rec minlist lst = match lst with 
                []  -> raise (Input_type "Empty list not defined") |
                [x] -> x |
                hd::tail -> let y = minlist tail 
                            in
                   if hd < y then hd else y ;;

  
 let rec length lst = match lst with
                 [] -> 0 |
               hd::tail -> 1 + (length tail) ;; (* computes the length of list*)

  let rec reverse lst = match lst with

                 [] ->  [] |
                hd::tail -> (reverse tail)@ [hd] ;;

(* enumerative data type *)

type months = Jan | Feb | March ;;
type date = {dd : int ; mm : months ; yy : int} ;;

let validdate = function x -> match x.mm with
                    Jan -> if ( x.dd > 31 || x.dd < 1) then "Not Valid"
                                 else "Valid" |

                    Feb -> if x.yy mod 4 = 0 then if x.dd <= 29 then "Valid"
                                              else "Not Valid"
                        else if x.dd <= 28 then "Valid" else "not Valid" |


                    March -> if ( x.dd > 31 || x.dd < 1) then "Not Valid"
                                 else "Valid" ;;

(* record/structure data type *)
type rational = { num : int ; den : int } ;;
let ratmult (x , y ) = { num = x.num * y.num ; den = x.den * y.den } ;;

(* Variant data type  *)

type number = Int of int | Float of float | Rational of rational | Invalid ;;

let mulnumber (x, y) = match ( x, y) with
        (Int a , Int b) -> Int ( a * b ) |
        ( Float a , Float b) -> Float ( a *. b ) |
        (Rational a , Rational b) -> Rational ( ratmult (a,b) ) |
        (Int a , Float b) -> Float ( (float a ) *. b ) |
        (Int a , Rational b) -> Rational ( { num = a* b.num ; den = b.den });;


 (* recursively defined structures *)
type 'a lst = Empty | Element of 'a * 'a lst ;;

let list1 = Element (2 , Element(3, Element( 1, Empty))) ;;

let rec mylength l = (* l is our defn of 'a lst *)
  
       match l with
    Empty ->  0 |
    Element (a , b) -> 1 + mylength (b) ;;

(* Create a list of random numbers *)

 let randlist (len, bnd) = if len < 0 then raise (Input_type "positive only")
         else let rec mylist (i, lst) = if i = 0 then lst else
                                    mylist( i-1 , (Random.int bnd)::lst)
                   in   mylist(len, []) ;; 

(* Insertion Sort *)

 let rec insort lst = (* insertion sort starting from last element *)

        let rec insert elt lst = (* the insertion function defined locally*)
        match lst with [] -> [elt] |
        head :: tail -> if elt <= head then elt :: lst else
                              head :: insert elt tail
           in
 match lst with [] ->[] |
          head :: tail -> insert head (insort tail) ;;
 let l1 = [ 5 ; 1; -5 ; 10 ; 23 ; 98 ; -102 ];;


let rec small lst = match lst with  (* returns all elem smaller than first*)
         [] -> [] |
         [x] -> [] |
       x::y::tail -> if y <= x then [y]@small (x::tail) else small (x::tail);;

 let rec large lst = match lst with
         [] -> [] |
         [x] -> [] |
         x::y::tail -> if y > x then [y]@large (x::tail) else large (x::tail);;

 let rec qsort lst = match lst with
   [] -> [] |
   [x] -> [x] |
   x::tail -> qsort(small lst)@[x]@qsort(large lst) ;;

 let rec select lst k = 
        let rec cnt lst = match lst with
           [] -> 0 |
           [x] -> 1 |
           x::y::tail -> if x >= y then 1 + cnt ( x::tail ) else cnt (x::tail)
                in let m = cnt lst in 
           if m = k then match lst with
                           hd::tail -> hd 
                    else if m > k then select (small lst) k
                            else select (large lst) (k -m) ;;  

 let rec mymaplist (f ,lst) = match lst with 
                  [] -> [] |
                hd::tail -> (f hd) :: mymaplist (f , tail) ;;  



(* list iterater *)

let rec list_it f l e = match l with [] -> e |
          (a::l) -> f a (list_it f l e) ;;

 let mysum x y = x + y ;;

 (* tail recursive prefix *)

let prefix lst f = match lst with
                 [] -> [] |
                 [x] -> [x] |

        hd::tail ->
                    let rec prefix1 = function (inlist, outlist, last) ->
                    match inlist with [] -> outlist |
                hd::tail -> prefix1( tail, outlist@[ (f last hd)],(f last hd))

                  in
                  prefix1( tail, [hd], hd) ;;

(* curry transformation between multiparameter and one parameter function*)

let curry f = function x -> function y -> f(x,y) ;;
 let uncurry f = function (x,y) -> f x y ;;

let rec powerset l = match l with 
             []  ->   [[]] |
           hd::tail -> let cons a b = a::b in
                         (powerset tail) @ (List.map (cons hd) (powerset tail)) ;;

(* using bisection method for searching *)

let rec bisection  = function (* passing function f as a parameter *)

       (low, high, f , eps) -> if ( f ((low +. high)/. 2.0) > eps) then
                                  bisection (low, (low +. high)/. 2.0, f, eps)
                         else if (f ((low +. high)/. 2.0) +. eps < 0.0)
                            then bisection((low +. high)/. 2.0, high, f, eps)
                               else (low +. high)/. 2.0  ;;

 bisection (0.0 , 8.0 , (function x -> x*.x -. 8.0 ) , 0.001) ;;



  (* Arrays *)

let rand_int_array  n = Array.init n (function i -> Random.int (n*n)) ;;

(* an array of random integers in the range n*n *)


let rec binsearch arr x i j = let mid = (i+j)/2 in (* binary search *)

              if ((j-i <= 1) && (arr.(i)<> x) && (arr.(j) <> x)) then ~-1
                                       (* not succeeded in length 2 array*)
      else if arr.(mid) = x then mid

               else if arr.(mid) > x then binsearch arr x i (mid-1)

                            else binsearch arr x (mid+1) j  ;;


let swap i j arr2 =  let y = arr2.(j) in ( arr2.(j) <- arr2.(i) ;
 arr2.(i) <- y ) ; arr2 ;;  (* exchanging elements from index i and j *)


 (* array of arrays where each array has different length *)

  let b = Array.init 4 ( function i -> (Array.init (i+1) (function j -> i))) ;;


let rec insortarr arr i j = (* insertion sort where i ..j are sorted *)

 let rec insert k j arr1 =  (* insert arr1.(j) in the correct position
                               in sorted portion (k) .. (j-1) *)
   if k = j then arr1
    else if arr1.(j-1) <= arr1.(j) then arr1
           else insert k (j-1) ( swap (j-1) j arr1) 
                     in
                         (* recursive insertion sort *)
    if ( j= (Array.length arr) - 1 ) then arr 
           else
          insortarr (insert i (j+1) arr) i (j+1) ;;


 (* write a while loop *) 

 let ifib1 n = let prev = ref 0 and curr = ref 1 and i = ref 0 in

(* prev , curr and i can be modified *)


              while (!i < n) do
                curr := !curr + !prev ;
                prev := !curr - !prev ;
                  i := !i+ 1
                          (* invariant Fib(i) = !prev, Fib(i+1) = !curr *)
                done ;
             !prev ;;



 let iterbinsrch arr x low high =   
      let i = ref low and j = ref high and mid = ref ((low + high)/2) in

     while not (((!j- !i <= 1) && (arr.(!i)<> x) && (arr.(!j) <> x))) do

 (* if arr.(mid) > x then binsearch arr x i (mid-1)
                            else binsearch arr x (mid+1) j *)

          if arr.(!mid) > x then j := !mid -1 else i := !mid + 1;
              mid := (!i + !j)/2 ;
              
         done;
       if arr.(!mid) = x then !mid else ~-1 ;;