3

在The little schemer一书中，我们发现这个函数只支持长度小于或等于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)
4

2 回答 2

2

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

  • 空列表()
  • 一个 cons 单元（也称为对），其中对的汽车是列表的第一个元素，对的cdr是列表的其余部分。

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

  • 空列表的结果是什么？
  • 列表其余部分的结果是什么？如何变成整个列表的结果？

对于length，这意味着：

  • 空列表的长度为 0。
  • 当列表其余部分的长度为n时，整个列表的长度为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 的列表，并且对于所有其他列表都是不正确的，但对于所有其他列表它将返回 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

这种思维可以用python或其他过程语言重写吗？在递归中仍然很难想象一个自动创造的乐趣。

相同的原则适用于 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
于 2015-04-06T21:16:13.820 回答
2

TL;DR：（ 在表格内）计算适用于长度为0的列表的函数，并将用于计算将用于处理参数列表尾部（即 的结果）的函数。(mk-length A)condlength(A A)length(cdr ...)

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

                               (mk-length eternity)               ; length≤1

和

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

作品。

（注意：(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
                                  (lambda (x) (mk-length eternity)) )
                               (cdr l))))))))
     '(1 2))

我们可以看到at的结果是用来处理的，而at的结果会在处理时替换那个调用。(mk-length ...);(2)(cdr l)argumentmk-length;(2)mk-length(cddr l)

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

如果使用，则处理正常，然后用于处理也正常的处理（因此，正确处理长度2），然后自然失败（长度为3及以上）。(mk-length (lambda (x) (mk-length eternity)))(cdr l)((lambda (x) (mk-length eternity)) (lambda (x) (mk-length eternity))) = (mk-length eternity)(cddr l)((eternity eternity) (cdddr l))

因此要处理最多三个元素的列表，

                              ((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 (lambda (x) (mk-length x)))   ; (2)       ; length≤∞

它将列表的下一个元素处理为

                     ((lambda (x) (mk-length x)) (lambda (x) (mk-length x)))
    =
                     (mk-length (lambda (x) (mk-length x)))

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

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

于 2018-01-18T14:18:39.507 回答