(* ==============================================
   Cours 2 - Syntaxe OCaml : let rec
   ============================================== *)

(* -------------------------------------------------
   1. Récursion sur les entiers
   ------------------------------------------------- *)

(* --- 1.1 Factorielle --- *)
let rec factorielle n =
  if n <= 1 then 1
  else n * factorielle (n - 1)

let () =
  Printf.printf "factorielle 5 = %d\n" (factorielle 5)

(* --- 1.2 Somme des n premiers entiers --- *)
let rec somme_entiers n =
  if n = 0 then 0
  else n + somme_entiers (n - 1)

let () =
  Printf.printf "somme_entiers 100 = %d\n" (somme_entiers 100)

(* --- 1.3 Puissance : x^n --- *)
let rec puissance x n =
  if n = 0 then 1
  else x * puissance x (n - 1)

let () =
  Printf.printf "puissance 2 10 = %d\n" (puissance 2 10)

(* --- 1.4 Suite de Fibonacci --- *)
let rec fib n =
  if n <= 1 then n
  else fib (n - 1) + fib (n - 2)

let () =
  Printf.printf "fib 10 = %d\n" (fib 10)

(* --- 1.5 Compter les pairs dans [1..n] --- *)
let rec compte_pairs n =
  if n = 0 then 0
  else (if n mod 2 = 0 then 1 else 0) + compte_pairs (n - 1)

let () =
  Printf.printf "compte_pairs 10 = %d\n" (compte_pairs 10)

(* -------------------------------------------------
   2. Récursion sur les listes (pattern matching)
   ------------------------------------------------- *)

(* --- 2.1 Longueur d'une liste --- *)
let rec longueur lst =
  match lst with
  | [] -> 0
  | _ :: xs -> 1 + longueur xs

let () =
  Printf.printf "longueur [10;20;30;40] = %d\n" (longueur [10; 20; 30; 40])

(* --- 2.2 Somme des éléments --- *)
let rec somme_liste lst =
  match lst with
  | [] -> 0
  | x :: xs -> x + somme_liste xs

let () =
  Printf.printf "somme_liste [1..5] = %d\n" (somme_liste [1; 2; 3; 4; 5])

(* --- 2.3 Produit des éléments --- *)
let rec produit_liste lst =
  match lst with
  | [] -> 1
  | x :: xs -> x * produit_liste xs

let () =
  Printf.printf "produit_liste [2;3;4] = %d\n" (produit_liste [2; 3; 4])

(* --- 2.4 Dernier élément (None si vide) --- *)
let rec dernier lst =
  match lst with
  | [] -> None
  | [x] -> Some x
  | _ :: xs -> dernier xs

let () =
  Printf.printf "dernier [1;2;3] = %s\n"
    (match dernier [1; 2; 3] with Some n -> string_of_int n | None -> "None")

(* --- 2.5 Concaténer deux listes --- *)
let rec concatene lst1 lst2 =
  match lst1 with
  | [] -> lst2
  | x :: xs -> x :: concatene xs lst2

let () =
  Printf.printf "concatene [1;2] [3;4] = [%s]\n"
    (String.concat "; " (List.map string_of_int (concatene [1; 2] [3; 4])))

(* --- 2.6 map : appliquer une fonction à chaque élément --- *)
let rec map f lst =
  match lst with
  | [] -> []
  | x :: xs -> f x :: map f xs

let () =
  Printf.printf "map (x->x*x) [1;2;3] = [%s]\n"
    (String.concat "; " (List.map string_of_int (map (fun x -> x * x) [1; 2; 3])))

(* --- 2.7 filter : garder les éléments vérifiant un prédicat --- *)
let rec filter p lst =
  match lst with
  | [] -> []
  | x :: xs ->
    if p x then x :: filter p xs
    else filter p xs

let () =
  Printf.printf "filter pair [1..6] = [%s]\n"
    (String.concat "; " (List.map string_of_int
      (filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5; 6])))

(* --- 2.8 Range : construire [n; n-1; ...; 1] --- *)
let rec range n =
  if n <= 0 then []
  else n :: range (n - 1)

let () =
  Printf.printf "range 5 = [%s]\n"
    (String.concat "; " (List.map string_of_int (range 5)))

(* --- 2.9 reverse : inverser une liste --- *)
let rec reverse lst =
  match lst with
  | [] -> []
  | x :: xs -> reverse xs @ [x]

let () =
  Printf.printf "reverse [1;2;3] = [%s]\n"
    (String.concat "; " (List.map string_of_int (reverse [1; 2; 3])))

(* -------------------------------------------------
   3. Récursion mutuelle (let rec...and)
   ------------------------------------------------- *)

(* Pair et impair définis récursivement *)
let rec pair n =
  n = 0 || n > 0 && impair (n - 1)
and impair n =
  n = 1 || n > 0 && pair (n - 1)

let () =
  Printf.printf "pair 6  = %B\n" (pair 6);
  Printf.printf "impair 6 = %B\n" (impair 6)

(* -------------------------------------------------
   4. Bonus : combiner map et filter
   ------------------------------------------------- *)

(* Doubler les éléments pairs *)
let double_pairs lst =
  map (fun x -> 2 * x) (filter (fun x -> x mod 2 = 0) lst)

let () =
  Printf.printf "double_pairs [1..8] = [%s]\n"
    (String.concat "; " (List.map string_of_int (double_pairs [1; 2; 3; 4; 5; 6; 7; 8])))