轨道
/
Factor
Factor
/
练习
/
图书管理员的账本
图书管理员的账本

图书管理员的账本

学习练习

简介

有时你想把一个序列合并成一个值;有时你又想看到合并过程中产生的每一个中间值。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 则把值展开成一个序列。

说明

你是图书管理员,负责记录读者账户的账本。每周有两类工作落到你桌上:

  • 一串请求队列:读者要求记入的贷记(还书、已缴的罚款),以及系统新记录的借记(新产生的逾期罚款)。读者账户带有贷记保护:一笔大到会让账户变成负数的贷记,只记入到实际欠款额度为止,因此余额永远不会降到零以下。
  • 一张交易清单:已经登记到账户上的条目。正数金额是借记(新罚款),负数金额是贷记(付款)。

每周你都要核对账目:处理完请求后的最终余额、由交易得出的每日滚动余额,以及一个用来标出罚款激增时段的滚动低水位标记。

1. 处理请求队列

定义 protected-balance,它接收一个 opening 余额和一个 requests 数组(带符号的金额),依次处理每个请求后返回最终余额。一笔会让余额降到零以下的支取,只记入到可用额度为止,因此滚动余额以零为下限。

100 { 50 -200 30 } protected-balance .
! => 30

500 { 100 -300 -250 } protected-balance .
! => 50

0 { -10 50 } protected-balance .
! => 50

2. 滚动余额

定义 running-balance,它接收一个 transactions 数组,返回一个长度相同的序列,其中第 i 个元素是前 i+1 笔交易之后的余额(相对于从零开始的余额)。

{ 50 -30 -20 100 } running-balance .
! => { 50 20 0 100 }

3. 目前为止的最低余额

定义 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 }

4. 一直减半到目标值

图书馆正在推行一项罚款赦免计划:读者的未结余额在每个缴费周期减半,直到降至或低于免罚阈值。定义 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 .
! => { }
通过 GitHub 编辑 链接将在新窗口或新标签页中打开
Factor Exercism

准备好开始 图书管理员的账本 了吗?

注册 Exercism,借助 47 个概念163 个练习 和真人导师指导,学习并掌握 Factor,全部免费。