(* Cours 1: introduction *)

(* les fonctions *)

let id = fun x -> x;;

(* ... recursives *)

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

(* ... definies par cas *)

let rec fact = function 
                  0 -> 1
               |  n -> n* fact (n-1);;

let rec pgcd = function
                 (0,n) -> n
               | (m,n) -> pgcd (n mod m, m);;

pgcd (30,12);;

(* recursion mutuelle *)

let rec paire = function 0 -> true 
                       | n -> impaire (n-1)
and impaire   = function 0 -> false
                       | n -> paire (n-1);;

(* le filtre "fourre-tout" _ *)

let not = function
            true -> false
          |  _   -> true;;

not true;;
not false;;

let booland = function
            (true,true) -> true
          | (true,false) -> false
          | (false,true) -> false
          | (false,false) -> false;;

let booland = function
            (true,true) -> true
          |      _      -> false;;

booland (false,false);;

(* quelque type interessant *)

let compose = fun f -> fun g -> fun x -> f (g x);;

let k = fun x -> fun y -> x;;

let s = fun x -> fun y -> fun z -> (x z) ( y z);;

(* Des programmes!!!! *)

(* Iterations bornees *)

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

iter 10 (fun x -> x+1) 1;;

let fibeff n = fst (iter n (fun (x,y) -> (x+y,x)) (1,0));;

(* Iterations non bornees *)

let rec loop p f x = if p x then x else loop p f (f x);;

(* fonction de McCarty *)

let rec mc  n = if n > 100 then n -10
                           else mc (mc (n+11));;