有時你想把一個序列收合成單一的值;有時你想看見收合過程中產生的每一個中間值。Factor 把這兩種需求拆成兩套工具:reduce(位於sequences裡)負責收合成單一值的摺疊,而math.statistics裡的累積系列則負責逐步累積的形式。
reduce:通用的摺疊reduce ( seq init quot: ( prev elt -- next ) -- result )
reduce會一次一個項目地走過序列,沿路帶著一個持續更新的結果(也就是累加器),並把它交給一個接受兩個引數的引述。這個引述會收到目前的累加器和下一個元素;它在堆疊上留下的任何東西,都會成為新的累加器。
USING: math sequences ;
{ 1 2 3 4 } 0 [ + ] reduce . ! => 10
{ 1 2 3 4 } 1 [ * ] reduce . ! => 24
非零的初始值與自訂的合併方式,是reduce能辦到、而sum和product搆不著的部分。例如,找出序列中最大的值,並在沒有任何值能勝過它時採用一個預設值:
USING: math.order ;
{ 3 1 -4 5 -2 } 0 [ max ] reduce . ! => 5
{ -3 -1 -4 } 0 [ max ] reduce . ! => 0
初始值0也參與比較:當每個元素都輸給它時,它就充當結果,因此一個全為負數的序列仍然會產生0,而不是某個任意的最小值。
有時你想要的是每一個中間結果,而不只是最後那一個。math.statistics裡的累積系列會回傳一個與輸入等長的序列,其中每個位置都是對「以該位置結尾的前綴」所做的縮減結果:
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 }
一個實用的模式是串接累積縮減:其中一個的輸出本身就是一個序列,可以直接餵給另一個。如此一來,「持續摘要的持續摘要」就能用兩個詞表達。這些組合很有彈性,只要依照每一步在摘要什麼來兩兩搭配即可。
produce:展開reduce把一個序列消耗成一個值。produce(位於sequences裡)則反其道而行:從一個初始值出發,反覆測試與推進,生成一個序列。
produce ( pred quot -- seq )
每一次疊代都會先在目前的狀態上執行pred;如果它回傳的結果為真,就會呼叫quot來產生下一個元素並更新狀態。當pred回傳f時,疊代就會停止,並回傳收集到的元素。
一個經典的例子是費波那契數列(每個數字都是前兩個數字的和)。持續變動的狀態是(a, b)這一對。每一步會輸出b,接著把這一對換成(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 }
持續變動的狀態橫跨兩個值,所以主體用了tuck(位於kernel裡)來推進這一對,它是把最頂端元素複製到第二個元素下方的三元素重排;最後再用2nip收拾乾淨,它同樣位於kernel,是nip的雙元素版本。把這個呼叫從左到右讀:
[ dup 100 < ]會查看這一對的頂端(也就是下一個要輸出的數字),只要它還在界限之下就繼續。[ tuck + over ]會把狀態推進到(b, a + b)並輸出b,在堆疊上留下三個值:下面是新的一對,上面是剛輸出的數字。produce停止後,尾端剩下的兩個值(最後的那一對)會用2nip丟棄,只留下產生出來的序列。produce是reduce的精確對偶:reduce把序列摺疊成一個值,produce則把一個值展開成序列。
你是圖書館員,負責維護讀者帳戶的帳本。每週都有兩類工作會落到你桌上:
每週你都要結算帳目:處理完請求後的最終餘額、由交易算出的每日累計餘額,以及用來標出罰款暴增時期的累計最低水位。
定義protected-balance,接受一個opening期初餘額和一組requests陣列(帶正負號的金額),依序處理每個請求後回傳最終餘額。若某筆提款會讓餘額低於零,就只處理到可用金額為止,因此累計餘額以零為下限。
100 { 50 -200 30 } protected-balance .
! => 30
500 { 100 -300 -250 } protected-balance .
! => 50
0 { -10 50 } protected-balance .
! => 50
定義running-balance,接受一組transactions陣列,回傳一個長度相同的序列,其中第i個元素是前i+1筆交易之後的餘額(相對於從零開始的餘額)。
{ 50 -30 -20 100 } running-balance .
! => { 50 20 0 100 }
定義least-balance-so-far,接受一組transactions陣列,回傳一個長度相同的序列,其中第i個元素是到第i個位置(含)為止所見過的最低累計餘額。這就是累計最低水位,很適合用來找出帳戶看起來岌岌可危的日子。
{ 50 -30 -20 100 } least-balance-so-far .
! => { 50 20 0 0 }
{ 200 -50 -100 -200 } least-balance-so-far .
! => { 200 150 50 -150 }
圖書館正在推行罰款特赦方案:讀者的未繳餘額每隔一個繳費週期就減半,直到降到寬免門檻或以下為止。定義halve-until,接受一個principal本金和一個target目標值,回傳一連串減半後的值(使用整數除法),從第一次減半開始,只要當下的值仍嚴格高於target就繼續下去。最後產生的值會是第一個降到target或以下的值。
100 5 halve-until .
! => { 50 25 12 6 3 }
64 1 halve-until .
! => { 32 16 8 4 2 1 }
3 5 halve-until .
! => { }