Il arrive qu'on veuille combiner une séquence en une seule valeur ; il arrive aussi qu'on veuille voir chaque valeur intermédiaire produite par la combinaison en cours de route. Factor répartit cela en deux outils : reduce (dans sequences) pour le fold à valeur unique, et la famille cumulative de math.statistics pour la variante progressive.
reduce : le fold général
reduce ( seq init quot: ( prev elt -- next ) -- result )
reduce parcourt une séquence élément par élément, en transportant un résultat courant (l'accumulateur) qu'il fournit à une quotation à deux arguments. La quotation reçoit l'accumulateur courant et l'élément suivant ; ce qu'elle laisse sur la pile devient le nouvel accumulateur.
USING: math sequences ;
{ 1 2 3 4 } 0 [ + ] reduce . ! => 10
{ 1 2 3 4 } 1 [ * ] reduce . ! => 24
Une valeur initiale non nulle et un combinateur personnalisé sont ce que sum et product ne peuvent pas atteindre. Par exemple, la plus grande valeur d'une séquence, avec une valeur par défaut si aucune valeur ne la dépasse :
USING: math.order ;
{ 3 1 -4 5 -2 } 0 [ max ] reduce . ! => 5
{ -3 -1 -4 } 0 [ max ] reduce . ! => 0
La valeur initiale 0 participe à la comparaison : elle sert de résultat lorsque tous les éléments perdent, si bien qu'une séquence de valeurs toutes négatives produit quand même 0 au lieu d'une plus petite valeur arbitraire.
Les réductions cumulatives
Parfois, on veut chaque résultat intermédiaire, pas seulement le dernier. La famille cumulative de math.statistics renvoie une séquence de même longueur que l'entrée, où chaque position correspond à la réduction du préfixe qui se termine à cette position :
cum-sum ( seq -- newseq ) ! running total
cum-product ( seq -- newseq ) ! running product
cum-min ( seq -- newseq ) ! running minimum
cum-max ( seq -- newseq ) ! running maximum
USING: math.statistics ;
{ 3 1 4 1 5 9 2 6 } cum-sum . ! => { 3 4 8 9 14 23 25 31 }
{ 1 2 3 4 } cum-product . ! => { 1 2 6 24 }
{ 3 1 4 1 5 9 2 6 } cum-min . ! => { 3 1 1 1 1 1 1 1 }
{ 3 1 4 1 5 9 2 6 } cum-max . ! => { 3 3 4 4 5 9 9 9 }
Un schéma utile consiste en des réductions cumulatives enchaînées : la sortie de l'une est elle-même une séquence, prête à alimenter la suivante. On peut ainsi exprimer « le résumé courant d'un résumé courant » en deux mots. Les combinaisons sont souples : associe-les selon ce que chaque étape résume.
produce : le unfold
reduce consomme une séquence pour produire une valeur. produce (dans sequences) va dans l'autre sens : il génère une séquence à partir d'une valeur initiale en testant et en avançant de façon répétée :
produce ( pred quot -- seq )
À chaque itération, pred est d'abord exécuté sur l'état courant ; s'il renvoie une valeur vraie, quot est appelé pour produire l'élément suivant et mettre à jour l'état. Quand pred renvoie f, l'itération s'arrête et les éléments collectés sont renvoyés.
Un exemple classique est la suite de Fibonacci (chaque nombre est la somme des deux précédents). L'état courant est la paire (a, b). Chaque étape émet b, puis remplace la paire par (b, a + b) :
USING: kernel math sequences ;
! Fibonacci numbers strictly below 100:
0 1 [ dup 100 < ] [ tuck + over ] produce 2nip .
! => { 1 1 2 3 5 8 13 21 34 55 89 }
L'état courant couvre deux valeurs, donc le corps utilise tuck (dans kernel), le réarrangement à trois éléments qui copie le sommet sous le deuxième, pour faire avancer la paire, et 2nip (également dans kernel, l'analogue à deux éléments de nip) pour nettoyer la pile à la fin. Lisons l'appel de gauche à droite :
- Le prédicat
[ dup 100 < ] regarde le sommet de la paire (le prochain nombre à émettre) et continue tant qu'il reste en dessous de la borne.
- Le corps
[ tuck + over ] fait passer l'état à (b, a + b) et émet b, laissant trois valeurs sur la pile : la nouvelle paire en dessous, le nombre émis au sommet.
- Une fois que
produce s'arrête, les deux valeurs restantes (la paire finale) sont écartées avec 2nip, ce qui ne laisse que la séquence produite.
produce est le dual exact de reduce : là où reduce plie une séquence en une valeur, produce déplie une valeur en une séquence.
Exercice d'apprentissage
