Fold et Reduce : guide pratique

Sommaire

Voir aussi : FUNCTIONS pour la référence des signatures, BROADCAST_GUIDE pour les patterns de transformation.

Le principe

Broadcast distribue une opération sur une structure et en préserve la forme. Fold agrège une structure en une seule valeur.

broadcast : [a, b, c] → [f(a), f(b), f(c)]     # forme conservée
fold      : [a, b, c] → résultat               # forme réduite

Les deux opèrent sur des collections, mais dans des directions opposées :

  • broadcast descend dans les structures (jusqu'aux feuilles)
  • fold consomme un niveau de structure (une seule profondeur)

Signatures

fold(iterable, init, f)
# f(acc, x) -> new_acc
# Retourne init si la collection est vide

reduce(iterable, f)
# f(acc, x) -> new_acc
# Le premier élément sert d'accumulateur
# Erreur si la collection est vide

fold est la primitive (totale). reduce est le raccourci (partiel), et il accepte aussi des monoïdes nommés à la place du callback (section suivante).

Réduire par monoïde nommé

Un monoïde, c'est un élément neutre plus une opération associative. reduce en connaît sept et sait donc agréger sans qu'on écrive la boucle.

reduce(iterable, m1, m2, ..., mk)
# mi parmi : sum, len, max, min, any, all, concat
# un seul monoïde -> la valeur ; plusieurs -> un tuple, dans l'ordre donné

data = list(3, -1, 4, -1, 5, 9, -2, 6)

reduce(data, sum)              # → 23
reduce(data, len)              # → 8
reduce(data, sum, len, max)    # → (23, 8, 9)

La forme variadique est ce qui distingue cette écriture d'un simple sum(data) : elle agrège plusieurs accumulateurs en une passe, là où le fold équivalent demande de faire circuler un tuple à la main et d'indexer ses positions.

monoïde agrège sur collection vide
sum la somme 0 (son élément neutre)
len le nombre d'éléments 0
any au moins un vrai False
all tous vrais True
max le maximum erreur (pas de neutre)
min le minimum erreur
concat la concaténation erreur

Un monoïde qui a un élément neutre le rend sur une collection vide ; les autres lèvent, comme reduce avec un callback. len et concat s'appellent aussi seuls : len(xs), concat(xs).

Le comptage passe par len et non par un nom count dédié : ce dernier serait un doublon exact de len, et il occuperait un nom de variable très courant — le masquer dans une fonction déclencherait W204 pour une simple écriture d'agrégat.

Un callback lambda reste sur le reduce classique. La distinction se fait sur l'identité de la fonction passée, pas sur son == : un objet dont la comparaison lève n'est donc jamais comparé.

Un monoïde ne demande que deux choses : un élément qui ne fait rien, et une opération qui ne se soucie pas des parenthèses.

Exemples de base

Accumuler des valeurs

# Somme
fold(list(1, 2, 3, 4), 0, (acc, x) => { acc + x })  # → 10

# Produit
fold(list(1, 2, 3, 4), 1, (acc, x) => { acc * x })  # → 24

# Concaténation
fold(list("a", "b", "c"), "", (acc, x) => { acc + x })  # → 'abc'

Le choix de init est crucial : c'est l'élément neutre de l'opération.

  • Somme : 0 (car 0 + x = x)
  • Produit : 1 (car 1 * x = x)
  • Concaténation : "" (car "" + s = s)
  • Intersection logique : True (car True and x = x)

Cas vide

fold(list(), 0, (acc, x) => { acc + x })     # → 0
fold(list(), 1, (acc, x) => { acc * x })     # → 1
fold(list(), "", (acc, x) => { acc + x })    # → ''

Quand la collection est vide, fold retourne init. C'est ce qui rend l'opération totale : pas de cas d'erreur.

reduce : quand init est inutile

reduce(list(3, 1, 4, 1, 5), (a, b) => { if a > b { a } else { b } })  # → 5
reduce(list(10, 20, 30), (acc, x) => { acc + x })                     # → 60

reduce prend le premier élément comme accumulateur initial. Utile quand l'élément neutre est évident ou quand il n'existe pas (ex: max, min).

Patterns courants

Compter des éléments

# Compter les éléments positifs
positifs = fold(list(3, -1, 4, -1, 5), 0, (acc, x) => {
    if x > 0 { acc + 1 } else { acc }
})
print(positifs)  # → 3

Filtrer d'abord puis compter est plus court, et dit la même chose :

positifs = reduce(list(3, -1, 4, -1, 5).[if > 0], len)
print(positifs)  # → 3

Construire une structure

# Inverser une liste (fold construit une nouvelle structure)
inversee = fold(list(1, 2, 3, 4), list(), (acc, x) => {
    list(x) + acc
})
print(inversee)  # → [4, 3, 2, 1]

Aplatir un niveau

# Aplatir une liste de listes (un seul niveau)
plat = fold(list(list(1, 2), list(3, 4), list(5)), list(), (acc, row) => {
    acc + row
})
print(plat)  # → [1, 2, 3, 4, 5]

# Le monoïde `concat` fait exactement ce fold
plat = reduce(list(list(1, 2), list(3, 4), list(5)), concat)
print(plat)  # → [1, 2, 3, 4, 5]

fold ne descend qu'un niveau. C'est une propriété, pas une limitation : chaque appel de fold consomme exactement un niveau de structure. Pour deux niveaux, deux folds.

Réduire avec logique

# Tous vrais ?
tous = fold(list(True, True, False), True, (acc, x) => { acc and x })
print(tous)  # → False

# Au moins un vrai ?
un = fold(list(False, False, True), False, (acc, x) => { acc or x })
print(un)  # → True

Les monoïdes all et any couvrent ces deux cas directement :

print(reduce(list(True, True, False), all))   # → False
print(reduce(list(False, False, True), any))  # → True

Composition broadcast + fold

C'est le pattern central : broadcast transforme, fold agrège. Ensemble, ils forment un pipeline complet.

Transformer puis agréger

# Carrés puis somme
data = list(1, 2, 3, 4)
somme_carres = fold(data.[** 2], 0, (acc, x) => { acc + x })
print(somme_carres)  # → 30

# Doubler puis produit
produit_doubles = fold(data.[* 2], 1, (acc, x) => { acc * x })
print(produit_doubles)  # → 384

Filtrer puis agréger

# Somme des éléments > 3
data = list(1, 5, 2, 8, 3, 7)
somme_grands = fold(data.[if > 3], 0, (acc, x) => { acc + x })
print(somme_grands)  # → 20

Pipeline complet : filter -> map -> fold

# Prendre les positifs, les doubler, les sommer
data = list(-3, 1, -1, 4, -2, 5)
resultat = fold(data.[if > 0].[* 2], 0, (acc, x) => { acc + x })
print(resultat)  # → 20

Lecture : prendre data, garder les positifs ([if > 0]), doubler ([* 2]), puis fold-sommer.

Le pipeline broadcast -> fold est l'aller-retour complet d'une donnée à travers une structure : broadcast l'ouvre, fold la referme.

Comparaison avec l'approche impérative

Le pipeline broadcast + fold remplace des boucles explicites :

# Impératif
data = list(1, 2, 3, 4, 5)
total = 0
for x in data {
    if x > 2 {
        total = total + (x * 10)
    }
}
print(total)  # → 120

# Déclaratif (broadcast + fold)
resultat = fold(data.[if > 2].[* 10], 0, (acc, x) => { acc + x })
print(resultat)  # → 120

Les deux produisent le même résultat. La version déclarative sépare les trois opérations (filtrer, transformer, agréger) au lieu de les entremêler dans une boucle.

Fold sur structures imbriquées

fold opère sur un seul niveau. Pour des structures imbriquées, on compose les niveaux explicitement.

Un niveau : agréger les sous-structures

# Longueur totale de sous-listes
matrice = list(list(1, 2), list(3, 4, 5), list(6))
total_elements = fold(matrice, 0, (acc, row) => { acc + len(row) })
print(total_elements)  # → 6

Deux niveaux : fold imbriqué

# Somme de tous les éléments d'une matrice
matrice = list(list(1, 2, 3), list(4, 5, 6), list(7, 8, 9))
somme_totale = fold(matrice, 0, (acc, row) => {
    acc + fold(row, 0, (a, x) => { a + x })
})
print(somme_totale)  # → 45

Fold pour mapper sur les lignes

# Somme des carrés de chaque ligne
matrice = list(list(1, 2, 3), list(4, 5, 6))
sommes = fold(matrice, list(), (acc, row) => {
    acc + list(fold(row.[** 2], 0, (a, x) => { a + x }))
})
print(sommes)  # → [14, 77]

Lecture : pour chaque ligne, broadcast [** 2] élève au carré, puis un fold interne somme. Le fold externe accumule les résultats dans une liste.

fold vs builtins spécialisés

Les builtins sum, min, max sont des spécialisations de fold :

# Équivalences conceptuelles
data = list(1, 2, 3, 4, 5)

# sum(data)  ≡  fold(data, 0, (acc, x) => { acc + x })
print(sum(data))                                          # → 15
print(fold(data, 0, (acc, x) => { acc + x }))             # → 15

# min(data)  ≡  reduce(data, (a, b) => { if a < b { a } else { b } })
print(min(data))                                              # → 1
print(reduce(data, (a, b) => { if a < b { a } else { b } }))  # → 1

Les builtins sont plus concis pour les cas standards. fold prend le relais quand la logique d'agrégation est custom.

Quand utiliser quoi

Besoin Outil
Transformer chaque élément data.[op] (broadcast)
Filtrer des éléments data.[if cond] (broadcast filter)
Agréger en une valeur (somme, produit, concat) fold(data, init, f)
Agréger sans valeur initiale reduce(data, f)
Somme / min / max simples sum(data), min(data), max(data)
Transformer puis agréger fold(data.[op], init, f)
Filtrer, transformer, agréger fold(data.[if cond].[op], init, f)
Agréger des structures imbriquées fold dans fold

Le choix entre fold et un builtin spécialisé est un choix de lisibilité, pas de sémantique. Les deux font la même chose. fold le fait en montrant le mécanisme.