(* Recursion *)

let rec pow (a : int ) (n : int) : int =
    match n with
        0 -> 1
    |   1 -> a
    |   other -> a * pow a (n - 1)
;;

let rec float_pow (a : float) (n : int) : float =
    if ((a < 0.0) && (n mod 2 != 0)) then
        -.float_pow (abs_float a) n
    else if((a < 0.0) && (n mod 2 == 0)) then
        float_pow (abs_float a) n
    else if (n = 0) then
        1.0
    else if (n = 1) then
        a
    else
        a *. float_pow a (n - 1)
;;

(* When testing negative a, I did float_pow (-.a) n *)

let rec print_list = function (* Function taken from Stack Overflow to help print lists *)
    [] -> ()
    | head::tail -> print_int head ; print_string " " ; print_list tail ;
;;


let rec reverse list =
    reverse_helper [] list
and reverse_helper acc = function
    | [] -> acc
    | head::tail -> reverse_helper (head::acc) tail
    (* (head::acc) puts the first elemen of the current list at the "back" until the last element of the list is put first *)
;;

let rec compress = function
    | [] -> []
    | head::(next:: _ as tail) -> compress_helper head next tail
    | (_:: _ as tail) -> tail
and compress_helper head next tail =
    if (head = next) then
        compress tail
    else
        head::compress tail
;;

let rec cluster list =
    cluster_helper [] [] list
and cluster_helper biglist smalllist = function
    | [] -> []    (* Can only be reached if original list is empty *)
    | [singleton] -> (singleton :: biglist) :: smalllist
    | head :: (next :: _ as tail) -> if head = next then cluster_helper (head :: biglist) smalllist tail else cluster_helper [] ((head :: biglist) :: smalllist) tail
;;

    (* NOTE: Can also use accumulator for this function. Check adjacent elements, create new list if they are not the same. *)

let slice list i j = function
    | [] -> []
    | _::_ -> []
;;
(* Couldn't do slice *)

(* pow tests *)
print_int(pow 3 10);;
print_string("\n");;
print_int(pow 2 8);;
print_string("\n");;

(* float_pow tests *)
print_float(float_pow (-2.2) 2);;
print_string("\n");;
print_float(float_pow (-27.1) 3);;
print_string("\n");;
print_float(float_pow (27.1) 2);;
print_string("\n");;
print_float(float_pow 4.0 2);;
print_string("\n");;

(* List tests *)
let a_list = [1;2;3;4;5];;
let b_list = [1;2;3;4;5;6;7;8;9;10];;
let uncompressed_list = [10;10;20;30;40;40;40;50];;
let unclustered_list = [1;1;1;2;3;3;1;1];;
print_list a_list;;
let reversed_list = reverse a_list;;
print_string("\n");;
print_list reversed_list;;
print_string("\nUncompressed List: ");;
print_list uncompressed_list;;
let compressed_list = compress uncompressed_list;;
print_string("\nCompressed List: ");;
print_list compressed_list;;
print_string("\n");;
(* let sliced_list = slice b_list 3 2;;
print_list sliced_list;;
print_string("\n");; *)

(* Higher-order functions *)

let composition f g x =
    f (g x)
;;

let rec equiv_on f g lst : bool =
    match lst with
    | [] -> true
    | head::tail -> (f head = g head) && (equiv_on f g tail); (* Checks if all corresponding indexes from lst are the same with functions f and g applied to them *)
;;

let rec pairwisefilter cmp lst =
    match lst with
    | [] -> []
    | head::next::tail -> cmp head next :: pairwisefilter cmp tail
    | _ as remaining -> remaining
;;


let square x = x * x;;
let increment x = x + 1;;
let f i = i * i;;
let g i = 3 * i;;

let square_of_increment = composition square increment;;
print_int(square_of_increment 4);;
print_string("\n");;
equiv_on f g [1;2;3];; (* booleans are not printed*)
equiv_on f g [3];; (* booleans are not printed*)

let min a b = if a > b then b else a;;
let pairwisefilter_list = pairwisefilter min [14; 11; 20; 25; 10; 11; 12];;
print_list pairwisefilter_list;;
print_string("\n");;


let polynomial lst x =
    let rec aux lst x =
        match lst with
        | [] -> 0
        | head::tail -> match head with (a, b) -> a * pow x b + aux tail x
        in aux lst x
    ;;

let f = polynomial [3, 3; -2, 1; 5, 0];;
print_int(f 3);;

(* Data types *)

(* Truth Table *)
type bool_expr =
    | Lit of string
    | Not of bool_expr
    | And of bool_expr * bool_expr
    | Or of bool_expr * bool_expr
    ;;

let rec evaluate_truth_table a a_val b b_val = function
    | Lit str -> if str = a then a_val else b_val
    | Not expr -> not(evaluate_truth_table a a_val b b_val expr)
    | Or(val_1, val_2) -> evaluate_truth_table a a_val b b_val val_1 || evaluate_truth_table a a_val b b_val val_2
    | And(val_1, val_2) -> evaluate_truth_table a a_val b b_val val_1 && evaluate_truth_table a a_val b b_val val_2
    ;;

let truth_table a b bool_expr =
    [(true, true, evaluate_truth_table a true b true bool_expr);
    (true, false, evaluate_truth_table a true b false bool_expr);
    (false, true, evaluate_truth_table a false b true bool_expr);
    (false, false, evaluate_truth_table a false b false bool_expr)]
    ;;

let truth_table_test = truth_table "a" "b" (Or(And(Lit("a"), Lit("b")), Not(Lit("a"))));;
(* (bool * bool * bool) list = [(true, true, true); (true, false, false); (false, true, true); (false, false, true)] *)
(* End of Truth Table *)


type 'a binary_tree =
    | Empty
    | Node of 'a * 'a binary_tree * 'a binary_tree
    ;;

let rec tree2str = function
    | Empty -> ""
    | Node(root, child1, child2) -> tree2str_helper root child1 child2
and tree2str_helper root child1 child2 =
    match child1, child2 with
    | (Empty, Empty) -> string_of_int root
    | (_, _) -> string_of_int root ^ "(" ^ tree2str child1 ^ "," ^ tree2str child2 ^ ")"
    ;;

let intList : list = [1;3;4;5;6];;
let clusterIntList : list = cluster intList;;
print_list (intList);;

let a_tree = Node(1, Node(2, Node(4, Empty, Empty), Node(5, Empty, Empty)),
Node(3, Node(6, Empty, Empty), Node(7, Empty, Empty)));;
print_string("\n");;
let tree2str_test = tree2str a_tree;;
print_string(tree2str_test);;