带点尾符号的方案递归

Question

我正在尝试做 SICP 的练习 2.20。它引入了点尾符号。在我完成练习之前，我需要帮助来理解我编写的这个测试程序有什么问题：

(define (f . b)
     (if (null? b) '() (cons (car b) (f . (cdr b)))))

当我在解释器中输入 (f 1 2 3) 时，我得到的不是我预期的 (1 2 3)，而是“超出最大递归深度”错误。

虽然我看不出我做错了什么。 b 是列表 (1 2 3)，所以我应该得到 (cons 1 (f . (2 3)) => (cons 1 (cons 2 (f . (3)))) => (cons 1 (cons 2 (cons 3 (f . ())))) => (1 2 3).

我怀疑问题是点符号只适用于define，但我想写一个递归函数。我该怎么做？

Answer 1

dotted-tail 符号可以与 define 一起使用，这意味着额外的参数被收集在一个列表中。使用 OP (define (f . b) ;...)，在像 (f 1 2 3) 这样的函数调用中，b 绑定到函数体中的列表 (1 2 3)。但是，您不能在函数调用中使用 dotted-tail 表示法。

但仅从尝试的函数调用中删除点 (f . (cdr b)) 也不起作用。问题是 (cdr b) 是一个列表，所以在第一次递归调用之后你有 (f (cdr b)) 这意味着传递给 f 的值是列表 (cdr b)，并且由于定义函数的方式，此列表被收集到另一个列表中并绑定到新函数体中的 b。

如果初始调用是 (f 1 2 3)，那么参数将被收集到一个列表中，以便 b 在第一次调用中绑定到 (1 2 3)。那么(car b)就是1，后面的调用就是(f (2 3))。然后参数 (2 3) 将被收集到一个列表中，以便 b 在第二次调用中绑定到 ((2 3))。现在 (car b) 是 (2 3)，这根本不是我们想要的。

本书稍后会介绍apply，这提供了一个解决难题的方法：

(define (g . b)
  (if (null? b)
      '()
      (cons (car b) (apply g (cdr b)))))

但是，由于我们还不知道 apply，所以我们必须发挥创意。另一种方法是在 f 中定义一个辅助函数，它接受一个列表参数而不是任意数量的参数：

(define (f . b)
  (define (helper xs)
    (if (null? xs)
        '()
        (cons (car xs) (helper (cdr xs)))))
  (helper b))

现在，递归调用是 helper，期望一个列表参数。

交互示例：

> (g 1 2 3)
(1 2 3)
> (f 1 2 3)
(1 2 3)

带点尾符号的方案递归

Scheme recursion with dotted-tail notation

scheme

sicp