Monades

1. Introduction

Dans le cours précédent, on a découvert l'opérateur |> (pipe) qui permet d'enchaîner des transformations de façon lisible :

[1; 2; 3; 4; 5]
  |> List.filter (fun x -> x mod 2 = 0)
  |> List.map (fun x -> x * 2)
  |> List.fold_left (+) 0

C'est simple : chaque fonction renvoie une valeur, la suivante la prend en entrée. Mais que se passe-t-il si une fonction peut échouer ? Ou retourner plusieurs résultats ? Ou dépendre d'un état global ?

Les monades sont la généralisation du pipe à ces cas plus complexes. Si le pipe, c'est "prends une valeur et applique-lui une fonction", la monade, c'est "prends une valeur dans un contexte et applique-lui une fonction qui peut enrichir ce contexte".

Le terme "monade" vient des mathématiques (théorie des catégories), mais pas de panique : on va les aborder par la pratique, sans formalismes inutiles.

Dans ce cours, on va parcourir plusieurs monades, de la plus simple à la plus abstraite :

1. Liste — le contexte du non-déterminisme (plusieurs résultats possibles).
2. Option — le contexte de l'échec possible (liste à 0 ou 1 élément).
3. State — le contexte de l'état mutable (simulé proprement).
4. Environnement (Reader) — le contexte de la configuration.
5. Continuation — le contexte du "et après ?" (la mère de toutes les monades).

2. Le problème

Imaginez qu'on veuille faire une division sécurisée : une fonction qui renvoie None si on divise par zéro.

let safe_div x y =
  if y = 0 then None else Some (x / y)

Maintenant, on veut chaîner plusieurs divisions : calculer 12 / 2 / 3 (= 2) de façon sécurisée. Avec le pipe |>, on ne peut pas écrire :

(* Ceci ne type PAS : safe_div attend des int, pas des option *)
Some 12 |> safe_div 2  (* erreur de type ! *)

On doit extraire manuellement la valeur de l'option :

let resultat =
  match Some 12 with
  | None    -> None
  | Some x  ->
      match safe_div x 2 with
      | None    -> None
      | Some y  -> safe_div y 3

C'est la pyramide de la mort (callback hell). Pour chaque étape, on vérifie manuellement si tout va bien. C'est répétitif, verbeux, et source d'erreurs.

2.1 Pipe ne suffit plus

Le pipe |>, c'est tout simplement :

let (|>) x f = f x

Il fonctionne quand x est une valeur brute et f prend une valeur brute. Mais quand x est une valeur dans un contexte (option, liste, …), on a besoin d'un opérateur qui comprend ce contexte.

Cet opérateur, c'est bind, noté >>= en OCaml (prononcez "bind"). Sa signature :

• ('a t) -> ('a -> 'b t) -> 'b t
• Soit : "étant donné une valeur dans un contexte t, et une fonction qui produit une valeur dans ce contexte, applique la fonction en gérant le contexte".

Et return (parfois pure) :

• 'a -> 'a t
• Soit : "met une valeur brute dans le contexte par défaut".

Avec ces deux opérateurs, on peut enfin écrire proprement :

// Le bind pour option *)
let (>>=) opt f =
  match opt with
  | None   -> None
  | Some x -> f x

(* return pour option *)
let return x = Some x

(* La division sécurisée en une ligne ! *)
return 12
  >>= safe_div 2
  >>= safe_div 3

Magique ! Si une division échoue, le None se propage automatiquement. Plus de pyramide, plus de match manuels.

OCaml (depuis 4.08) permet même d'utiliser le sucre let* pour écrire encore plus lisiblement :

// On déclare let* comme bind pour option *)
let (let*) = (>>=)

(* Et on peut écrire : *)
let resultat =
  let* x = return 12 in
  let* y = safe_div x 2 in
  safe_div y 3

Ça ressemble à du code impératif, mais c'est purement fonctionnel. Chaque let* "dépaquette" la valeur du contexte et la rend disponible pour la suite.

3. La Monade Liste

Maintenant qu'on a vu le principe général, attaquons la monade Liste — la star de ce cours, et celle qui relie le plus naturellement au cours 2 sur les ADT.

L'idée : une liste représente plusieurs résultats possibles pour un calcul (non-déterminisme). bind sur une liste, c'est "pour chaque élément de la liste, applique la fonction, et rassemble tous les résultats".

3.1 bind & return pour les listes

// bind pour les listes : flat_map / concat_map *)
let (>>=) lst f = List.flatten (List.map f lst)

// return pour les listes : singleton *)
let return x = [x]

Testons :

[1; 2; 3] >>= (fun x -> [x; x * 10])

Comprenez ce qui se passe : pour chaque élément de la liste d'entrée, on génère une liste de sortie, puis on concatène le tout. C'est le flat_map des listes (ou concat_map).

Avec let* :

let (let*) = (>>=)

let exemple =
  let* x = [1; 2; 3] in
  let* y = [10; 100] in
  return (x + y)

On vient de faire un produit cartésien ! Chaque let* "choisit" une valeur dans la liste, et on combine les choix. Ça revient à écrire :

// Équivalent sans monade, avec deux boucles imbriquées *)
List.flatten (
  List.map (fun x ->
    List.map (fun y -> x + y) [10; 100])
  [1; 2; 3])

3.2 Compréhensions de listes

Avec let* sur les listes, on a une syntaxe très proche des compréhensions de listes (list comprehensions) qu'on trouve en Python, Haskell, ou Scala.

En Python : [x+y for x in [1,2,3] for y in [10,100]]

En OCaml avec la monade liste :

// Toutes les combinaisons de (x, y) où x ∈ {1,2,3}, y ∈ {a,b} *)
let paires =
  let* x = [1; 2; 3] in
  let* y = ["a"; "b"] in
  return (x, y)

On peut aussi filtrer avec une condition (comme le if dans les compréhensions Python) :

// "Yeux de la coccinelle" : combinaisons de (x, y, z) où x+y+z = 10 *)
let yeux =
  let* x = [1; 2; 3] in
  let* y = [1; 2; 3] in
  let* z = [1; 2; 3] in
  let* _ = if x + y + z = 10 then [()] else [] in
  return (x, y, z)

Le filtre if utilise une astuce : si la condition est vraie, on retourne [()] (une liste avec un élément, qui "laisse passer"), sinon [] (liste vide, qui "bloque" la combinaison). C'est exactement le guard des compréhensions.

Application concrète : On a une table d'employés et une table de départements, on veut lister tous les employés avec leur département :

type employe = { nom: string; dept_id: int }
type departement = { id: int; nom_dept: string }

let employes = [
  { nom = "Alice"; dept_id = 1 };
  { nom = "Bob";   dept_id = 2 };
  { nom = "Eve";   dept_id = 1 };
]

let departements = [
  { id = 1; nom_dept = "R&D" };
  { id = 2; nom_dept = "Marketing" };
]

// Jointure avec la monade liste *)
let repertoire =
  let* emp   = employes in
  let* dept  = departements in
  let* _    = if emp.dept_id = dept.id then [()] else [] in
  return (emp.nom, dept.nom_dept)

C'est une requête de base de données écrite en OCaml pur ! Le let* fait la jointure, le if fait la condition de jointure.

3.3 Option : la liste à 0 ou 1 élément

Voici une révélation : option est un cas particulier de list où la liste a au plus 1 élément.

// Option est une Liste avec au plus un élément *)
let option_to_list opt =
  match opt with
  | None   -> []
  | Some x -> [x]

// Le bind de l'option est le flat_map limité à 0 ou 1 :
// - Si None → aucun résultat → None
// - Si Some x → un résultat → f x, qui doit donner Some ou None

Cette analogie est profonde : la monade liste est la mère de toutes les monades de "choix". L'option en est une version appauvrie (0 ou 1) mais très utile. La monade Result est une généralisation avec un message d'erreur (Ok 'a | Error 'e).

Et avec les binding operators d'OCaml (≥ 4.08), on peut même avoir des let* qui fonctionnent pour toutes les monades en même temps si on définit le bon let* — ou on peut utiliser des opérateurs par monade (let* pour les listes, let+ pour les options, etc.).

4. La Monade State

Parfois, on a besoin de maintenir un état qui évolue au fil des calculs : un compteur, un générateur de nombres aléatoires, un cache de mémoïsation. En programmation impérative, on utilise une variable mutable. En programmation fonctionnelle, on passe l'état explicitement.

La monade State encapsule ce passage d'état pour que vous n'ayez pas à le faire à la main.

L'idée : un calcul stateful est une fonction qui prend un état et retourne une valeur et un nouvel état :

// Un calcul stateful : 's → 'a * 's *)
type ('a, 's) state = State of ('s -> 'a * 's)

// Exécuter un calcul stateful *)
let run_state (State f) s = f s

Le return pour State : produit une valeur sans changer l'état.

let return x = State (fun s -> (x, s))

Le bind pour State : exécute le premier calcul, récupère la valeur et le nouvel état, puis exécute le second calcul.

let (>>=) (State m) f =
  State (fun s ->
    let (a, s') = m s in
    let (State g) = f a in
    g s')

On a aussi besoin de deux opérations de base :

• get : lire l'état courant.
• put : remplacer l'état courant.

// Lire l'état courant *)
let get = State (fun s -> (s, s))

// Écrire un nouvel état *)
let put s = State (fun _ -> ((), s))

Exemple : un compteur. On veut numéroter automatiquement des éléments :

// Incrémenter et retourner la nouvelle valeur *)
let tick =
  let* n = get in
  let* _ = put (n + 1) in
  return n

// Numéroter une liste *)
let numeroter lst =
  let* x    = lst in
  let* idx  = tick in
  return (idx, x)

// On lance le calcul avec état initial 0 *)
run_state (numeroter ["a"; "b"; "c"]) 0

Résultat : les éléments numérotés et l'état final (le compteur à 3).

4.1 Mémoïsation avec State

Un classique : Fibonacci avec mémoïsation. Naïvement, fib est exponentiel. Avec un cache (état), il devient linéaire :

// Cache de Fibonacci : une table associant n → fib(n) *)
let fib_memo n =
  let rec fib_state n =
    let* cache = get in
    match Hashtbl.find_opt cache n with
    | Some v -> return v
    | None   ->
        let* v =
          if n <= 1 then return n
          else
            let* a = fib_state (n - 1) in
            let* b = fib_state (n - 2) in
            return (a + b)
        in
        let* _ = put (Hashtbl.add cache n v; cache) in
        return v
  in
  fst (run_state (fib_state n) (Hashtbl.create 100))

Ce code est purement fonctionnel (le cache est encapsulé dans la monade State) tout en étant aussi efficace qu'une version impérative avec cache mutable. Le meilleur des deux mondes !

5. La Monade Environnement (Reader)

Parfois, on a juste besoin de lire une configuration, sans la modifier. Un paramètre global (une base de données, des réglages, un environnement) qu'on ne veut pas passer explicitement à chaque fonction.

La monade Reader (ou Environnement) encapsule ce pattern :

// Reader : un calcul qui lit dans un environnement 'r *)
type ('a, 'r) reader = Reader of ('r -> 'a)

let run_reader (Reader f) r = f r

// return : ignore l'environnement *)
let return x = Reader (fun _ -> x)

// bind : passe l'environnement à travers la chaîne *)
let (>>=) (Reader m) f =
  Reader (fun r ->
    let a = m r in
    let (Reader g) = f a in
    g r)

// ask : lire l'environnement *)
let ask = Reader (fun r -> r)

// local : exécuter un calcul dans un environnement modifié *)
let local f (Reader m) = Reader (fun r -> m (f r))

Vous remarquez la différence avec State ? Reader ne peut pas modifier l'environnement — il le passe juste à chaque étape. C'est ce qui le rend plus simple et plus sûr.

5.1 Évaluation contextuelle

Reprenons l'exemple des expressions arithmétiques du cours 2, mais avec des variables. L'environnement est une table qui associe des noms à des valeurs :

// Notre AST avec variables *)
type expr =
  | Const  of int
  | Var    of string
  | Add    of expr * expr
  | Let    of string * expr * expr

// Environnement de type : string → int *)
type env = (string, int) Hashtbl.t

// Évaluateur avec la monade Reader *)
let rec eval e =
  match e with
  | Const n      -> return n
  | Var x        ->
      let* r = ask in
      return (Hashtbl.find r x)
  | Add (e1, e2)  ->
      let* a = eval e1 in
      let* b = eval e2 in
      return (a + b)
  | Let (x, e1, e2) ->
      let* v = eval e1 in
      local (fun r -> Hashtbl.add r x v; r) (eval e2)

// Et on lance :*)
run_reader (eval (Add (Var "x", Const 1)))
  (Hashtbl.of_list ["x", 42])

Sans Reader, il faudrait passer l'environnement r manuellement à chaque appel récursif. Avec Reader, il est invisible : on l'obtient avec ask quand on en a besoin, et local permet de créer des sous-environnements.

6. La Monade Continuation

On arrive à la monade la plus abstraite (et la plus puissante) : la monade Continuation (Cont). Alors que List représente "plusieurs résultats", Option "peut-être un résultat", State "un résultat avec état", la Continuation représente "ce qu'on fait du résultat".

En programmation classique, une fonction retourne une valeur. En style par passages de continuation (CPS), une fonction prend un argument supplémentaire : une continuation — une fonction qui sera appelée avec le résultat.

// Style direct *)
let add x y = x + y

// Style par passages de continuation *)
let add_cps x y k = k (x + y)

La monade Continuation encapsule ce pattern :

// Continuation monad : ('a → 'r) → 'r *)
type ('a, 'r) cont = Cont of (('a -> 'r) -> 'r)

let run_cont (Cont f) k = f k

// return : passe la valeur à la continuation *)
let return x = Cont (fun k -> k x)

// bind : compose les continuations *)
let (>>=) (Cont m) f =
  Cont (fun k ->
    m (fun a ->
      let (Cont g) = f a in
      g k))

Mais à quoi ça sert ?

Avec la monade Continuation, on peut implémenter :

• L'exception précoce (early exit) — sortir d'un calcul avant la fin.
• Le backtracking — essayer plusieurs chemins, revenir en arrière si on échoue.
• Les coroutines — suspendre et reprendre un calcul.
• Le fork/join — lancer des calculs en parallèle et attendre les résultats.

En fait, la monade Continuation est la plus expressive de toutes : on peut simuler toutes les autres monades avec elle.

6.1 Early exit et backtracking

Exemple : on cherche un élément dans une liste, mais on veut s'arrêter dès qu'on trouve le premier. Avec la monade Cont, on peut "court-circuiter" :

// callcc : capturer la continuation courante *)
// (call-with-current-continuation de Scheme) *)
let callcc f =
  Cont (fun k ->
    let (Cont g) = f (fun a -> Cont (fun _ -> k a)) in
    g k)

// Trouver le premier élément qui satisfait un prédicat *)
let find_first p lst =
  callcc (fun exit ->
    let* x = lst in
    let* _ = if p x then exit x else return () in
    return None)

callcc capture la continuation comme un "point de retour". Quand on appelle exit x, on saute directement à ce point, peu importe où on est dans le calcul. C'est un break ou un return impératif, mais purement fonctionnel !

7. Les lois des monades

Pour qu'un type avec return et >>= soit vraiment une monade, il doit respecter trois lois. Elles sont simples mais importantes (surtout si vous créez votre propre monade).

Vérifions pour la monade Liste :

(* Identité à gauche : return x >>= f = f x *)
(* return x = [x]; [x] >>= f = flatten (map f [x]) = f x ✓ *)

(* Identité à droite : m >>= return = m *)
(* m >>= return = flatten (map return m) = flatten [[a];[b];...] = m ✓ *)

(* Associativité : (m >>= f) >>= g = m >>= (fun x -> f x >>= g) *)
(* Les deux appliquent f à chaque élément puis g à chaque résultat ✓ *)

Ces lois garantissent que les monades se comportent de façon prévisible. C'est ce qui permet au programmeur de raisonner sur son code et au compilateur de faire des optimisations. Sans ces lois, on ne pourrait pas utiliser le sucre let* en toute sécurité.

8. Conclusion

On a parcouru un sacré bout de chemin !

D'autres monades existent (et vous les rencontrerez sûrement) :

• Writer — accumule un journal (logs) en plus du calcul.
• Either — comme Option mais avec un message d'erreur (Ok 'a | Error 'e).
• IO — la monade des entrées-sorties en Haskell (et en OCaml avec Lwt/Async).
• Parser — la monade des analyseurs syntaxiques… sujet du prochain cours !

En attendant, retenez ceci :

"A monad is just a monoid in the category of endofunctors, what's the problem?"
— Blague de mathématicien·ne·s qui fait pleurer les développeur·se·s

Fait avec ❤️, beaucoup de bind, et un return bien mérité