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

这个问题比你想象的要复杂。特别是,生成任意范围列表的笛卡尔积需要更多的工作 - 您是否尝试过使用两个以上范围的过程?这引起了我的兴趣,这次我将给出一个完整的解决方案,只使用为解决方案定义的程序,对列表(conscarcdrappend)、lambdaapply的简单操作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 回答