(* Problem 1 *)

let rec fold (base, step) list =
    match list with
          [] -> base
        | hd :: tl -> step (hd, fold (base, step) tl)

let concat ll = fold ([], fun (hd, acc) -> hd @ acc) ll 

let this = concat [[]; [1]; [2; 3]; [4; 5; 6]; [7; 8]; [9]; []]



(* Problem 2 *)

let revcat ll =
    let rec loop ll acc =
        match ll with
              [] -> acc
            | [] :: tail -> loop tail acc 
            | (h :: tl) :: tail -> loop (tl :: tail) (h:: acc)
 in
    loop ll []

let that = revcat [[]; [1]; [2; 3]; [4; 5; 6]; [7; 8]; [9]; []]



(* Problem 3 *)

type 'a t = Z | S of 'a
type nat = R of nat t

let rec fold f n = match n with R Z -> f Z | R (S m) -> f (S (fold f m))  
 
let rec unfold g n = match g n with Z -> R Z | S m -> R (S (unfold g m))

let int2nat u = unfold (fun m -> if m = 0 then Z else S (m-1)) u

let nat2int v =   fold (fun n -> match n with Z -> 0 | S m -> m+1) v

let x = int2nat 3
let y = nat2int x