scheme - 方案中的可变参数函数

Question

我必须在Scheme中定义一个可变参数函数，其形式如下: (define (n-loop procedure [(x,y) 对的列表]) 其中对的列表可以是任意长度。

每对指定一个下限和上限。也就是说，以下函数调用:(n-loop (lambda (x y) (inspect (list x y))) (0 2) (0 3)) 生成:

(list x y) is (0 0)
(list x y) is (0 1)
(list x y) is (0 2)
(list x y) is (1 0)
(list x y) is (1 1)
(list x y) is (1 2)

显然，car 和 cdr 必须参与到我的解决方案中。但使这变得困难的规定如下。根本不能使用赋值语句或迭代循环(while 和 for)。

我可以使用 while 和 for 来处理它，以通过对列表进行索引，但看来我必须使用递归。我不需要任何代码解决方案，除非您认为有必要进行解释，但是有人对如何攻击它有建议吗？

Answer 1

在Scheme中进行循环的标准方法是使用尾递归。事实上，假设您有这个循环:

(do ((a 0 b)
     (b 1 (+ a b))
     (i 0 (+ i 1)))
    ((>= i 10) a)
  (eprintf "(fib ~a) = ~a~%" i a))

这实际上被宏扩展为如下所示:

(let loop ((a 0)
           (b 1)
           (i 0))
  (cond ((>= i 10) a)
        (else (eprintf "(fib ~a) = ~a~%" i a)
              (loop b (+ a b) (+ i 1)))))

进一步将其宏扩展为这个(我不会宏扩展cond，因为这与我的观点无关):

(letrec ((loop (lambda (a b i)
                 (cond ((>= i 10) a)
                       (else (eprintf "(fib ~a) = ~a~%" i a)
                             (loop b (+ a b) (+ i 1)))))))
  (loop 0 1 0))

您应该看到这里的 letrec 并思考，“啊哈!我看到递归了!”。确实如此(特别是在这种情况下，尾递归，尽管 letrec 也可以用于非尾递归)。

Scheme 中的任何 迭代循环都可以重写为该形式(命名的 let 版本是在 Scheme 中惯用的编写循环的方式，但是如果您的作业不允许您这样做)使用命名的let，进一步扩展并使用letrec)。我上面描述的宏扩展是简单而机械的，您应该能够看到一个如何转换为另一个。

<小时/>

由于您的问题询问可变参数函数如何，因此您可以这样编写可变参数函数:

(define (sum x . xs)
  (if (null? xs) x
      (apply sum (+ x (car xs)) (cdr xs))))

(顺便说一句，这是一种编写 sum 函数的极其低效的方法；我只是用它来演示如何发送(使用 apply)和接收(使用不正确的 lambda 列表)任意数量的参数。)

<小时/>

更新

好的，这里有一些一般建议:您将需要两个循环:

1. 一个外循环，遍历范围级别(这是你的可变参数)
2. 内部循环，循环遍历每个范围级别中的数字

在每个循环中，仔细考虑:

1. 起始条件是什么
2. 结束条件是什么
3. 你想在每次迭代中做什么
4. 迭代之间是否需要保留任何状态

特别要仔细考虑最后一点，因为在给定任意数量的嵌套级别的情况下，这就是您将如何嵌套循环。 (在下面的示例解决方案中，这就是 cur 变量。)

决定所有这些事情后，您就可以构建解决方案的总体结构。我将在下面发布我的解决方案的基本结构，但是在查看我的代码之前，您应该好好考虑一下您想要如何解决问题，因为它会让您很好地掌握之间的差异你的解决方案方法和我的，它将帮助你更好地理解我的代码。

另外，不要害怕首先使用命令式循环来编写它(例如 do)，然后将其转换为等效的名为 let 的内容。在职的。只需重读第一部分即可了解如何进行该转换。

综上所述，这是我的解决方案(删除了具体细节):

(define (n-loop proc . ranges)
  (let outer ((cur ???)
              (ranges ranges))
    (cond ((null? ranges) ???)
          (else (do ((i (caar ranges) (+ i 1)))
                    ((>= i (cadar ranges)))
                  (outer ??? ???))))))

请记住，一旦您开始工作，您仍然需要将 do 循环转换为基于命名 let 的循环。 (或者，您可能需要更进一步，将外部循环和内部循环都转换为它们的 letrec 形式。)