5. Bien avancé - Catamorphismes

🎯 Introduction

C'est un bien gros mot pour décrire formellement ce que tu as déjà appris à faire.

Tu as appris foldr. Maintenant, découvrons le vrai nom de ce que tu fais depuis le début : les catamorphismes.

Spoiler : foldr est un catamorphisme !

1. Le Mot Qui Fait Peur

Catamorphisme (du grec κατά "vers le bas" + μορφή "forme")

Traduction simple : "Déconstruire une structure en descendant vers quelque chose de plus simple"

En encore plus simple : "Transformer une structure récursive en une valeur"

2. Rappel : Ta Liste est une Structure Récursive

type Liste a
    = Vide
    | Cons a (Liste a)

Une liste, c'est :

SOIT Vide
SOIT construite avec Cons + un élément + une autre liste

C'est récursif : une liste contient une liste !

Cons 1 (Cons 2 (Cons 3 Vide))
  ↑       ↑       ↑      ↑
  Cons    Cons    Cons   Vide

3. Le Catamorphisme = "Dé-construire"

Construction vs Déconstruction

Construction (créer une liste) :

-- Je CONSTRUIS avec Cons et Vide
maListe = Cons 1 (Cons 2 (Cons 3 Vide))

Déconstruction (détruire une liste pour en extraire une valeur) :

-- Je DÉCONSTRUIS avec foldr
taille maListe = foldr (\_ acc -> 1 + acc) 0 maListe
--> 3

Le catamorphisme, c'est la déconstruction systématique !

4. L'Intuition Visuelle

Construction d'une liste

Catamorphisme (foldr)

On remplace :

Chaque Cons par notre fonction f
Vide par notre accumulator acc

5. Le Pattern Universel

Toute structure récursive a son catamorphisme

Pour les listes :

type Liste a = Vide | Cons a (Liste a)

-- Son catamorphisme :
foldr : (a -> b -> b) -> b -> Liste a -> b
--       ↑ pour Cons    ↑ pour Vide

Pour les arbres binaires :

type Arbre a = Feuille | Noeud a (Arbre a) (Arbre a)

-- Son catamorphisme :
foldArbre : b -> (a -> b -> b -> b) -> Arbre a -> b
--          ↑     ↑ pour Noeud          ↑
--      pour Feuille              structure à déconstruire

Pour les Maybe :

type Maybe a = Nothing | Just a

-- Son catamorphisme :
foldMaybe : b -> (a -> b) -> Maybe a -> b
--          ↑     ↑ pour Just
--      pour Nothing

6. La Formule Magique d'un Catamorphisme

Étape 1 : Regarde ton type

type Liste a
    = Vide              -- Constructeur 1 (0 argument récursif)
    | Cons a (Liste a)  -- Constructeur 2 (1 argument + 1 récursif)

Étape 2 : Crée le catamorphisme

Pour chaque constructeur, fournis un "remplaçant" :

foldr : (a -> b -> b) -> b -> Liste a -> b
        ↑              ↑
        remplace Cons  remplace Vide

Détail :

Vide → b (juste une valeur)
Cons a (Liste a) → (a -> b -> b) (fonction qui prend l'élément et le résultat récursif)

Étape 3 : Implémente

foldr : (a -> b -> b) -> b -> Liste a -> b
foldr fCons fVide lst =
    case lst of
        Vide -> fVide                           -- Applique fVide
        Cons tete queue -> fCons tete (foldr fCons fVide queue)
        --                 ↑     ↑      ↑
        --                 fonction  élément  résultat récursif

7. Exemples Concrets

Exemple 1 : Taille

Question : Comment remplacer les constructeurs ?

-- Liste originale
Cons 1 (Cons 2 (Cons 3 Vide))

-- Pour calculer la taille :
-- - Remplace chaque Cons par "1 +"
-- - Remplace Vide par 0

(1 +) ((1 +) ((1 +) 0))
= 3

En code :

taille = foldr (\_ acc -> 1 + acc) 0
--             ↑                   ↑
--             remplace Cons       remplace Vide

Exemple 2 : Somme

-- Liste originale
Cons 5 (Cons 3 (Cons 2 Vide))

-- Pour calculer la somme :
-- - Remplace chaque Cons par +
-- - Remplace Vide par 0

5 + (3 + (2 + 0))
= 10

En code :

somme = foldr (+) 0
--            ↑   ↑
--            remplace Cons  remplace Vide

Exemple 3 : Identité (ne rien changer)

-- Que se passe-t-il si je remplace Cons par Cons et Vide par Vide ?

identite = foldr Cons Vide

-- Trace
identite (Cons 1 (Cons 2 Vide))
= Cons 1 (identite (Cons 2 Vide))
= Cons 1 (Cons 2 (identite Vide))
= Cons 1 (Cons 2 Vide)

-- Je recrée la même liste !

8. Catamorphisme vs Récursion Manuelle

Récursion manuelle

taille : Liste a -> Int
taille lst =
    case lst of
        Vide -> 0
        Cons _ queue -> 1 + taille queue

Ce que tu fais :

Pattern matching sur les constructeurs
Pour chaque constructeur, dis quoi faire
Rappelle récursivement la fonction

Catamorphisme

taille = foldr (\_ acc -> 1 + acc) 0

Ce que tu fais :

Fournis un "remplaçant" pour chaque constructeur
Le catamorphisme fait la récursion pour toi

Avantage : Tu n'écris plus le pattern matching, c'est fait une fois pour toutes !

9. Pourquoi C'est Important ?

1. Abstraction

Au lieu de réécrire 100 fois :

case lst of
    Vide -> ...
    Cons tete queue -> ... (récursion queue) ...

Tu écris une fois foldr et tu le réutilises !

2. Garanti Sans Bug

-- ❌ Risque d'oublier un cas
maFonction lst =
    case lst of
        Cons tete queue -> ...
        -- Oups, j'ai oublié Vide !

-- ✅ foldr force à donner les 2 cas
maFonction = foldr fCons fVide
--                 ↑     ↑
--                 obligatoires

3. Raisonnement Mathématique

Les catamorphismes ont des propriétés prouvables :

-- Fusion law
foldr f acc (foldr g base lst) = foldr h acc lst
-- (sous certaines conditions)

-- Universal property
h = foldr f acc  SI ET SEULEMENT SI
    h Vide = acc
    h (Cons x xs) = f x (h xs)

Ces propriétés permettent d'optimiser automatiquement ton code !

10. Le Vocabulaire

Catamorphisme

Cata = vers le bas
Morphisme = transformation de structure
Catamorphisme = transformer en descendant (déconstruire)

Autres morphismes

Anamorphisme (le contraire) :

Ana = vers le haut
Construit une structure à partir d'une graine
Exemple : unfold

-- Générer [1, 2, 3, ..., n]
range : Int -> Liste Int
range n =
    if n <= 0 then
        Vide
    else
        Cons n (range (n - 1))
-- C'est un anamorphisme !

Hylomorphisme (les deux) :

Hylo = tout ensemble
Anamorphisme puis catamorphisme
Exemple : triFusion

triFusion : Liste comparable -> Liste comparable
triFusion lst =
    -- 1. Déconstruire en sous-listes (ana)
    -- 2. Reconstruire en fusionnant (cata)

11. Le Lien avec les Mathématiques

En théorie des catégories

Un catamorphisme est un morphisme initial de l'algèbre F-initiale.

Traduction : - Ta liste est une algèbre (structure avec opérations) - Vide et Cons sont tes opérations - foldr est le morphisme qui transforme cette algèbre en n'importe quelle autre

Propriété universelle :

Pour toute fonction h : Liste a -> b satisfaisant
    h Vide = base
    h (Cons x xs) = f x (h xs)

Il existe un UNIQUE foldr tel que h = foldr f base

Conséquence : foldr est LA manière canonique de définir des fonctions sur les listes !

12. Application : Écrire Ton Propre Catamorphisme

Pour un type custom

-- Type pour les nombres naturels
type Nat = Zero | Succ Nat

-- 0, 1, 2, 3 s'écrit :
-- Zero, Succ Zero, Succ (Succ Zero), Succ (Succ (Succ Zero))

-- Son catamorphisme
foldNat : b -> (b -> b) -> Nat -> b
foldNat zero succ n =
    case n of
        Zero -> zero
        Succ pred -> succ (foldNat zero succ pred)

-- Exemples
toInt : Nat -> Int
toInt = foldNat 0 (\acc -> acc + 1)

double : Nat -> Nat
double = foldNat Zero (\acc -> Succ (Succ acc))

Pour un arbre binaire

type Arbre a
    = Feuille
    | Noeud a (Arbre a) (Arbre a)

-- Son catamorphisme
foldArbre : b -> (a -> b -> b -> b) -> Arbre a -> b
foldArbre feuille noeud arbre =
    case arbre of
        Feuille -> feuille
        Noeud valeur gauche droite ->
            noeud valeur
                (foldArbre feuille noeud gauche)
                (foldArbre feuille noeud droite)

-- Exemples
tailleArbre : Arbre a -> Int
tailleArbre = foldArbre 0 (\_ g d -> 1 + g + d)

sommeArbre : Arbre Int -> Int
sommeArbre = foldArbre 0 (\val g d -> val + g + d)

13. La Recette pour Créer un Catamorphisme

Étapes

Identifie les constructeurs de ton type

type MonType a = Constructeur1 ... | Constructeur2 ...

Pour chaque constructeur, crée un paramètre de fonction
Constructeur sans récursion → valeur simple
Constructeur avec récursion → fonction
Implémente avec pattern matching
Applique le paramètre correspondant
Pour les parties récursives, appelle récursivement le catamorphisme
Utilise-le !

Exemple : Maybe

-- 1. Type
type Maybe a = Nothing | Just a

-- 2. Paramètres
-- Nothing → b (valeur)
-- Just a → (a -> b) (fonction)

-- 3. Implémentation
foldMaybe : b -> (a -> b) -> Maybe a -> b
foldMaybe nothing just m =
    case m of
        Nothing -> nothing
        Just x -> just x

-- 4. Utilisation
getOr : a -> Maybe a -> a
getOr default = foldMaybe default (\x -> x)

isJust : Maybe a -> Bool
isJust = foldMaybe False (\_ -> True)

14. Pourquoi "Catamorphisme" et pas "Fold" ?

Histoire

1960s-70s : Concept découvert en théorie des catégories
1980s : Appliqué en programmation fonctionnelle (ML, Miranda)
1990s : Bananas paper (Erik Meijer) popularise le terme
Aujourd'hui : fold en pratique, catamorphisme en théorie

Noms équivalents

Terme	Langage/Contexte
`foldr`	Haskell, Elm
`reduce`	JavaScript, Python
`inject`	Ruby
`aggregate`	LINQ (C#)
catamorphisme	Théorie des catégories

Tous décrivent la même chose !

15. Le Schéma de Récursion Universel

Tout est un catamorphisme !

-- Addition
add : Nat -> Nat -> Nat
add n m = foldNat m Succ n

-- Multiplication
mult : Nat -> Nat -> Nat
mult n m = foldNat Zero (\acc -> add m acc) n

-- Concaténation
concat : Liste a -> Liste a -> Liste a
concat xs ys = foldr Cons ys xs

-- Map
map : (a -> b) -> Liste a -> Liste b
map f = foldr (\x acc -> Cons (f x) acc) Vide

-- Filter
filter : (a -> Bool) -> Liste a -> Liste a
filter p = foldr (\x acc -> if p x then Cons x acc else acc) Vide

Presque toutes les fonctions sur des structures récursives peuvent s'écrire comme catamorphismes !

16. En Résumé

Ce qu'est un catamorphisme

Une déconstruction systématique d'une structure récursive
Un remplacement de chaque constructeur par une opération
Une abstraction du pattern récursif

Pourquoi c'est utile

✅ Moins de code répétitif
✅ Moins d'erreurs
✅ Raisonnement mathématique possible
✅ Optimisations automatiques
✅ Base de la programmation générique

La formule magique

Structure récursive
    ↓
Catamorphisme (remplace les constructeurs)
    ↓
Valeur

17. Exercice Mental

Sans coder, réfléchis :

contient peut-il s'écrire avec foldr ?
Problème : il faudrait arrêter tôt, mais foldr parcourt tout
Solution partielle possible avec || mais inefficace
removeAllElt avec foldr ?
Base : Vide
Combinaison : si tete == e alors skip, sinon Cons tete acc
Oui, c'est possible !
triFusion avec foldr ?
Non direct, c'est un hylomorphisme (déconstruit puis reconstruit)
Mais fusion peut s'écrire avec foldr !

🎯 Conclusion

Tu faisais des catamorphismes depuis le début sans le savoir !

foldr n'est pas juste une fonction utile, c'est LE pattern fondamental pour travailler avec des structures récursives.

Citation finale :

"Un catamorphisme, c'est comme une recette de cuisine :
Tu prends ta structure, tu remplaces chaque ingrédient (constructeur)
par une opération, et tu obtiens ton plat (résultat)."

Maintenant quand quelqu'un te demande "C'est quoi foldr ?", tu peux répondre :

"C'est le catamorphisme des listes !" 🎓

Et si ils demandent "C'est quoi un catamorphisme ?", réponds :

"C'est la manière canonique de déconstruire une structure récursive en remplaçant ses constructeurs par des opérations."

Tu es maintenant initié à la théorie des catégories ! 🚀