对scheme中collector的一点理解

写在前面

collector出现在《 the little schemer》chapter 08中,刷了两遍才算勉强理解,记录下。

collector 的运用,对应着《 the little schemer》中提到了第10戒:Build functions to collect more than one value at a time. 简单理解为创建函数,一次收集多个值,然后对这些值进行再处理。

看个例子,加深对collector的理解。

代码演示

根据《the little schemer》chapter 08 中给出的奇偶数例子稍稍加以改编。

定义函数 number-only*&co,给到一个list, 要求:找出这个list中的所有数字,并求出数字的总和。将总和和新的数字集一并输出。

比如:

; 输出结果的格式(sum newlist), list的第一个元素是求和的结果,第二个元素为所取到数字集。
;
(number-only*&co (quote (9 apples 2 oranges 10 peaches 11 pears)) cal-number)
;Value : (32 (9 2 10 11))

(number-only*&co (quote (9 apples (2 oranges) (10) peaches ((11)) pears)) cal-number)
;Value : (32 (9 (2) (10) ((11))))

这里cal-number 就是一个collector。

来看number-only*&cocal-number的定义:

; define number-only*&co
;
(define number-only*&co
  (lambda (l col)
    (cond
      ((null? l) (col (quote ()) 0))
      ((atom? (car l))
      (cond
        ((number? (car l))
         (number-only*&co (cdr l)
          (lambda (newlat s)
            (col (cons (car l) newlat) (+ (car l) s)))))
        (else (number-only*&co (cdr l) col))))
      (else (number-only*&co (car l)
                           (lambda (al as)
                            (number-only*&co (cdr l)
                              (lambda (dl ds)
                                (col (cons al dl) (+ as ds))))))))))
;
; define cal-number
;
(define cal-number
  (lambda (l s)
    (cons s (cons l (quote ())))))
;

简单解释下:

number-only*&co 接受两个参数,一个是list,一个是collector。

collector接受两个参数,一个是newlist, 一个是 s (s is short for sum), newlist用来存 l 中的数字,s用来存数字求和的结果。

collector的初始值是col((quote ()) 0),也就是newlist 为空,s为0,理解这一点很重要。

  • 当 l 是空的 list 时,number-only*&co的结果就是 (col (quote ()) 0).

  • 当 l 不为空时,判断 l 的第一个元素是不是一个atom:

    • (atom? (car l)) 为 #t, 判断第一个元素是不是number:

      • 第一个元素是number,添加到newlist里面,同时s = s + (car l)。此时新的collector长这样:

        (lambda (newlat s)
           (col (cons (car l) newlat) (+ (car l) s)))
        
      • 第一个元素不是number,那就什么也不做,collector不变,仍然为col。

    • (atom? (car l)) 为 #f:

      这里就要定义 (car l) 后的collector了。这个collector需要使用number-only*&co 来遍历 (cdr l),挑出(cdr l)中的所有数字,并算出这些数字的和。所以,它应该长成这样:

      (lambda (al as)
        (number-only*&co (cdr l)
           (lambda (dl ds)
                ......)))
      

      「这里al, as 是 number-only*&co 处理(car l) 时得到的结果,而dl, ds 是 number-only*&co 处理 (cdr l) 时得到的结果。」

      有了al, dl, as, ds, 后面只需要将两者得到的结果整合起来即可。

      所以,else语句中,最后的collector长这样:

      (lambda (al as)
        (number-only*&co (cdr l)
          (lambda (dl ds)
            (col (cons al dl) (+ as ds)))))
      

至此, number-only*&co 的定义完成。

cal-number 仅仅是一个collector,返回(sum newlist), 没什么特别的。

也可以定义新的collector,比如只返回sum,或者只返回newlist。

(define sum-number
  (lambda (l s)
    s))
;
(define number-list
  (lambda (l s)
    l))

然后调用的时候,使用新的collector:

(number-only*&co (quote (9 apples (2 oranges) (10) peaches ((11)) pears)) sum-number)
;Value: 32

(number-only*&co (quote (9 apples (2 oranges) (10) peaches ((11)) pears)) number-list)
;Value : (9 (2) (10) ((11)))

OK。算是又刷了一遍,可以开启下一章的旅途了。

参考

《The little schemer》