```
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
in
match lst with [] ->[] |
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 ;;

```