Little Schemer：编写只支持长度≤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

Lisp 中的列表（Scheme、Common Lisp 等）是由 cons 单元和一个特殊的（空列表）构建的。也就是说，只要你有一个列表，它就是 either:

空列表()
一个 cons cell（也称为对），其中 car 是列表的第一个元素，cdr这对是列表的其余部分。

因为有两种类型的列表，列表的递归算法通常只回答两个问题：

空列表的结果是什么？
列表其余部分的结果是什么？如何将其转化为整个列表的结果？

对于长度，这意味着：

空列表的长度为0。
当list的rest的长度为n时，整个list的长度为n + 1。

The Little Schemer 中提出的解决方案类型首先开发了一个解决第一种情况的解决方案，这意味着它适用于长度为 ≤0 的列表。一旦您有了可以（正确）处理这两种情况的解决方案，您就有了适用于任何长度列表的解决方案。没有真正的增量解决方案可以扩展函数以处理长度为 ≤2 的列表。

你可以，我想，做这样的事情：

 (((lambda (mk-length)
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l ) 0)
              (else 1)))))

这适用于长度为 0 的列表和长度为 1 的列表，它对所有其他列表都是不正确的，但它对所有其他列表都是 return 1。除非你改变递归的结构，否则我认为那真的是你能做的最好的事情。如果你愿意改变递归的结构，你可以做：

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

但是你真的不应该采用这种方法，因为现在你在三种不同的情况下处理列表而不是两种，这（几乎）从来不是你想要的做。

翻译成 Python

Can this thinking rewrite by python or something process language? It is still hard to image a auto created fun in recurse.

同样的原则适用于 Python，或任何支持高阶函数的语言。在 Python 中更习惯于在本地定义函数然后调用它，而不是直接调用 lambda 表达式，因此这对您来说可能更具可读性：

def length(l):
    def driver(recurse):
        "Returns the result of calling `recurse` with itself."
        return recurse(recurse);
    def zeroForEmptyListOrElseOnePlusRecurse(recurse):
        """Returns a function that returns 0 if its input is the
        empty list, or else returns one plus whatever calling 
        `recurse(recurse)` with the tail of the list returns."""
        def length(l):
            """Returns 0 if l is the empty list, and one plus
            the results of `(recurse(recurse))(l)` otherwise."""
            if l == []:
                return 0;
            else:
                _, *rest = l
                return 1+(recurse(recurse))(rest)
        return length
    return (driver(zeroForEmptyListOrElseOnePlusRecurse))(l)

print(length([1,2,3])) # 3
print(length([1,2]))   # 2
print(length([1]))     # 1
print(length([]))      # 0

Answer 2

TL;DR: (mk-length A)（里面的cond 形式) 计算适用于长度列表 0 的 length 函数，并将使用 (A 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 ...)在;(2)的结果是用来处理的(cdr l)，而 ;(2) 处的 argument 到 mk-length 将在处理 [=] 时替换该调用中的 mk-length 27=].

如果使用 (mk-length eternity)（如您的第一个代码），(cdr l) 处理正常但是 ((eternity eternity) (cddr l)) 自然失败。

如果使用(mk-length (lambda (x) (mk-length eternity)))，(cdr l) 处理正常然后 ((lambda (x) (mk-length eternity)) (lambda (x) (mk-length eternity))) = (mk -length eternity) 用于处理 (cddr l) 这也是可以的（因此，长度 2 被正确处理), 然后 ((eternity 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)。

Little Schemer：编写只支持长度≤2列表的函数

Little Schemer: write function that only supports lists of length ≤ 2

recursion

scheme

y-combinator

the-little-schemer

anonymous-recursion

翻译成 Python