Manchmal möchtest du eine Sequenz zu einem einzigen Wert zusammenfassen,
manchmal möchtest du jeden Zwischenwert sehen, den die Zusammenfassung
dabei erzeugt. Factor teilt das in zwei Werkzeuge auf: reduce (in
sequences) für die Faltung auf einen einzigen Wert und die
kumulative Familie in math.statistics für die
laufende Form.
reduce – die allgemeine Faltung
reduce ( seq init quot: ( prev elt -- next ) -- result )
reduce geht eine Sequenz Element für Element durch, trägt dabei ein
laufendes Ergebnis mit (den Akkumulator) und übergibt es an eine
Quotation mit zwei Argumenten. Die Quotation erhält den laufenden
Akkumulator und das nächste Element; was auch immer sie auf dem Stack
hinterlässt, wird zum neuen Akkumulator.
USING: math sequences ;
{ 1 2 3 4 } 0 [ + ] reduce . ! => 10
{ 1 2 3 4 } 1 [ * ] reduce . ! => 24
Ein Startwert ungleich null und eine eigene Kombinationsfunktion sind die
Teile von reduce, die sum und product nicht erreichen können. Zum
Beispiel der größte Wert in einer Sequenz, mit einem Standardwert, falls
ihn kein Wert übertrifft:
USING: math.order ;
{ 3 1 -4 5 -2 } 0 [ max ] reduce . ! => 5
{ -3 -1 -4 } 0 [ max ] reduce . ! => 0
Der Startwert 0 nimmt am Vergleich teil: Er dient als Ergebnis, wenn
jedes Element unterliegt, sodass eine Sequenz aus lauter negativen Werten
trotzdem 0 liefert statt eines beliebigen kleinsten Werts.
Kumulative Reduktionen
Manchmal möchtest du jeden Zwischenwert, nicht nur den letzten. Die
kumulative Familie in math.statistics gibt eine
Sequenz zurück, die so lang ist wie die Eingabe, wobei jede Position die
Reduktion über das an dieser Position endende Präfix ist:
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 }
Ein nützliches Muster sind verkettete kumulative Reduktionen: Die
Ausgabe der einen ist selbst eine Sequenz, bereit, in eine andere
eingespeist zu werden. So lässt sich „laufende Zusammenfassung einer
laufenden Zusammenfassung“ mit zwei Wörtern ausdrücken. Die Kombinationen
sind flexibel; kombiniere sie danach, was jeder Schritt zusammenfasst.
produce – die Entfaltung
reduce verbraucht eine Sequenz zu einem Wert. produce (in
sequences) geht den umgekehrten Weg und erzeugt aus
einem Startwert eine Sequenz, indem es wiederholt prüft und
weiterschreitet:
produce ( pred quot -- seq )
Jede Iteration führt zuerst pred mit dem aktuellen Zustand aus; liefert
es einen wahren Wert, wird quot aufgerufen, um das nächste Element zu
erzeugen und den Zustand zu aktualisieren. Wenn pred f zurückgibt,
stoppt die Iteration und die gesammelten Elemente werden zurückgegeben.
Ein klassisches Beispiel ist die Fibonacci-Folge (jede Zahl ist die
Summe der beiden vorherigen). Der laufende Zustand ist das Paar
(a, b). Jeder Schritt gibt b aus und ersetzt dann das Paar durch
(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 }
Der laufende Zustand umfasst zwei Werte, deshalb nutzt der Rumpf
tuck (in kernel) – das dreielementige Umordnen, das das
oberste Element unter das zweite kopiert –, um das Paar
weiterzuschieben, und 2nip (ebenfalls in kernel, das zweielementige
Gegenstück zu nip) räumt am Ende auf. Liest man den Aufruf von links
nach rechts:
- Die Prädikat-Funktion
[ dup 100 < ] blickt auf das obere Element des
Paares (die nächste auszugebende Zahl) und fährt fort, solange sie
noch unter der Grenze liegt.
- Der Rumpf
[ tuck + over ] schiebt den Zustand auf (b, a + b)
weiter und gibt b aus, sodass drei Werte auf dem Stack bleiben – das
neue Paar unten, die ausgegebene Zahl oben.
- Nachdem
produce stoppt, werden die beiden abschließenden Werte (das
letzte Paar) mit 2nip verworfen, sodass nur die erzeugte Sequenz
übrig bleibt.
produce ist das exakte Gegenstück zu reduce: Während reduce eine
Sequenz zu einem Wert zusammenfaltet, entfaltet produce einen Wert zu
einer Sequenz.
Lernübung
