Xalg / Fix / L'agrégation : replier des valeurs sans casser le point fixe
Navigation
Apprendre
Recettes
Référence
Comprendre
Bonnes pratiques
En pratique
Explications

L'agrégation : replier des valeurs sans casser le point fixe

Déduire des faits, c'est le métier de base de Fix. Mais parfois tu ne veux pas tous les faits — tu veux les résumer : un total, un maximum, un compte. C'est l'agrégation.

Un but de corps, pas une commande à part

L'agrégation s'écrit comme un littéral dans le corps d'une règle :

best_score(P, B) :- agg(B, max, S, score(P, S)).

« Le meilleur score de P, c'est le max des S tels que score(P, S). » Fix groupe par les variables de la tête (P), replie S avec l'opérateur, et lie le résultat (B).

Six opérateurs : min, max, sum, count, product, avg.

prix(o1, 100).  prix(o1, 200).  prix(o2, 50).
total(O, T) :- agg(T, sum, P, prix(O, P)).
?- total(O, T).
O = o1, T = 300
O = o2, T = 50

Typer un prédicat d'accumulation

La tête d'une règle d'agrégation se signe comme n'importe quel prédicat — un sig ordinaire, où la position qui reçoit le résultat porte un type numérique :

sig(prix,  [commande, montant]).
sig(total, [commande, montant]).     % la position de T : un type numérique

total(O, T) :- agg(T, sum, P, prix(O, P)).
?- total(O, T).
O = o1, T = 300

Pour sum, min, max, product, le résultat vit naturellement dans le même type que la valeur repliée (montant → montant). Deux cas particuliers : count produit un nombre quel que soit le type de la source — donne-lui son propre type (quantite) ; et avg produit un flottant même sur des entiers (avg de 100 et 201 → 150.5). Rien d'autre à savoir : les variables de tête restantes (les clés de groupage) se signent comme d'habitude.

Et si tu déclares la position résultat d'un type fermé non numérique (un enum), le mismatch est refusé à la compilation :

fix: agrégat total : mode sum incompatible (requiert numérique (⁺) en position résultat)
    → :help aggregation

Pourquoi un monoïde

Replier, c'est combiner deux à deux avec une opération associative et commutative — un monoïde. Et c'est exactement ce qu'il faut : comme l'ordre des règles n'a aucune importance en Fix, l'ordre dans lequel on replie ne doit pas en avoir non plus. Le max de {a, b, c} est le même quel que soit le chemin.

L'agrégation n'est donc pas un greffon : c'est l'opération du treillis, appliquée sur le même point fixe que le reste.

Récursion : idempotents seulement

Tu peux agréger récursivement — c'est ainsi qu'on calcule un plus court chemin (le min des chemins, qui dépendent eux-mêmes de min). Mais uniquement avec un opérateur idempotent (min, max : reprendre le résultat ne le change pas).

Un sum ou un count en récursion n'aurait pas de point fixe stable (il grossirait sans fin). Fix le détecte et le refuse à la compilation — pas de résultat faux, un message.

Pour le plus court chemin, écris la relaxation (l'agrégat borne la récursion à chaque pas) plutôt que l'« accumulation d'abord » (cout(X, Z, C) :- cout(X, Y, C1), arc(Y, Z, C2), add(C1, C2, C). puis min à la fin) : la relaxation termine même sur graphe cyclique (poids ≥ 0), l'accumulation énumère TOUS les chemins et, sur un cycle, s'arrête sur une erreur explicite (« évaluation incomplète ») en temps borné — jamais un calcul sans fin, jamais un résultat faux muet. Un cycle de poids négatif sous min récursif est lui aussi détecté et signalé (certificat Bellman-Ford). La recette complète est dans Recettes.

Chaînage

Chaque agrégat lit sa source à sa clôture complète (une strate). Tu peux donc empiler : un second agrégat lit le premier, une strate plus haut — un roll-up.

ventes(nord, widget, 10).  ventes(nord, gadget, 5).  ventes(sud, widget, 7).
total_region(R, T) :- agg(T, sum, V, ventes(R, _P, V)).

Les bords honnêtes

À côté