(* I Fonctions récursives *)
(* I.1 Somme des n premiers entiers *)
let rec somme (n : int) : int = match n with
  | 0 -> 0
  | _ -> n + somme (n - 1) ;; (* bien faire attention aux parenthèses pour n - 1 ! *)


somme 10 ;; 

(* I.2 Une variante de la précédente *)
let rec somme_f (f : int -> int) (n : int) : int = match n with
  | 0 -> f 0
  | _ -> f n + somme_f f (n - 1) ;; 
  
somme_f (function x -> x * x * x) 100 ;;
  
(* I.3 Versions récursives de la division euclidienne *)
let rec quotient (a : int) (b : int) : int = match a with
  | _ when a < b -> 0
  | _ -> 1 + quotient (a - b) b ;;
(* L'idée est que si a < b alors le quotient est nul. Dans le cas contraire c'est qu'il y a au moins une fois b dans a, et donc la réponse est 1 + le quotient de (a - b) par b *)  
quotient 55 8 ;;

let rec reste (a : int) (b : int) : int = match a with
  | _ when a < b -> a
  | _ -> reste (a - b) b ;;

reste 55 8 ;;

(* I.4 Nombre de chiffres d'un entier *)
let rec nbdigits (n : int) : int =
  match n with
  | n when n < 10 -> 1
  | _ -> 1 + nbdigits (n / 10) ;;

nbdigits 3;;
nbdigits 35;;
nbdigits 3537462;;

(* II Fonctionnelles *)
(* II.1 Fonctionnelles simples *)
let h1  (f : float -> float) : float = (f 0. +. f 1.) /. 2. ;;
let h2 (f : float -> float) (x : float)  : float = (f x) *. (f x) ;; (* Noter qu'ici rien n'impose le type de l'argument de f *)
let h3 (f : float -> float) = function x -> (f x) ** 2. ;; (* Et là non plus... *)
let h4 (f : float -> float) = function x -> f (f x) ;; (* et là même le type de ce qui est rendu par f est libre... *)
let h5 (f : float -> float) = function x -> f (x +. 1.) ;;

(* II.2 *)
let compose  (f : 'a -> 'b) (g :'c -> 'a) : 'c -> 'b = function x -> f (g x) ;;

let mini (f : 'a -> 'b) (g : 'a -> 'b) : 'a -> 'b = function x -> min (f x) (g x) ;;

let max_comp (f : 'a -> 'a) (g : 'a -> 'a) : 'a -> 'a = function x-> max (f (g x)) (g (f x)) ;;

(* II.3 Différences finies *)
(* Bien comprendre qu'une suite est une fonction de N dans quelque chose, ici R *)
let delta (u : int -> float) : int -> float = function n -> u (n + 1) -. u n ;;

(* II.4 Curryfication, décurryfication *)
let curry (f : 'a * 'b -> 'c) : 'a -> 'b -> 'c = fun x y -> f (x, y) ;;
function (x, y) -> x * y ;; (* une fonction anonyme non curryfiée à deux variables *)
curry (function (x, y) -> x * y) ;; (* La même fonction curryfiée ! *)

let uncurry (f : 'a -> 'b -> 'c) : 'a * 'b -> 'c  = function (x, y) -> f x y ;;
fun x y -> x * y ;; (* Une fonction anonyme curryfiée à deux variables *)
uncurry (fun x y -> x * y) ;; (*La même fonction décurryfiée ! *)

(* II.5 Fonctionnelle récursive *)
let rec iter (f : int -> 'a -> 'a) (x : 'a) (n : int) : 'a =
  match n with
  | 0 -> f 0 x
  | _ -> f n (iter f x (n - 1)) ;;

iter (fun x y -> x + y) 2 5;;
(* devrait rendre 17 selon le schéma suivant
f(0,2) = 2, puis f(1,2) = 3, puis f(2,3) = 5, puis f(3,5) = 8, puis f(4, 8) = 12 et enfin f(5, 12) *)