recursion - 小阴谋家 : write function that only supports lists of length ≤ 2

Question

在小阴谋家一书中，我们发现这个函数只支持长度小于或等于1的列表:

 (((lambda (mk-length)                                  ; A.
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l ) 0)
              (else (add1 ((mk-length  eternity ) (cdr l))))))))
 '(1))

我想一步步研究，想写一个类似的函数，只支持长度小于或等于2的列表。

请不要通过提供如下代码来回答此问题:

(((lambda (mk-length)                                   ; B.
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l) 0 )
              (else (add1((mk-length mk-length) (cdr l))))))))
 '(a b c d))

因为这个函数支持任意长度。

我已经知道如何编写这样的函数:

(((lambda (mk-length)                                   ; C.
      (mk-length
          (mk-length (mk-length eternity))))
  (lambda (length)
      (lambda (l)
          (cond
              ((null? l) 0)
              (else (add1 (length (cdr l))))))))
 '(1 2)) ;;

为了实现我的目标。但这段代码与第一个代码片段相差不止一步。

也许，我不应该改变:

(lambda (mk-length)                                     ; D.
      (mk-length mk-length)

Answer 1

TL;DR: (mk-length <b>A</b>) (在 cond 表单内)计算 length 函数适用于长度为 0 的列表，并将使用 (<b>A</b> A)计算 length 函数将用于处理参数列表的尾部(即 (cdr ...) 的结果)。

<小时/>

您的第一个代码片段 ( ;A. ) 仅适用于长度为 0 和 1 的列表。为了使它也适用于 2，替换

                               (mk-length <b>eternity</b>)               ; length≤1

与

                               (mk-length   ; (2)                 ; length≤2
                                  <b>(lambda (x) (mk-length eternity))</b>)

有效。

(注意: (mk-length eternity) 本身计算 length≤0 ，但整体函数变为 length≤1 ；这是所有进一步的 length≤i 评论所指的。)

仔细观察

     (((lambda (mk-length)
          (mk-length mk-length))            
      (lambda (mk-length)                   ; (1)
          (lambda (l)                       
              (cond
                  ((null? l ) 0)
                  (else (add1 ((mk-length   ; (2)                 ; length≤2
                                  <b>(lambda (x) (mk-length eternity))</b> )
                               (cdr l))))))))
     '(1 2))

我们可以看到(mk-length <b>...</b>)的结果在;(2)用于处理(cdr l) ，而 argument 至 mk-length在;(2)将取代mk-length在处理 (cddr l) 时的调用中.

如果(mk-length <b>eternity</b>)使用(如您的第一个代码中所示)，(cdr l)处理正常，但是 ((<b>eternity</b> eternity) (cddr l))自然会失败。

如果(mk-length <b>(lambda (x) (mk-length eternity))</b>)使用，(cdr l)处理好然后 (<b>(lambda (x) (mk-length eternity))</b> (lambda (x) (mk-length eternity))) = (mk-length <b>eternity</b>)用于处理(cddr l)这也可以(因此，长度 2 被正确处理)，然后 ((<b>eternity</b> eternity) (cdddr l))自然会失败(对于长度 3 及以上)。

从而处理最多三个元素的列表，

                              ((mk-length   ; (2)                 ; length≤3
                                  (lambda (x) (mk-length 
                                                (lambda (x) (mk-length eternity)))) )

可以使用:

    (define (eternity x) (- 1))    ; to get an error instead of looping

    (((lambda (mk-length)
          (mk-length mk-length))
      (lambda (mk-length)
          (lambda (l)
              (cond
                  ((null? l ) 0)
                  (else (add1 ((mk-length   ; (2)                 ; length≤3
                                  (lambda (x) (mk-length
                                               (lambda (x) (mk-length eternity)))) )
                               (cdr l))))))))

      '(1 2 3))        ; => 3

    ; ...........
    ; '(1 2 3 4))      ; => **error**

正如您所猜测的那样，这是使用的过渡步骤

                     (mk-length <b>(lambda (x) (mk-length x))</b>)   ; (2)       ; length≤∞

将列表的下一个元素的处理变成

                     (<b>(lambda (x) (mk-length x))</b> (lambda (x) (mk-length x)))
    =
                     (<b>mk-length</b> (lambda (x) (mk-length x)))

因此适用于每个列表，无论其长度是多少。

通过 eta 转换，这只是 (mk-length mk-length) .