练习 1.43

对于表达式：

(repeated f n)

repeated 函数返回一个接受单个参数 x 的函数 g ，在这个函数 g 的函数体内， f 被调用了 n 次。

比如说，表达式 (repeated square 4) 的展开式应该为：

(repeated square 4)

(lambda (x)
    (square ((repeated square 3)
             x)))

(lambda (x)
    (square ((lambda (x)
                 (square ((repeated square 2)
                          x)))
             x)))

(lambda (x)
    (square ((lambda (x)
                 (square ((lambda (x)
                              (square ((repeated square 1) x)))
                          x)))
             x)))

(lambda (x)
    (square ((lambda (x)
                 (square ((lambda (x)
                              (square (square x)))
                          x)))
             x)))

repeated

根据前面列出的规则，可以给出相应的 repeated 函数（递归计算）：

;;; 43-repeated.scm

(define (repeated f n)
    (if (= n 1)
        f
        (lambda (x)
            (let ((fs (repeated f (- n 1))))
                (f (fs x))))))

; 无 let 版本
;
; (define (repeated f n)
;    (if (= n 1)
;        f
;        (lambda (x)
;            (f ((repeated f (- n 1)) x)))))

repeated 也可以迭代地计算：

;;; 43-iter-repeated.scm

(define (repeated f n)
    (define (iter i repeated-f)
        (if (= i 1)
            repeated-f
            (iter (- i 1)
                  (lambda (x)
                      (f (repeated-f x))))))
    (iter n f))

带 compose 的 repeated

事实上，我们完全不必使用 lambda 来显式地组合起两个函数（因为这样容易出错），使用 练习 1.42 的 compose 就可以更好地完成这件事。

以下是使用 compose 定义的递归计算的 repeated ：

;;; 43-rec-repeated-using-compose.scm

(load "42-compose.scm")

(define (repeated f n)
    (if (= n 1)
        f
        (compose f
                 (repeated f (- n 1)))))

迭代计算的 repeated 也可以用 compose 来定义：

;;; 43-iter-repeated-using-compose.scm

(load "42-compose.scm")

(define (repeated f n)
    (define (iter i repeated-f)
        (if (= i 1)
            repeated-f
            (iter (- i 1)
                  (compose f repeated-f))))
    (iter n f))

测试

无 compose ，递归计算的 repeated ：

1 ]=> (load "43-repeated.scm")

;Loading "43-repeated.scm"... done
;Value: repeated

1 ]=> ((repeated square 2) 5)

;Value: 625

无 compose ，迭代计算的 repeated ：

1 ]=> (load "43-iter-repeated.scm")

;Loading "43-iter-repeated.scm"... done
;Value: repeated

1 ]=> ((repeated square 2) 5)

;Value: 625

带 compose ，递归计算的 repeated ：

1 ]=> (load "43-rec-repeated-using-compose.scm")

;Loading "43-rec-repeated-using-compose.scm"...
;  Loading "42-compose.scm"... done
;... done
;Value: repeated

1 ]=> ((repeated square 2) 5)

;Value: 625

带 compose ，迭代计算的 repeated ：

1 ]=> (load "43-iter-repeated-using-compose.scm")

;Loading "43-iter-repeated-using-compose.scm"...
;  Loading "42-compose.scm"... done
;... done
;Value: repeated

1 ]=> ((repeated square 2) 5)

;Value: 625

讨论

blog comments powered by Disqus