(* 1. Produit des éléments d'une liste *)
let rec produit lst =
  match lst with
  | [] -> 1
  | x :: xs -> x * produit xs
(* produit [2; 3; 4] = 24 *)

(* 2. Généralisation : fold_right sur les listes *)
let rec recurse_list : 'a 'b. ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b =
  fun f z lst -> match lst with [] -> z | x :: xs -> f x (recurse_list f z xs)

(* 3. Variante fold_left (parcours gauche→droite) *)
let rec recurse_list_g : 'a 'b. ('b -> 'a -> 'b) -> 'b -> 'a list -> 'b =
  fun f z lst -> match lst with [] -> z | x :: xs -> recurse_list_g f (f z x) xs

(* produit avec recurse_list *)
let produit2 lst = recurse_list ( * ) 1 lst
(* produit2 [2; 3; 4] = 24 *)

(* 4. Applications de recurse_list (fold_right) *)

(* a. Somme des éléments *)
let somme lst = recurse_list (+) 0 lst
(* somme [1; 2; 3; 4] = 10 *)

(* b. Longueur d'une liste *)
let longueur lst = recurse_list (fun _ acc -> acc + 1) 0 lst
(* longueur [7; 8; 9] = 3 *)

(* c. Concaténation de deux listes *)
let concatene lst1 lst2 = recurse_list (fun x acc -> x :: acc) lst2 lst1
(* concatene [1; 2] [3; 4] = [1; 2; 3; 4] *)

(* d. Renversement d'une liste (efficace avec recurse_list_g) *)
let renverse lst = recurse_list_g (fun acc x -> x :: acc) [] lst
(* renverse [1; 2; 3] = [3; 2; 1] *)

(* e. Map : appliquer une fonction à chaque élément *)
let map f lst = recurse_list (fun x acc -> f x :: acc) [] lst
(* map (fun x -> x * x) [1; 2; 3] = [1; 4; 9] *)

(* f. Filter : garder les éléments vérifiant un prédicat *)
let filter p lst = recurse_list (fun x acc -> if p x then x :: acc else acc) [] lst
(* filter (fun x -> x mod 2 = 0) [1; 2; 3; 4] = [2; 4] *)

(* g. Maximum d'une liste (None si vide) *)
let maximum lst =
  recurse_list (fun x acc ->
    match acc with
    | None -> Some x
    | Some m -> Some (max x m)) None lst
(* maximum [3; 7; 2; 9; 1] = Some 9 *)

(* h. Appartenance : test si un élément est dans la liste *)
let appartient x lst =
  recurse_list (fun y acc -> acc || y = x) false lst
(* appartient 3 [1; 2; 3; 4] = true *)

(* i. Concaténation de listes de listes *)
let aplatir lst = recurse_list (fun xs acc -> recurse_list (fun x acc' -> x :: acc') acc xs) [] lst
(* aplatir [[1; 2]; [3]; [4; 5]] = [1; 2; 3; 4; 5] *)

(* j. Zip : combine deux listes en une liste de paires (tronque à la plus courte) *)
let rec zip xs ys =
  match xs, ys with
  | [], _ | _, [] -> []
  | x :: xs', y :: ys' -> (x, y) :: zip xs' ys'

(* 5. Applications de recurse_list_g (fold_left) *)

(* k. Découpage : prend les n premiers éléments *)
let prendre n lst =
  let (_, res) = recurse_list_g (fun (i, acc) x ->
    if i < n then (i + 1, x :: acc)
    else (i + 1, acc)) (0, []) lst
  in
  renverse res
(* prendre 3 [10; 20; 30; 40; 50] = [10; 20; 30] *)

(* l. Supprimer les doublons consécutifs *)
let dedup lst =
  let (_, res) = recurse_list_g (fun (last, acc) x ->
    if Some x = last then (last, acc)
    else (Some x, x :: acc)) (None, []) lst
  in
  renverse res
(* dedup [1; 1; 2; 3; 3; 3; 4] = [1; 2; 3; 4] *)

(* m. Regroupement par paquets de taille k *)
let paquets k lst =
  let (reste, paq, res) = recurse_list_g (fun (i, paq, res) x ->
    if i < k - 1 then (i + 1, x :: paq, res)
    else (0, [], (renverse (x :: paq)) :: res)) (0, [], []) lst
  in
  let res = if reste > 0 then renverse paq :: res else res in
  renverse res
(* paquets 3 [1; 2; 3; 4; 5; 6; 7] = [[1; 2; 3]; [4; 5; 6]; [7]] *)

(* n. Premiers : garde les éléments ≤ n qui vérifient un prédicat *)
let prendre_tant_que p lst =
  let (_, res) = recurse_list_g (fun (ok, acc) x ->
    if ok && p x then (true, x :: acc)
    else (false, acc)) (true, []) lst
  in
  renverse res
(* prendre_tant_que (fun x -> x < 5) [1; 3; 7; 2; 9] = [1; 3] *)

(* o. Supprimer les n derniers éléments *)
let sauter_derniers n lst =
  let len = longueur lst in
  let (_, res) = recurse_list_g (fun (i, acc) x ->
    if i < len - n then (i + 1, x :: acc)
    else (i + 1, acc)) (0, []) lst
  in
  renverse res
(* sauter_derniers 2 [10; 20; 30; 40; 50] = [10; 20; 30] *)

(* p. Regrouper par alternance (pair → liste A, impair → liste B) *)
let separer lst =
  recurse_list_g (fun (l1, l2) x ->
    (x :: l2, l1)) ([], []) lst
(* separer [1; 2; 3; 4; 5; 6] = ([6; 4; 2], [5; 3; 1]) *)

let () =
  Printf.printf "produit [2;3;4]       = %d\n" (produit [2; 3; 4]);
  Printf.printf "produit2 [2;3;4]      = %d\n" (produit2 [2; 3; 4]);
  Printf.printf "somme [1..4]          = %d\n" (somme [1; 2; 3; 4]);
  Printf.printf "longueur [7;8;9]      = %d\n" (longueur [7; 8; 9]);
  Printf.printf "concatene [1;2] [3;4] = [%s]\n" (String.concat "; " (List.map string_of_int (concatene [1; 2] [3; 4])));
  Printf.printf "renverse [1;2;3]      = [%s]\n" (String.concat "; " (List.map string_of_int (renverse [1; 2; 3])));
  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])));
  Printf.printf "filter pair [1;2;3;4] = [%s]\n" (String.concat "; " (List.map string_of_int (filter (fun x -> x mod 2 = 0) [1; 2; 3; 4])));
  Printf.printf "maximum [3;7;2;9;1]   = %s\n" (match maximum [3; 7; 2; 9; 1] with Some n -> string_of_int n | None -> "None");
  Printf.printf "appartient 3 [1..4]   = %B\n" (appartient 3 [1; 2; 3; 4]);
  Printf.printf "aplatir [[1;2];[3];[4;5]] = [%s]\n" (String.concat "; " (List.map string_of_int (aplatir [[1; 2]; [3]; [4; 5]])));
  Printf.printf "zip [1;2;3] [4;5;6]   = [%s]\n" (String.concat "; " (List.map (fun (a, b) -> Printf.sprintf "(%d,%d)" a b) (zip [1; 2; 3] [4; 5; 6])));
  Printf.printf "prendre 3 [10;20;30;40;50] = [%s]\n" (String.concat "; " (List.map string_of_int (prendre 3 [10; 20; 30; 40; 50])));
  Printf.printf "dedup [1;1;2;3;3;3;4] = [%s]\n" (String.concat "; " (List.map string_of_int (dedup [1; 1; 2; 3; 3; 3; 4])));
  Printf.printf "paquets 3 [1..7]      = [%s]\n" (String.concat "; " (List.map (fun l -> "[" ^ String.concat ";" (List.map string_of_int l) ^ "]") (paquets 3 [1; 2; 3; 4; 5; 6; 7])));
  Printf.printf "prendre_tant_que (<5) [1;3;7;2;9] = [%s]\n" (String.concat "; " (List.map string_of_int (prendre_tant_que (fun x -> x < 5) [1; 3; 7; 2; 9])));
  Printf.printf "sauter_derniers 2 [10;20;30;40;50] = [%s]\n" (String.concat "; " (List.map string_of_int (sauter_derniers 2 [10; 20; 30; 40; 50])));
  let (l1, l2) = separer [1; 2; 3; 4; 5; 6] in
  Printf.printf "separer [1..6]        = ([%s], [%s])\n" (String.concat ";" (List.map string_of_int l1)) (String.concat ";" (List.map string_of_int l2))