Às vezes você quer combinar uma sequência em um único valor;
às vezes você quer ver todos os valores intermediários que a
combinação produz ao longo do caminho. O Factor divide isso em duas
ferramentas: reduce (em sequences) para a redução a um
único valor, e a família cumulativa em math.statistics
para a forma acumulada.
reduce: a redução geral
reduce ( seq init quot: ( prev elt -- next ) -- result )
reduce percorre uma sequência item por item, carregando um
resultado acumulado (o acumulador) e passando-o para uma
quotation de dois argumentos. A quotation recebe o acumulador
atual e o próximo elemento; o que ela deixar na pilha se torna o
novo acumulador.
USING: math sequences ;
{ 1 2 3 4 } 0 [ + ] reduce . ! => 10
{ 1 2 3 4 } 1 [ * ] reduce . ! => 24
Uma semente diferente de zero e um combinador personalizado são as
partes de reduce que sum e product não alcançam. Por exemplo,
o maior valor de uma sequência, com um padrão caso nenhum valor o
supere:
USING: math.order ;
{ 3 1 -4 5 -2 } 0 [ max ] reduce . ! => 5
{ -3 -1 -4 } 0 [ max ] reduce . ! => 0
A semente 0 participa da comparação: ela funciona como o
resultado quando todos os elementos perdem, então uma sequência
só de valores negativos ainda produz 0, e não um menor valor
arbitrário.
Reduções cumulativas
Às vezes você quer todos os resultados intermediários, não apenas o
final. A família cumulativa em
math.statistics retorna uma sequência do mesmo
comprimento que a entrada, em que cada posição é a redução sobre
o prefixo que termina naquela posição:
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 }
Um padrão útil são reduções cumulativas encadeadas: a
saída de uma é ela mesma uma sequência, pronta para alimentar
outra. Isso torna "resumo acumulado de um resumo acumulado"
expressável em duas palavras. As combinações são flexíveis: junte-as
conforme o que cada passo está resumindo.
produce: o desdobramento
reduce consome uma sequência e a transforma em um valor. produce (em
sequences) faz o caminho inverso: gera uma
sequência a partir de uma semente, testando e avançando
repetidamente:
produce ( pred quot -- seq )
Cada iteração primeiro roda pred sobre o estado atual; se ele
retornar um valor verdadeiro, quot é chamado para produzir o próximo elemento
e atualizar o estado. Quando pred retorna f, a iteração para
e os elementos coletados são retornados.
Um exemplo clássico é a sequência de Fibonacci (cada número é
a soma dos dois anteriores). O estado atual é o par
(a, b). Cada passo emite b e então substitui o par por
(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 }
O estado atual abrange dois valores, então o corpo usa tuck
(em kernel), o embaralhamento de três elementos que copia
o topo para baixo do segundo, para avançar o par, e 2nip (também em
kernel, o análogo de dois elementos do nip) arruma tudo no
final. Lendo a chamada da esquerda para a direita:
- O predicado
[ dup 100 < ] espia o topo do par
(o próximo número a ser emitido) e continua enquanto ele
ainda estiver abaixo do limite.
- O corpo
[ tuck + over ] avança o estado para
(b, a + b) e emite b, deixando três valores na pilha:
o novo par embaixo, o número emitido no topo.
- Depois que
produce para, os dois valores restantes (o par
final) são descartados com 2nip, deixando apenas a sequência
produzida.
produce é o dual exato de reduce: onde reduce dobra uma
sequência até reduzi-la a um valor, produce desdobra um valor até
chegar a uma sequência.
Exercício de aprendizagem
