Cours 3 — Monades (OCaml)

« Monade est un mot qui fait peur. En réalité, une monade est juste un pattern qui revient tout le temps, comme le fait de devoir ranger sa chambre : c'est chiant, mais une fois qu'on a compris, tout est plus propre. »

Introduction

Rappel du cours 2 : Types algébriques, types sommes et produits, arbres binaires, AST, compilation en bytecode et machine à pile.

Ce cours : le pattern bind/return appliqué à option (calculs qui échouent), list (non-déterminisme, requêtes), et parsec (analyse syntaxique).

Le type option (rappel)

option = None (absence) ou Some x (valeur).

let safe_div a b =
  if b = 0 then None
  else Some (a / b)

Problème : chaîner devient verbeux.

let f x = match safe_div 10 x with
  | None -> None
  | Some y -> match safe_div y 2 with
    | None -> None
    | Some z -> Some (z + 1)

La monade option (bind/return)

let ( >>= ) opt f = match opt with
  | None -> None
  | Some x -> f x

let retour x = Some x

Avec >>= (bind), on chaîne les calculs élégamment :

let exemple =
  safe_div 10 2 >>= fun y ->
  safe_div y 2 >>= fun z ->
  retour (z + 1)
(* val exemple : int option = Some 3 *)

« La monade Option, c'est comme un colis Amazon : soit il arrive (Some), soit il est "perdu dans la chaîne logistique" (None). Et bind, c'est le livreur qui enchaîne les livraisons sans vous faire remplir un formulaire à chaque étape. »

Avant / Après

Sans monade :

let f x y z = match safe_div x y with
  | None -> None
  | Some a -> match safe_div a z with
    | None -> None
    | Some b -> Some (b + 1)

Avec monade :

let f x y z =
  safe_div x y >>= fun a ->
  safe_div a z >>= fun b ->
  retour (b + 1)

La monade Liste

'a list = plusieurs résultats possibles (non-déterminisme).

let retour x = [x]

let ( >>= ) m f = List.concat (List.map f m)
(* concat map : chaque élément peut produire 0, 1 ou N résultats *)

« Le bind de la monade Liste, c'est comme un distributeur de chewing-gums qui, pour chaque chewing-gum, vous en redonne plusieurs. Vous finissez avec une montagne de chewing-gums. »

Produit cartésien

let cartesian xs ys =
  xs >>= fun x ->
  ys >>= fun y ->
  retour (x, y)
(* cartesian [1;2;3] ["a";"b"] =
   [(1,"a"); (1,"b"); (2,"a"); (2,"b"); (3,"a"); (3,"b")] *)

Triplets pythagoriciens

let pythagore n =
  let r = List.init n (fun i -> i + 1) in
  r >>= fun a ->
  r >>= fun b ->
  r >>= fun c ->
  if a * a + b * b = c * c then retour (a, b, c)
  else []
(* pour n = 10 → [(3,4,5); (4,3,5); (6,8,10); (8,6,10)] *)

[] = échec (on filtre), retour = succès. On traduit l'énoncé mathématique littéralement.

Parties d'un ensemble (power set)

let rec parties = function
  | [] -> [[]]
  | x :: xs ->
    parties xs >>= fun p ->
    [p; x :: p]
(* parties [1;2;3] =
   [[]; [1]; [2]; [1;2]; [3]; [1;3]; [2;3]; [1;2;3]] *)

Monade Parsec — Analyse syntaxique

Problème : lire une chaîne, extraire une structure, gérer les erreurs.

type 'a parser = char list -> ('a * char list) option
(* [entrée] -> Some (résultat, reste) ou None *)

Le type dit tout : prend des caractères, retourne un résultat et le reste, ou échoue.

let retour x = (fun s -> Some (x, s))

let ( >>= ) p f =
  fun s -> match p s with
    | None -> None
    | Some (x, s') -> f x s'

Parseurs de base

let item = function          (* un caractère *)
  | [] -> None
  | c :: s -> Some (c, s)

let car c =                  (* un caractère précis *)
  item >>= fun x ->
  if x = c then retour x else None

let chiffre =                (* un chiffre *)
  item >>= fun c ->
  if '0' <= c && c <= '9' then retour c
  else None

On combine les parseurs avec >>= : car 'a' >>= fun _ -> car 'b' >>= fun _ -> chiffre lit "ab3" et retourne Some ('3', []).

Combinateurs

let ( <|> ) p q = fun s ->    (* p ou q *)
  match p s with
  | Some r -> Some r
  | None -> q s

let rec many p s =            (* 0 ou plus *)
  match p s with
  | None -> Some ([], s)
  | Some (x, s') ->
    many p s' >>= fun xs ->
    retour (x :: xs) s'

Des monades partout

Monade	Type	retour	>>= (bind)
`option`	`'a option`	`Some x`	`None → skip`
`list`	`'a list`	`[x]`	`concat map`
`parsec`	`char list → ...`	`fun s → Some (x,s)`	`passe l'état`
`writer`	`'a * string list`	`(x,[])`	`concatène logs`
`async`	`Promise`	`Promise.resolve`	`.then()`

« Le pattern bind/return est partout. Une fois vu, vous le verrez dans Promise.then, Optional.flatMap (Java), $_.then (jQuery)… »

« Les monades, c'est comme les lasagnes : des couches. Mais contrairement aux lasagnes, on peut les composer sans avoir mal au ventre. »

📄 monade_liste.ml 📄 parsec.ml 📄 annexe_monades.tex 📖 Polycopié PDF 📽️ Slides PDF

Prochain cours

Cours 4 : on utilise tout ça pour implémenter un mini-réseau de neurones en OCaml pur.

🔄 Cours 3 — Monades