3

我必须在 Scheme 中定义一个采用以下形式的可变参数函数: (define (n-loop procedure [a list of pairs (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)

显然,汽车和 cdr 将不得不参与我的解决方案。但是使这变得困难的规定如下。根本不使用赋值语句或迭代循环(while 和 for)。

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

4

1 回答 1

4

在 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 中惯用地编写循环的方式,但如果您的分配不允许您使用 named 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循环转换为一个基于 named的循环let。(或者,您可能需要更进一步,将外循环和内循环都转换为它们的letrec形式。)

于 2012-10-08T12:12:03.150 回答