O Livro-Razão da Bibliotecária

Às vezes queres combinar uma sequência num único valor; outras vezes queres ver todos os valores intermédios que a combinação produz pelo caminho. O Factor divide isto 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 um item de cada vez, levando consigo um resultado acumulado (o acumulador) e alimentando com ele uma quotation de dois argumentos. A quotation recebe o valor acumulado e o elemento seguinte; o que quer que deixe na pilha passa a ser 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 a que sum e product não chegam. Por exemplo, o maior valor de uma sequência, com um valor predefinido 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 na comparação: funciona como resultado quando todos os elementos perdem, pelo que uma sequência só de valores negativos produz na mesma 0, e não um valor mínimo arbitrário.

Reduções cumulativas

Às vezes queres todos os resultados intermédios, não apenas o final. A família cumulativa em math.statistics devolve uma sequência com o mesmo comprimento que a entrada, em que cada posição é a redução sobre o prefixo que termina nessa 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 as reduções cumulativas encadeadas: a saída de uma é ela própria uma sequência, pronta a alimentar outra. Isso torna o "resumo acumulado de um resumo acumulado" exprimível em duas palavras. As combinações são flexíveis: junta-as aos pares com base no que cada passo está a resumir.

produce: o desdobramento

reduce consome uma sequência e produz um valor. produce (em sequences) segue o caminho inverso: gera uma sequência a partir de uma semente, testando e avançando repetidamente:

produce ( pred quot -- seq )

Cada iteração começa por executar pred sobre o estado atual; se devolver um valor verdadeiro, quot é chamada para produzir o elemento seguinte e atualizar o estado. Quando pred devolve f, a iteração para e os elementos reunidos são devolvidos.

Um exemplo clássico é a sequência de Fibonacci (cada número é a soma dos dois anteriores). O estado acumulado é o par (a, b). Cada passo emite b e substitui depois 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 acumulado abrange dois valores, pelo que o corpo usa tuck (em kernel), a reorganização 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 de nip) para arrumar tudo no fim. Lendo a chamada da esquerda para a direita:

• O predicado [ dup 100 < ] espreita o topo do par (o próximo número a emitir) e continua enquanto este 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 em baixo e o número emitido no topo.
• Depois de produce parar, os dois valores que ficam no fim (o par final) são descartados com 2nip, deixando apenas a sequência produzida.

produce é o dual exato de reduce: onde reduce reduz uma sequência a um valor, produce desdobra um valor numa sequência.