A volte vuoi combinare una sequenza in un unico valore, altre volte vuoi vedere ogni valore intermedio che la combinazione produce lungo il percorso. Factor divide questi due casi in due strumenti: reduce (in sequences) per la riduzione a un valore singolo, e la famiglia cumulativa in math.statistics per la forma progressiva.
reduce: la riduzione generale
reduce ( seq init quot: ( prev elt -- next ) -- result )
reduce attraversa una sequenza un elemento alla volta, portando con sé un risultato corrente (l'accumulatore) e passandolo a una quotation a due argomenti. La quotation riceve l'accumulatore corrente e l'elemento successivo; qualunque cosa lasci sullo stack diventa il nuovo accumulatore.
USING: math sequences ;
{ 1 2 3 4 } 0 [ + ] reduce . ! => 10
{ 1 2 3 4 } 1 [ * ] reduce . ! => 24
Un seme diverso da zero e un combinatore personalizzato sono le parti di reduce a cui sum e product non arrivano. Per esempio, il valore più grande in una sequenza, con un valore predefinito se nessun elemento lo supera:
USING: math.order ;
{ 3 1 -4 5 -2 } 0 [ max ] reduce . ! => 5
{ -3 -1 -4 } 0 [ max ] reduce . ! => 0
Il seme 0 partecipa al confronto: diventa il risultato quando ogni elemento perde, quindi una sequenza di valori tutti negativi produce comunque 0 invece di un arbitrario valore minimo.
Riduzioni cumulative
A volte vuoi ogni risultato intermedio, non solo quello finale. La famiglia cumulativa in math.statistics restituisce una sequenza della stessa lunghezza dell'input, in cui ogni posizione è la riduzione del prefisso che termina in quella posizione:
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 modello utile è quello delle riduzioni cumulative concatenate: l'output di una è a sua volta una sequenza, pronta per essere passata a un'altra. Così un «riepilogo progressivo di un riepilogo progressivo» si esprime in due parole. Le combinazioni sono flessibili: abbinale in base a ciò che ogni passo sta riepilogando.
produce: la generazione
reduce consuma una sequenza per produrre un valore. produce (in sequences) va nella direzione opposta: genera una sequenza a partire da un seme, testando e avanzando ripetutamente:
produce ( pred quot -- seq )
Ogni iterazione esegue prima pred sullo stato corrente; se il risultato è vero, viene chiamata quot per produrre l'elemento successivo e aggiornare lo stato. Quando pred restituisce f, l'iterazione si ferma e gli elementi raccolti vengono restituiti.
Un esempio classico è la sequenza di Fibonacci (ogni numero è la somma dei due precedenti). Lo stato corrente è la coppia (a, b). Ogni passo emette b, poi sostituisce la coppia con (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 }
Lo stato corrente occupa due valori, quindi il corpo usa tuck (in kernel), lo shuffle a tre elementi che copia l'elemento in cima sotto il secondo, per far avanzare la coppia, e 2nip (anch'esso in kernel, l'analogo a due elementi di nip) per mettere a posto le cose alla fine. Leggiamo la chiamata da sinistra a destra:
- Il predicato
[ dup 100 < ] guarda in cima alla coppia (il prossimo numero da emettere) e continua finché è ancora sotto il limite.
- Il corpo
[ tuck + over ] porta lo stato a (b, a + b) ed emette b, lasciando tre valori sullo stack: la nuova coppia sotto e il numero emesso in cima.
- Dopo che
produce si ferma, i due valori finali (l'ultima coppia) vengono scartati con 2nip, lasciando solo la sequenza prodotta.
produce è l'esatto duale di reduce: dove reduce riduce una sequenza a un valore, produce genera una sequenza a partire da un valore.
Esercizio di apprendimento
