open FunUtils

let rec n_fold n f = if n = 0 then id else o f (n_fold (n-1) f)

let int2ch = n_fold (* synonym for n_fold *)

let ch2int c = c ((+) 1) 0

let succ c = fun f -> o f (c f)

let nonce = fun f x -> x

(* In the following, eta expansion makes OCAML's types less restrictive *)
let once f x = succ nonce f x (* acts like (fun f x -> f x) = n_fold 1 = id *)

let twice f x = succ once f x (* acts like (fun f x -> f (f x)) = n_fold 2 *)

let thrice f x = succ twice f x (* acts like (fun f x -> f (f (f x))) = n_fold 3 *)

let plus c1 c2 = fun f -> o (c1 f) (c2 f)

let plus' c1 c2 = ((c1 succ) c2)

(* Version of the Y operator from Kevin Milliken/Gopolan Nadathur's notes at: 
   http://www.itlabs.umn.edu/HyperNews/get/gopalan/courses/CSCI8980-fall-2001/classwork/2.html *)

type 'a wrap = Wrap of ('a wrap -> 'a)

let y =
   fun f ->
     (fun (Wrap x) -> f (x (Wrap x)))
     (Wrap (fun (Wrap x) -> f (fun y -> x (Wrap x) y)))

let fact = y (fun f n -> if n == 0 then 1 else n * f(n - 1));;

let chTrue = fun x y -> x

let chFalse = fun x y -> y

let chIf = fun b c a -> b (c()) (a()) (* assumes branches are thunked *)

let chPair x y = fun f -> f x y

let chFst p = p (fun x y -> x)

let chSnd p = p (fun x y -> y)

let chNil = fun c n -> n

let chCons x xs = fun c n -> c x (xs c n)

(* Conceptually, chHd should be easy -- something like

      let chHd xs = xs (fun x ans -> x) ??

    where ?? can be anything. But must go through hoops to 
    satsify the OCAML type checker. The following uses the
    fact that the infinite loop (y (fun f n -> f n) id)
    can have any return type in order to allow the folding
    function to have the right type. 

 *)

let chHd xs = (xs (fun x ans -> (fun () -> x)) (fun () -> (y (fun f n -> f n) id))) ()

let chTl xs = chSnd (xs (fun x p -> chPair (chCons x (chFst p)) (chFst p))
                    (chPair chNil chNil))

let chIsNull xs = xs (fun x ans -> chFalse) chTrue

(*************************************************************
In the following definitions, 

(1) You should *NOT* use any of the following:
     * n_fold
     * ch2int
     * int2ch
     * recursion
 
(2) Your may use anything else, including:
     * id
     * o (composition) 
     * nonce
     * once
     * succ
 *************************************************************)

let times c1 c2 =  (* Replace this stub *) nonce

let expt c1 c2 = (* Replace this stub *) nonce

let pred c = (* Replace this stub *) nonce