"The Seasoned Schemer"中的长度函数

Question

我一直在阅读The Seasoned Schemer,我遇到了长度函数的这个定义

(define length
  (let ((h (lambda (l) 0)))
    (set! h (L (lambda (arg) (h arg))))
    h))

后来他们说:

(L(lambda(arg)(h arg)))的值是多少？这是功能

(lambda (l)
  (cond ((null? l) 0)
     (else (add1 ((lambda (arg) (h arg)) (cdr l))))))

我不认为我完全理解这一点.我想我们应该将L自己定义为练习.我使用letrec 在长度定义中写了L的定义.这是我写的:

(define length
  (let ((h (lambda (l) 0)))
    (letrec ((L
              (lambda (f)
                (letrec ((LR
                          (lambda (l)
                            (cond ((null? l) 0)
                                  (else
                                   (+ 1 (LR (cdr l))))))))
                  LR))))                  
    (set! h (L (lambda (arg) (h arg))))
    h)))

因此,L将一个函数作为其参数并返回另一个函数,该函数将列表作为其参数并在列表上执行递归.我的解释是正确还是无可救药？无论如何,定义有效

 (length (list 1 2 3 4))  => 4

Answer 1

在《老谋深算》中length最初是这样定义的：

(define length
  (let ((h (lambda (l) 0)))
    (set! h (lambda (l)
              (if (null? l)
                  0
                  (add1 (h (cdr l))))))
    h))

在本书的后面，前面的结果被概括并length根据Y!（应用顺序、命令式 Y 组合器）重新定义，如下所示：

(define Y!
  (lambda (L)
    (let ((h (lambda (l) 0)))
      (set! h (L (lambda (arg) (h arg))))
      h)))

(define L
  (lambda (length)
    (lambda (l)
      (if (null? l)
          0
          (add1 (length (cdr l)))))))

(define length (Y! L))

问题中显示的第一个定义length只是一个中间步骤 -L过程与上面定义的完全相同，您不应该重新定义它。本章这一部分的目的是达到我的答案中所示的第二个定义。