cours1

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));;