published on
tags: scheme

在scheme中实现product函数

在tspl3书上见到的一个习题,简单写一下,就是实现一个product函数,给出一个list,求出它们的乘积。有一个要求是,如果list中有元素0,则不进行乘法。

实现,首先定义下我们用的乘法,统计被调用的次数

(define cnt 0)
(define my-* 
  (lambda (x y) (set! cnt (+ cnt 1)) (* x  y)))

然后思路很简单,我们先检查list有没有0,如果有则直接返回0,否则返回不需要考虑0product,实现如下:

(define (product-1 ls)
  (letrec ((product/without-check 
            (lambda (ls)
              (if (null? ls) 
                  1
                  (my-* (car ls) (product/without-check (cdr ls)))))))
    (if (memq 0 ls)
        0
       (product/without-check ls))))

测试的代码:

(display (product-1 '(1 2 3 4 5))) (newline) ;=> 120
(display cnt) (newline) ;=> 5
(display (product-1 '(7 3 8 0 1 9 5))) (newline) ; => 0
(display cnt) (newline) ;=> 5 (保持不变)

当然这个代码还有另外一种写法,就是使用cps的形式,我们传两个回调,一个代表继续执行,一个用来break迭代过程:

(define (product-2 ls)
  (letrec ((product& (lambda (ls k break)
                       (cond
                         ((null? ls) (k 1))
                         ((= (car ls) 0) (break 0))
                         (else (product& (cdr ls)
                                         (lambda (v)
                                            (k (my-* (car ls) v))) 
                                         break)))))
            (id (lambda (x) x)))
    (product& ls id id)))

同样测试的代码:

(display (product-2 '(1 2 3 4 5))) (newline) ;=> 120
(display cnt) (newline) ;=> 5
(display (product-2 '(7 3 8 0 1 9 5))) (newline) ; => 0
(display cnt) (newline) ;=> 5 (保持不变)

这样就少了一轮迭代过程。