1

我必须在 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)

现在，我之前曾发布过这个主题，并得到了很好的帮助。但是，我得到了新的指导方针来遵守。只能使用嵌套地图找到解决方案。

我一直在做的方法如下：找到由第一组边界指定的所有值（在示例中，(0 1 2)）。这可以通过一个名为(enumerate lowBound highBound). 然后，我需要获取这些数字中的每一个，并在下一组 bounds 中对每个数字进行 cons (0 1 2 3)，从而得到((0 0) (0 1) (0 2) (0 3) (1 0)...).

我写到这里的内容如下：

(define (n-loop op . pairs)
     (apply op (generate pairs))
)

(define (generate pairs)
    (map (lambda (x) (cons x (generate (cdr pairs)))) 
         (map (lambda (x) (enumerate (car x) (cadr x))) pairs))
)

但是对于给定的数字，这(0 1 0 1 2 0 1 2 0 1 2)会在我需要时输出((0 0) (0 1) (0 2) (0 3) (1 0)...)。这是一个讨厌的问题。有没有人有任何见解？

4

1 回答 1

1

这个问题比你想象的要复杂。特别是，生成任意范围列表的笛卡尔积需要更多的工作 - 您是否尝试过使用两个以上范围的过程？这引起了我的兴趣，这次我将给出一个完整的解决方案，只使用为解决方案定义的程序，对列表（cons、car、cdr、append）、lambda和apply的简单操作map。

首先，帮助程序从最简单到最难。我们需要一种方法来生成一系列数字。如果可用，请使用build-listor for-list，但如果您需要从头开始实现它：

(define (enumerate low high)
  (if (>= low high)
      '()
      (cons low
            (enumerate (add1 low) high))))

现在我们需要一种机制来折叠（减少、累积）列表中的值。如果可以使用foldr，否则像这样实现它：

(define (reduce proc lst init)
  (if (null? lst)
      init
      (proc (car lst)
            (reduce proc (cdr lst) init))))

为避免列表中不必要的嵌套，请使用flatmap- 一个映射和展平值列表的过程：

(define (flatmap proc lst)
  (reduce (lambda (e acc)
            (append (proc e) acc))
          lst '()))

这是解决方案的核心 - 一个生成表示范围的任意长值列表的笛卡尔积的过程：

(define (product . args)
  (reduce (lambda (pool result)
            (flatmap (lambda (x)
                       (map (lambda (y)
                              (cons x y))
                            result))
                     pool))
          args
          '(())))

最后，问题中的程序。它使用上面定义的帮助程序，注意到op接收到的参数可以有任意数量（取决于指定的范围数量），所以我们需要apply在每个生成的值元组上使用：

(define (n-loop op . pairs)
  (map (lambda (tuple) (apply op tuple))
       (apply product
              (map (lambda (pair)
                     (enumerate (car pair) (cadr pair)))
                   pairs))))

像这样测试它：

(n-loop (lambda (x y z) (list x y z))
        '(0 2) '(0 3) '(4 6))

> '((0 0 4) (0 0 5) (0 1 4) (0 1 5) (0 2 4) (0 2 5)
    (1 0 4) (1 0 5) (1 1 4) (1 1 5) (1 2 4) (1 2 5))
于 2012-10-22T16:07:28.713 回答