let double x = 2*x
let square x = x*x
let twice f x = f (f x)
let quad = twice double
let fourth = twice square

let ( $ ) f x = f x 

# square 2+2 ;;
- : int = 6
# square $ 2+2 ;;
- : int = 16

let ( @@ ) f g x = x |> g |> f

let rec repeat f n x =
  if n > 0
  then repeat f (n-1) (f x)
  else x
;;

 let fold_left f init lst =
  let rec impl acc f = function
    |[] -> acc
    |h::t -> impl (f acc h) f t
  in
  impl init f lst
;;

let product_left flst =
  fold_left (fun acc f -> acc*.f) 1.0 flst
;;

let product_right flst =
  List.fold_right (fun acc f -> acc *. f) flst 1.0
;;

let product_left  = fold_left ( *. ) 1.  ;;

let product_right flst = List.fold_right ( *. ) flst 1. ;;

let sum_cube_odd n =
  let lst = 0 -- n in
    fold_left ( + ) 0 (map (fun x -> x*x*x) lst)
;;

let sum_cube_odd_pipeline  n =
   let lst = 0 -- n in
     lst |> map (fun x -> x*x*x) |> fold_left ( + ) 0 
 ;;

let rec exists_rec p  = function 
  |[] -> false 
  |h::t -> (p h) || exists_rec t
;;

let exists_fold p lst =
  List.fold_left (fun acc e -> (p e) || acc) false lst  ;;

let exists_lib = List.exists;;

let rec account_balance1 acc lst =
  match (acc , lst) with
  | (a , _ ) when a <= 0 -> 0
  | (a , [])  -> a
  | (a, h::t ) -> account_balance1 (a-h) t
;;

let account_balance2 account lst =
  List.fold_left (fun acc e -> if acc>e then (acc - e) else 0) account lst
;;

let account_balance3 account lst =
  List.fold_right  (fun e acc  -> if acc>e then (acc - e) else 0) lst account 
;;

let uncurried_nth (lst, n) = List.nth lst n

let uncurried_append (h,t) = List.append h t ;;

let uncurried_char_compare (c1 , c2) = Char.compare c1 c2 ;;

let uncurried_stdlib_max (fst,snd) = Stdlib.max fst snd ;;

let uncurried_two_args  f2 (fst,snd) =  f2 fst snd  ;;

uncurried_two_args List.append ;;
uncurried_two_args Char.compare ;;
uncurried_two_args Stdlib.max ;;

let map_compose f g lst =
  let ( @@ ) f g x = x |> g |> f  in 
  List.map (f@@g ) lst
;;

let len_greater_then_three strs =
  List.filter (fun s -> String.length s >3) strs ;;

let add_float_one lst =
  List.map (fun x -> x +. 1.0) lst ;;

let concat_with_sep sep = function 
  | [] -> ""
  | h::t -> List.fold_left (fun acc e -> acc ^ sep ^ e) h t 
;;

let keys dict =
  dict |> List.map (fun (k,v) -> k) |> List.sort_uniq Stdlib.compare ;;

open OUnit2
open Stdlib

let is_valid_matrix  = function
    |[] -> false
    |[[]] -> false 
    |r::rows -> let l = List.length r in
       List.fold_left (fun acc e ->  (l!=0) && (List.length e = l)  && acc)  true rows

(**************************UNIT TEST****************************)
let make_test_case  name expected matrix =
  name >:: (fun _ -> assert_equal expected (is_valid_matrix matrix) )  

let test_suites = "is_valid_matrix" >::: [
    make_test_case "empty list" false [] ;
    make_test_case "empty int list" false [[]] ;
    make_test_case "more empty row vectors" false [[];[];[]];
    make_test_case "1-dim row vectors"  true  [[1];[2];[23]] ;
    make_test_case "row counts != colument counts"  false [[2];[23;4];[2;4]];
    make_test_case "3*3 matrix" true [[1;2;4];[3;4;5];[4;5;6]] ;
  ] 

let _ = run_test_tt_main test_suites  

open OUnit2
open Stdlib

(*
let add_row_vectors v1 v2 =
  if List.length v1 != List.length v2 then failwith "two vectors must have same dim"
  else 
    let rec impl acc v1 v2 =
      match (v1,v2) with 
      | (h1::t1,h2::t2) -> impl ((h1 + h2)::acc) t1 t2
      | _ -> List.rev acc
    in  impl [] v1 v2
;;
*)

let map2 op lst1 lst2 =
  if List.length lst1 != List.length lst2 then raise ( Invalid_argument "two lists should have same length" )
  else
    let rec loop acc l1 l2 = match (l1,l2) with
      | (h1::t1, h2::t2) -> loop ((op h1 h2)::acc) t1 t2
      | _ -> List.rev acc
    in loop [] lst1 lst2
;;


let add_row_vectors = map2 ( + ) ;;

let make_test_equal name  expected v1 v2 =
  name >:: (fun _ -> assert_equal expected  (add_row_vectors v1 v2) )

let make_test_raise name  v1 v2 =
  name >:: (fun _ -> assert_raises (Invalid_argument "two lists should have same length") (fun _ -> add_row_vectors v1 v2) ) 


let test_add_row_vectors = "add_row_vectors" >:::[
    make_test_equal "empty vectors" [] [] [] ;
    make_test_raise "different length" [2;4] [2;4;5];
    make_test_equal "add 3-dim vectors" [4;4;4]  [1;2;3] [3;2;1] ; 
  ]


let _ = run_test_tt_main test_add_row_vectors 

(** matrix.ml *)
let is_valid_matrix  = function
    |[] -> false
    |[[]] -> false 
    |r::rows -> let l = List.length r in
       List.fold_left (fun acc e ->  (l!=0) && (List.length e = l)  && acc)  true rows 

let fold_map  op init f lst1 lst2  =
    if List.length lst1 != List.length lst2 then raise ( Invalid_argument "two lists should have same length" )
    else
    let rec loop acc l1 l2 = match (l1,l2) with
      | (h1::t1, h2::t2) -> loop (op (f h1 h2) acc) t1 t2
      | _ -> acc
    in loop init lst1 lst2
;;

let map2 f l1 l2  =List.rev (fold_map (fun e acc -> e::acc) [] f l1 l2) ;;

let add_row_vectors = map2 ( + ) 

let add_matrices = map2 add_row_vectors ;;

let dot_product_row_vectors = fold_map ( + ) 0 ( * ) ;;

let colu_vector_of_row_vector  = List.map (fun e -> [e] )

let cons_colu_and_row colu row =  map2 ( @ )  colu (colu_vector_of_row_vector row)

let transpose_matrix m =
  if not(is_valid_matrix m) then raise (Invalid_argument "the input matrix is invalid")
  else
    match m with
    | h::t -> List.fold_left  cons_colu_and_row  (colu_vector_of_row_vector h) t
    | _ -> raise (Invalid_argument "the input matrix is invalid") 
;;

let multiply_matrices m1 m2 =
  let n = (transpose_matrix m2) in
  let rec impl acc m1 = 
    match m1 with
    |[] -> List.rev acc 
    |row::rest  ->   impl ((List.map  (fun x -> dot_product_row_vectors x row) n  )::acc) rest 
  in impl [] m1
;;