scheme - "The Seasoned Schemer"中的长度函数

Question

我一直在阅读《经验丰富的策划者》，并且遇到了 length 函数的定义

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

后来他们说:

What is the value of (L (lambda (arg) (h arg)))? It is the function

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

我认为我没有完全理解这一点。我想我们应该将L自己定义为一种练习。我使用 letrec 在 length 的定义中编写了 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

在“老练的阴谋家”中，长度最初定义如下:

(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 过程，您不应该重新定义它。本章这一部分的目的是达到我的答案中所示的第二个定义。