4. Avancé - Fonctions d'Ordre Supérieur

📚 Introduction

Tu as maintenant maîtrisé la récursion sur les listes. Il est temps de découvrir une abstraction puissante : les fonctions qui prennent d'autres fonctions en paramètres.

1. Les Fonctions sont des Valeurs

En Elm, les fonctions sont comme des nombres

-- Un nombre
x : Int
x = 42

-- Une fonction
double : Int -> Int
double n = n * 2

-- On peut passer une fonction en paramètre !
appliquer : (Int -> Int) -> Int -> Int
appliquer fonction valeur = fonction valeur
--        ↑               ↑       ↑
--        fonction       nombre   appelle la fonction

Exemple d'utilisation :

appliquer double 5
--> 10

appliquer (\x -> x + 1) 5
--> 6

2. Fonctions Anonymes (Lambda)

Syntaxe : `\param -> expression`

Une fonction anonyme (ou lambda) est une fonction sans nom, définie sur place.

-- Fonction normale (avec nom)
double : Int -> Int
double x = x * 2

-- Fonction anonyme (sans nom)
\x -> x * 2

Exemples

-- Lambda simple
\x -> x + 1

-- Lambda avec plusieurs paramètres
\x y -> x + y

-- Lambda avec condition
\x -> if x > 0 then x else 0

-- Lambda avec pattern matching
\lst -> case lst of
    Vide -> 0
    Cons _ q -> 1 + taille q

Pourquoi utiliser des lambdas ?

Cas 1 : Fonction utilisée une seule fois

-- ❌ Définir une fonction nommée pour un usage unique
estPair : Int -> Bool
estPair x = modBy 2 x == 0

resultat = filter estPair maListe

-- ✅ Lambda : plus concis
resultat = filter (\x -> modBy 2 x == 0) maListe

Cas 2 : Fonction trop simple pour mériter un nom

-- Ajouter 10 à chaque élément
ajouterDix = map (\x -> x + 10) maListe

3. Fonctions d'Ordre Supérieur

Définition

Une fonction d'ordre supérieur est une fonction qui :

Prend une ou plusieurs fonctions en paramètres, ET/OU
Retourne une fonction

Exemples que tu connais déjà !

-- take : prend n et une liste
take : Int -> Liste a -> Liste a

-- Mais on peut le voir comme :
-- take prend n et RETOURNE une fonction qui prend une liste
take : Int -> (Liste a -> Liste a)

En Elm, toutes les fonctions à plusieurs paramètres sont en fait des fonctions d'ordre supérieur !

4. La Fonction `foldr` : Le Pattern Ultime

Observation

Regarde ces fonctions que tu as écrites :

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

somme : Liste Int -> Int
somme lst =
    case lst of
        Vide -> 0
        Cons tete queue -> tete + somme queue

concat : Liste a -> Liste a -> Liste a
concat lst1 lst2 =
    case (lst1, lst2) of
        (Vide, _) -> lst2
        (Cons t q, _) -> Cons t (concat q lst2)

Elles suivent TOUTES le même pattern !

Cas de base : Vide -> valeur
Cas récursif : Cons tete queue -> combiner tete (récursion queue)

`foldr` capture ce pattern

foldr : (a -> b -> b) -> b -> Liste a -> b
foldr   combiner         base   liste     = résultat

Lecture :

combiner : fonction qui combine un élément avec le résultat du reste
base : valeur à retourner pour la liste vide
liste : la liste à traiter
résultat : le résultat final

Implémentation de `foldr`

foldr : (a -> b -> b) -> b -> Liste a -> b
foldr combiner base liste =
    case liste of
        Vide -> 
            base
        Cons tete queue -> 
            combiner tete (foldr combiner base queue)
--          ↑        ↑     ↑
--          fonction  élément  résultat du reste

Visualisation

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

-- foldr f base [1, 2, 3]
f    1 (f    2 (f    3 base))

-- On "remplace" Cons par f et Vide par base !

5. Réécrire avec `foldr`

5.1. `taille`

Version manuelle :

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

Identifions le pattern :

Valeur de base : 0
Combinaison : 1 + résultat_du_reste
La tête ne nous intéresse pas : on l'ignore

Avec foldr :

taille : Liste a -> Int
taille lst =
    foldr (\tete acc -> 1 + acc) 0 lst
--        ↑     ↑       ↑         ↑
--        λ  élément  accumulateur base

Encore plus court :

taille : Liste a -> Int
taille = foldr (\_ acc -> 1 + acc) 0

Trace d'exécution :

taille [1, 2, 3]
= foldr (\_ acc -> 1 + acc) 0 [1, 2, 3]
= (\_ acc -> 1 + acc) 1 (foldr (\_ acc -> 1 + acc) 0 [2, 3])
= 1 + ((\_ acc -> 1 + acc) 2 (foldr (\_ acc -> 1 + acc) 0 [3]))
= 1 + (1 + ((\_ acc -> 1 + acc) 3 (foldr (\_ acc -> 1 + acc) 0 [])))
= 1 + (1 + (1 + 0))
= 3

5.2. `somme`

Version manuelle :

somme : Liste Int -> Int
somme lst =
    case lst of
        Vide -> 0
        Cons tete queue -> tete + somme queue

Pattern :

Base : 0
Combinaison : tete + résultat

Avec foldr :

somme : Liste Int -> Int
somme lst =
    foldr (\tete acc -> tete + acc) 0 lst

Version ultra-courte :

somme : Liste Int -> Int
somme = foldr (+) 0
--            ↑
--            L'opérateur + est déjà une fonction (Int -> Int -> Int)

Pourquoi ça marche ?

(+) : Int -> Int -> Int
-- (+) est une fonction qui prend 2 Int et retourne un Int
-- C'est exactement ce que foldr attend !

foldr (+) 0 [1, 2, 3]
= 1 + (2 + (3 + 0))
= 6

5.3. `concat`

Version manuelle :

concat : Liste a -> Liste a -> Liste a
concat lst1 lst2 =
    case lst1 of
        Vide -> lst2
        Cons t q -> Cons t (concat q lst2)

Pattern :

Base : lst2 (pas Vide !)
Combinaison : Cons tete résultat

Avec foldr :

concat : Liste a -> Liste a -> Liste a
concat lst1 lst2 =
    foldr Cons lst2 lst1
--        ↑    ↑    ↑
--        constructeur  base  liste à parcourir

Trace :

concat [1, 2] [3, 4]
= foldr Cons [3, 4] [1, 2]
= Cons 1 (foldr Cons [3, 4] [2])
= Cons 1 (Cons 2 (foldr Cons [3, 4] []))
= Cons 1 (Cons 2 [3, 4])
= [1, 2, 3, 4]

5.4. `tousVrais`

Version manuelle :

tousVrais : Liste Bool -> Bool
tousVrais lst =
    case lst of
        Vide -> True
        Cons tete queue -> tete && tousVrais queue

Avec foldr :

tousVrais : Liste Bool -> Bool
tousVrais = foldr (&&) True
--                ↑    ↑
--                ET   base (promesse non violée)

Trace :

tousVrais [True, True, False]
= foldr (&&) True [True, True, False]
= True && (True && (False && True))
= True && (True && False)
= False

5.5. `auMoinsUnVrai`

Version manuelle :

auMoinsUnVrai : Liste Bool -> Bool
auMoinsUnVrai lst =
    case lst of
        Vide -> False
        Cons tete queue -> tete || auMoinsUnVrai queue

Avec foldr :

auMoinsUnVrai : Liste Bool -> Bool
auMoinsUnVrai = foldr (||) False
--                    ↑    ↑
--                    OU   base (aucun trouvé)

5.6. `ajouterFin`

Version manuelle :

ajouterFin : a -> Liste a -> Liste a
ajouterFin e lst =
    case lst of
        Vide -> Cons e Vide
        Cons tete queue -> Cons tete (ajouterFin e queue)

Avec foldr :

ajouterFin : a -> Liste a -> Liste a
ajouterFin e lst =
    foldr Cons (Cons e Vide) lst
--        ↑    ↑
--        reconstructeur  base = [e]

Trace :

ajouterFin 9 [1, 2, 3]
= foldr Cons [9] [1, 2, 3]
= Cons 1 (Cons 2 (Cons 3 [9]))
= [1, 2, 3, 9]

6. Nouvelles Fonctions avec `foldr`

6.1. `map` : Transformer chaque élément

-- Applique une fonction à chaque élément
map : (a -> b) -> Liste a -> Liste b
map f lst =
    foldr (\tete acc -> Cons (f tete) acc) Vide lst
--         ↑           ↑
--         transforme  ajoute au résultat

Exemple :

map (\x -> x * 2) [1, 2, 3]
--> [2, 4, 6]

map (\x -> x > 5) [3, 7, 2, 9]
--> [False, True, False, True]

Trace :

map (\x -> x * 2) [1, 2, 3]
= foldr (\tete acc -> Cons (tete * 2) acc) Vide [1, 2, 3]
= Cons (1*2) (foldr (...) Vide [2, 3])
= Cons 2 (Cons (2*2) (foldr (...) Vide [3]))
= Cons 2 (Cons 4 (Cons (3*2) (foldr (...) Vide [])))
= Cons 2 (Cons 4 (Cons 6 Vide))
= [2, 4, 6]

6.2. `filter` : Garder certains éléments

-- Garde les éléments qui satisfont un prédicat
filter : (a -> Bool) -> Liste a -> Liste a
filter predicate lst =
    foldr (\tete acc ->
        if predicate tete then
            Cons tete acc
        else
            acc
    ) Vide lst

Exemple :

filter (\x -> x > 5) [3, 7, 2, 9, 1]
--> [7, 9]

filter (\x -> modBy 2 x == 0) [1, 2, 3, 4, 5, 6]
--> [2, 4, 6]

6.3. `compte` avec `foldr`

compte : a -> Liste a -> Int
compte e lst =
    foldr (\tete acc ->
        if tete == e then
            1 + acc
        else
            acc
    ) 0 lst

6.4. `dupliquer` avec `foldr`

dupliquer : Liste a -> Liste a
dupliquer lst =
    foldr (\tete acc -> Cons tete (Cons tete acc)) Vide lst
--         ↑                ↑            ↑
--         élément       1ère fois   2ème fois

Trace :

dupliquer [1, 2]
= foldr (\tete acc -> Cons tete (Cons tete acc)) Vide [1, 2]
= Cons 1 (Cons 1 (foldr (...) Vide [2]))
= Cons 1 (Cons 1 (Cons 2 (Cons 2 (foldr (...) Vide []))))
= Cons 1 (Cons 1 (Cons 2 (Cons 2 Vide)))
= [1, 1, 2, 2]

7. Comprendre les Types de `foldr`

foldr : (a -> b -> b) -> b -> Liste a -> b
--       ↑       ↑      ↑    ↑         ↑
--       |       |      |    |         résultat final
--       |       |      |    liste d'éléments de type a
--       |       |      valeur de départ (type b)
--       |       accumulateur (résultat partiel)
--       élément de la liste

Exemples de types concrets :

-- taille
foldr : (a -> Int -> Int) -> Int -> Liste a -> Int
--       ↑    ↑     ↑        ↑      ↑          ↑
--       elem  acc   acc     base   liste    résultat

-- somme
foldr : (Int -> Int -> Int) -> Int -> Liste Int -> Int

-- concat
foldr : (a -> Liste a -> Liste a) -> Liste a -> Liste a -> Liste a

-- map
foldr : (a -> Liste b -> Liste b) -> Liste b -> Liste a -> Liste b
--       ↑          ↑                    ↑         ↑          ↑
--       elem    résultat partiel     []      liste    nouvelle liste

8. Composition de Fonctions

L'opérateur `>>`

(>>) : (a -> b) -> (b -> c) -> (a -> c)
--     fonction1   fonction2   fonction composée

Exemple :

-- Au lieu de
resultat = somme (map (\x -> x * 2) maListe)

-- On peut écrire
doubleEtSomme = (map (\x -> x * 2)) >> somme
resultat = doubleEtSomme maListe

Chaîner des transformations

-- Calculer la somme des carrés des nombres pairs
sommeCarresPairs : Liste Int -> Int
sommeCarresPairs =
    filter (\x -> modBy 2 x == 0)  -- Garde les pairs
    >> map (\x -> x * x)           -- Met au carré
    >> somme                       -- Additionne

-- Utilisation
sommeCarresPairs [1, 2, 3, 4, 5]
--> 2² + 4² = 4 + 16 = 20

9. Quand Utiliser `foldr` ?

✅ Utilise `foldr` quand :

Tu parcours toute la liste
```
taille, somme, concat, tousVrais
```
Tu construis une nouvelle structure
```
map, filter, dupliquer
```
Tu accumules un résultat
```
somme, compte
```
Le pattern récursif est clair
Cas de base évident
Combinaison simple

❌ N'utilise PAS `foldr` quand :

Tu veux arrêter tôt

-- contient : doit s'arrêter dès qu'on trouve
contient e lst =
    case lst of
        Vide -> False
        Cons tete queue ->
            if tete == e then
                True  -- ✅ S'arrête ici
            else
                contient e queue

-- foldr parcourt TOUTE la liste, même après avoir trouvé

La récursion est complexe

-- fusion de deux listes : besoin de déconstruire les 2
-- triFusion : récursion sur 2 moitiés

Tu as besoin de l'index

-- take, drop : nécessitent un compteur

10. `foldl` : Variante de Gauche à Droite

foldl : (a -> b -> b) -> b -> Liste a -> b
foldl f acc lst =
    case lst of
        Vide -> acc
        Cons tete queue -> 
            foldl f (f tete acc) queue
--          ↑       ↑
--          applique d'abord, puis continue

Différence avec `foldr`

-- foldr : associe à DROITE
foldr (+) 0 [1, 2, 3]
= 1 + (2 + (3 + 0))

-- foldl : associe à GAUCHE
foldl (+) 0 [1, 2, 3]
= ((0 + 1) + 2) + 3

Quand utiliser `foldl` ?

Pour renverse : foldl est plus efficace

renverse : Liste a -> Liste a
renverse = foldl (\tete acc -> Cons tete acc) Vide

-- Trace:
-- renverse [1, 2, 3]
-- = foldl Cons Vide [1, 2, 3]
-- = foldl Cons (Cons 1 Vide) [2, 3]
-- = foldl Cons (Cons 2 (Cons 1 Vide)) [3]
-- = foldl Cons (Cons 3 (Cons 2 (Cons 1 Vide))) []
-- = [3, 2, 1]

11. Exercices pour Réfléchir

Ne code pas ces exercices, juste réfléchis à comment tu les ferais :

Avec foldr, comment écrirais-tu removeAllElt ?
Quelle est la base ?
Comment combiner un élément avec le résultat ?
Peut-on écrire take avec foldr ?
Problème : take a besoin d'un compteur
Solution : utiliser une fonction auxiliaire avec un compteur
Comment écrire renverse avec foldr ?
Base : Vide
Combinaison : ajouterFin tete acc
Mais attention : O(n²) !

🎯 Résumé

Concepts Clés

Fonctions anonymes : \param -> expression
Fonctions d'ordre supérieur : prennent des fonctions en paramètres
foldr : capture le pattern récursif sur les listes

Le Pattern `foldr`

-- Pattern manuel
maFonction lst =
    case lst of
        Vide -> base
        Cons tete queue -> combiner tete (maFonction queue)

-- Avec foldr
maFonction = foldr combiner base

Quand Utiliser

Situation	Outil
Récursion simple sur 1 liste	`foldr`
Besoin d'arrêter tôt	Récursion manuelle
Récursion complexe	Récursion manuelle
Transformer/filtrer	`map`/`filter` (basés sur `foldr`)

💡 Citation

"Don't repeat yourself. If you see a pattern, abstract it."

— Principe de programmation fonctionnelle

foldr est l'abstraction du pattern de récursion sur les listes. Au lieu d'écrire 100 fois le même case lst of..., tu l'écris une fois et tu le réutilises ! 🚀

4. Avancé - Fonctions d'Ordre Supérieur

📚 Introduction

1. Les Fonctions sont des Valeurs

En Elm, les fonctions sont comme des nombres

2. Fonctions Anonymes (Lambda)

Syntaxe : \param -> expression

Exemples

Pourquoi utiliser des lambdas ?

3. Fonctions d'Ordre Supérieur

Définition

Exemples que tu connais déjà !

4. La Fonction foldr : Le Pattern Ultime

Observation

foldr capture ce pattern

Implémentation de foldr

Visualisation

5. Réécrire avec foldr

5.1. taille

5.2. somme

5.3. concat

5.4. tousVrais

5.5. auMoinsUnVrai

5.6. ajouterFin

6. Nouvelles Fonctions avec foldr

6.1. map : Transformer chaque élément

6.2. filter : Garder certains éléments

6.3. compte avec foldr

6.4. dupliquer avec foldr

7. Comprendre les Types de foldr

8. Composition de Fonctions

L'opérateur >>

Chaîner des transformations

9. Quand Utiliser foldr ?

✅ Utilise foldr quand :

❌ N'utilise PAS foldr quand :

10. foldl : Variante de Gauche à Droite

Différence avec foldr

Quand utiliser foldl ?

11. Exercices pour Réfléchir

🎯 Résumé

Concepts Clés

Le Pattern foldr

Quand Utiliser

💡 Citation

Syntaxe : `\param -> expression`

4. La Fonction `foldr` : Le Pattern Ultime

`foldr` capture ce pattern

Implémentation de `foldr`

5. Réécrire avec `foldr`

5.1. `taille`

5.2. `somme`

5.3. `concat`

5.4. `tousVrais`

5.5. `auMoinsUnVrai`

5.6. `ajouterFin`

6. Nouvelles Fonctions avec `foldr`

6.1. `map` : Transformer chaque élément

6.2. `filter` : Garder certains éléments

6.3. `compte` avec `foldr`

6.4. `dupliquer` avec `foldr`

7. Comprendre les Types de `foldr`

L'opérateur `>>`

9. Quand Utiliser `foldr` ?

✅ Utilise `foldr` quand :

❌ N'utilise PAS `foldr` quand :

10. `foldl` : Variante de Gauche à Droite

Différence avec `foldr`

Quand utiliser `foldl` ?

Le Pattern `foldr`