🔥 Cours 1 — Programmation Fonctionnelle

Objectif et plan

Objectif : découvrir la programmation fonctionnelle avec OCaml, comprendre pourquoi c'est important, et apprendre les bases.

1. Histoire et importance d'OCaml
2. Développer un programme OCaml (REPL, compilation)
3. Fonctions : trois formes, variations, récursion
4. Listes : construction, pattern matching, récurseur
5. map, filter, fold…

Pourquoi OCaml est le plus important

Histoire : Né à l'INRIA (Caml → OCaml en 1996).

• Typage fort + inférence : le compilateur détecte les erreurs sans qu'on écrive les types
• Pattern matching exhaustif : un oubli → warning
• Immutabilité par défaut : une fonction = une fonction
• Performance : compilateur natif, proche du C
• Industrie : Jane Street (60M lignes), Facebook (Infer), Docker, Bloomberg
• Langage du prouveur Coq (preuve formelle)

Comment développer un programme OCaml

Trois manières :

1. Toplevel (REPL) : ocaml, tapez des expressions
2. Script : ocaml prog.ml
3. Compilation : ocamlc -o prog prog.ml ou ocamlopt -o prog prog.ml (natif)

# 1 + 2 * 3;;
- : int = 7
# let carre x = x * x;;
val carre : int -> int = <fun>

Les trois formes de fonctions

1. Anonyme (lambda) :

fun x -> x * x
fun x y -> x + y

2. Nommée :

let carre x = x * x
let somme a b = a + b

3. Récursive : let rec permet de s'appeler soi-même

let rec fact n =
  if n <= 1 then 1
  else n * fact (n - 1)

Fonctions : variations et application partielle

Plusieurs écritures, même résultat :

let add a b = a + b           (* classique *)
let add = fun a b -> a + b     (* lambda *)
let add = (+)                  (* alias d'opérateur *)

Application partielle :

let add5 = add 5   (* val add5 : int -> int *)
(* add5 3 → 8 *)

Opérateurs personnalisés :

let ( *** ) x y = x * x + y * y   (* 3 *** 4 → 25 *)

La factorielle (récursion simple)

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

Évaluation de factorielle 4 : 4 × (3 × (2 × (1 × 1))) = 24

Problème : chaque appel empile n × … sur la pile. O(n) en pile → débordement pour n grand.

Récursion terminale (tail rec)

Idée : accumulateur pour le résultat partiel.

let rec fact_tail n acc =
  if n <= 1 then acc
  else fact_tail (n - 1) (n * acc)

let factorielle n = fact_tail n 1

Évaluation : fact_tail 4 1 → fact_tail 3 4 → fact_tail 2 12 → fact_tail 1 24 → 24

Plus de pile à déplier : OCaml transforme en boucle. O(n) en temps, O(1) en pile.

Le récurseur sur ℕ

On extrait le motif de la récursion :

let rec recurse n z f =
  if n = 0 then z
  else f n (recurse (n - 1) z f)

recurse généralise toute récursion sur un entier :

let factorielle n = recurse n 1 ( * )
let somme n       = recurse n 0 (+)
let puissance x n = recurse n 1 (fun _ acc -> x * acc)

Listes en OCaml

Deux constructeurs :

• [] — liste vide
• x :: xs — ajoute x devant xs (cons)

Sucre syntaxique : [1; 2; 3] = 1 :: 2 :: 3 :: []

Pattern matching :

let rec somme lst = match lst with
  | [] -> 0
  | x :: xs -> x + somme xs

Récurseur sur listes (fold_right)

let rec recurse_list f z lst = match lst with
  | [] -> z
  | x :: xs -> f x (recurse_list f z xs)

C'est fold_right : on remplace [] par z, :: par f.

let produit  = recurse_list ( * ) 1
let somme    = recurse_list (+) 0
let longueur = recurse_list (fun _ acc -> acc + 1) 0

map, filter, fold

let map f lst =
  recurse_list (fun x acc -> f x :: acc) [] lst
  (* map (fun x -> x*2) [1;2;3] → [2;4;6] *)

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] *)

Prochain cours

Cours 2 : le mot-clé type, les types algébriques (sommes, produits, arbres, AST), le pattern matching exhaustif, la compilation en bytecode.