2022-09-04 04:45
在"列表处理工具箱"之基础上, 我们继续来检视一些列表处理的习语.
1. append-map
append-map就类似于map, 它的一种可能定义如下.
与map的定义相比, 其实append-map仅仅是将cons替换成了append.
注记. append-map又常被称为flatmap.
平凡的例子多看无益, 我们看看一个稍不平凡的应用吧.
product产生两个列表的"笛卡尔积", 以下是一些例子.
实际上, 我们可以定义更一般的product.
当然了, 一般的product亦可以借助于fold-right之抽象来定义.
以下是一些例子.
当然了, 上面存在一些留待解释的Scheme机制.
一个是apply函数 (而不是形式), 还是举一些例子说明为好.
(apply + '(1 2 3))就相当于(+ 1 2 3), 所以结果是6.
apply函数也可以接受更多的参数, 比如
(apply + 1 2 '(3))也相当于(+ 1 2 3),
也就是说, 多出来的参数会按照顺序拼接到列表的前段.
另一个则是Scheme用以定义接受多个参数的过程的点记号.
理解点记号的方式在于将其视为"模式匹配", 不过"模式"在形式上非常受限.
比如(product . lst*)和(product)匹配会怎样, 要使得两个项相同, 就必须令lst*是();
(product . lst*)和(product (1 2) (a b))匹配会怎样, 要使得两个项相同, 就必须令lst*是((1 2) (a b)).
所以, product可以接受任意多个参数, 然后这些参数会形成一个列表, 此即lst*绑定至的值.
(define (product . lst*) <body>)应该算是句法糖, 脱糖的写法是
(define product (lambda lst* <body>)).
不过, 同样是按照模式匹配来理解.
同理, (define (foo a . x*) <body>)或等价版本(define foo (lambda (a . x*) <body>))定义了接受大于等于一个参数的过程, 并且第一个参数的值和a相关联, 其后的值形成列表与x*相关联.
(define (bar a b . x*) <body>)或等价版本(define bar (lambda (a b . x*) <body>))呢? 你肯定有答案了.
注记. 我必须承认这里的记号并非一致, 但希望读者能够领会我说的意思, 而不是纠结于细节.
2. 生成列表的过程.
这些过程的构造往往需要ad hoc的智慧, 是依照手头事情的特殊性得来的, 我们只看一个例子.
init代表初值, next代表从一值转移到下一值的过程, pred是判断值是否合乎要求的谓词.
利用enumerate之抽象, 常可定义一些较为实用的过程, 比如iota.
以下是一些例子.
练习. 编写过程foo, 以自然数n为输入, 产生所有满足和小于n的自然数三元组的列表.
节末注记. 对于列表处理, 我们侧重的是我们能够表达什么, 而不是效率事务. (事实上, 许多情况下, 列表处理无可救药地低效.) 在某种意义上, APL语言提供了类似的表达力. 在APL中, 一切都是矩阵, 而有许多用于处理矩阵的函数. APL语言实现的策略是尽可能综合这些函数, 比如合成两个操作为一个. 显然, 我们也可以在Scheme实现中内置这样的优化, 比如合成两趟map为一趟. (但是, 鉴于Scheme的灵活性, 为了保持正确的语义, 优化其实很难进行, 但我想对于受限的应用常能发挥很好的效用.)