(* Higher-Order Functions *)
let compose f g = fun x -> f (g x);;

let plus_two x = 2 + x;;

compose plus_two plus_two;;

compose plus_two;;

(* Thrice *)
let thrice f x = f (f (f x)) ;;

let thrice f = compose f (compose f f);;

let thrice f = compose (compose f f) f;;

let thrice f =
  let g = compose f f
  in compose f g;;

(* Curried vs Uncurried *)
let add_three x y z = x + y + z;;

let add_triple (u,v,w) = u + v + w;;

(* Partial Application *)

(+);;

(+) 2 3;;

let plus_two = (+) 2;;

plus_two 7;;

(* Lambda Lifting *)

let add_two = (+) (print_string "test"; 2);;

let add2 = fun x -> (+) (print_string "test"; 2) x;;

thrice add_two 5;;

thrice add2 5;;

(* Curry and Uncurry *)

(+);;

let curry f x y = f (x,y);;

let uncurry f (x,y) = f x y;;

let plus = uncurry (+);;

plus (3,4);;

curry plus 3 4 ;;

(* Reversing Arguments *)

let flip f a b = f b a;;

List.map ((-) 1) [5;6;7];;

List.map (flip (-) 1) [5;6;7];;

let (-) = flip (-);;

2 - 5;;

let (-) = flip (-);; (* put it back to normal *)

2 - 5;;

(* Folding Functions over Lists *)
let rec sumlist list = match list with
  | [] -> 0
  | x::xs -> x + sumlist xs;;

sumlist [2;3;4];;

let rec prodlist list = match list with
  | [] -> 1
  | x::xs -> x * prodlist xs;;

prodlist [2;3;4];;

(* Folding *)
let rec fold_left f a list = match list with
  | [] -> a
  |  x::xs -> fold_left f (f a x) xs;;

let rec fold_right f list b = match list with
  | [] -> b
  | x::xs -> f x (fold_right f xs b);;

let sumlist list = fold_right (+) list 0;;

sumlist [2;3;4];;

let prodlist list = fold_right ( * ) list 1;;

prodlist [2;3;4];;

(* Encoding Recursion with Fold *)

let rec append list1 list2 = match list1 with
  | [] -> list2
  | x::xs -> x :: append xs list2;;

let append list1 list2 = 
  fold_right (fun x y -> x :: y) list1 list2;;

(* Combining Lists of Functions *)
let rec complist flist = match flist with
  | [] -> (fun x -> x)
  | f::fs -> compose f (complist fs);;

complist [( - ) 1; ( * ) 3; plus_two];;

complist [( - ) 1; ( * ) 3; plus_two] 5;;

let complist flist = 
  fold_right (fun x y -> compose x y) flist (fun x -> x);;

complist [( - ) 1; ( * ) 3; plus_two] 5;;

(* Repeating n times *)
let rec repeat n f x =
  match n with
    | 0 -> x
    | _ -> f (repeat (n - 1) f x);;

repeat 8 (fun x -> x * 2) 1;;

let rec iter n f x = 
  match n with
      0 -> x
    | _ -> iter (n - 1) f (f x);;

iter 8 (fun x -> x * 2) 1;;

(* Mapping *)
let rec inclist list =
  match list with
    | [] -> []
    | x::xs -> (1 + x) :: inclist xs;;

inclist [2;3;4];;

let rec doublelist list = 
  match list with
    | [] -> []
    | x::xs -> (2 * x) :: doublelist xs;;

doublelist [2;3;4];;

let inclist list = List.map (fun x -> 1 + x) list;;

inclist [2;3;4];;

let doublelist list = List.map (fun x -> 2 * x) list;;

doublelist [2;3;4];;

(* Map from Fold *)
let map f list =
  fold_right (fun x y -> f x :: y) list [];;

map ((+) 1) [2;3;4];;

(* Related Function: Zip *)
let rec zip list1 list2 =
  match (list1,list2) with
    | ([],_) -> []
    | (_,[]) -> []
    | (x::xs,y::ys) -> (x,y)::zip xs ys;;

zip [1;2;3] [4;5;6];;

(* Zipwith *)
let rec zipwith f list1 list2 =
  match (list1,list2) with
    | ([],_) -> []
    | (_,[]) -> []
    | (x::xs,y::ys) -> f x y :: zipwith f xs ys;;

zipwith (+) [1;2;3] [4;5;6];;

zipwith (fun x y -> (x,y)) [1;2;3] [4;5;6];;

(* Zip from Zipwith *)
let zip = zipwith (fun x y -> (x,y));;

zip [1;2;3] [4;5;6];;

(* Sample problem 1 *)
let flipuc f = uncurry (flip (curry f));;

let minus (x,y) = x - y;;

minus (5,3);;

flipuc minus (5,3);;

let cons (x,xs) = x::xs;;

let snoc = flipuc cons;;

snoc(snoc ([1],2),3);;

(* Sample problem 2 *)
let app_fst f (a,c) = f a;;

app_fst ((+) 1) (3,7);;

app_fst ((+) 1) (4, "hi");;

(* Sample problem 3 *)
let listId list = fold_right (fun x xs -> x :: xs) list [];;

listId [1;2;3];;

(* Sample problem 4 *)
let gezero list = fold_right
  (fun x xs -> (if x >= 0 then x :: xs else xs)) list [];;

gezero [1;0;3;-5;7;-2];;