有时你想把一个序列合并成一个值;有时你又想看到合并过程中产生的每一个中间值。Factor 把这两件事拆成了两组工具:用于单值折叠的 reduce(在 sequences 中),以及 math.statistics 中用于累积形式的累积系列。
reduce:通用的折叠reduce ( seq init quot: ( prev elt -- next ) -- result )
reduce 一次处理序列中的一个元素,沿途带着一个不断更新的结果(也就是累加器),把它交给一个接受两个参数的 quotation。这个 quotation 接收当前的累加器和下一个元素;它留在栈上的结果会成为新的累加器。
USING: math sequences ;
{ 1 2 3 4 } 0 [ + ] reduce . ! => 10
{ 1 2 3 4 } 1 [ * ] reduce . ! => 24
非零的初始值,加上自定义的合并函数,正是 sum 和 product 触及不到的 reduce 的部分。例如,求序列中的最大值,并在没有值能胜过它时给出一个默认值:
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 中)来推进这对值,tuck 是一个三元素重排操作,把栈顶复制到第二个元素下面;最后再用 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 .
! => { }