SICP Ex2.41：地图和平面图

Question

在 SICP 练习 2.41 中，作者要求您设计一个程序，该程序列出三个小于特定数字的不同数字，然后“过滤”总和等于另一个任意数字的三元组。

这是我的程序：

(define (unique-pair-sum n s)
  (define (unique-triplet a) 
        (flatmap (lambda (i)
           (flatmap (lambda (j)
              (map (lambda (k) (list i j k))
                 (enumerate-interval 1 (- j 1))))
              (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 a)))
  (filter (lambda (x) (= (+ (car x) (cadr x) (caddr x)) s)) 
          (unique-triplet n)))

这是书中描述的 flatmap 过程：

(define (flatmap proc seq) (accumulate append nil (map proc seq)))

和例子的结果：

(unique-pair-sum 6 9) ; ((4 3 2) (5 3 1) (6 2 1))

如您所见，此代码没有任何问题，但是当我将 (lambda (j)...) 之前的“flatmap”更改为简单的“map”时，发生了一些奇怪的事情：

(unique-triplet 6) ; (() () ((3 2 1)) () ((4 2 1)) ((4 3 1) (4 3 2)) () ((5 2 1)) ((5 3 1) (5 3 2)) ((5 4 1) (5 4 2) (5 4 3)) () ((6 2 1)) ((6 3 1) (6 3 2)) ((6 4 1) (6 4 2) (6 4 3)) ((6 5 1) (6 5 2) (6 5 3) (6 5 4)))

但原始代码工作正常：

(unique-triplet 6) ; ((3 2 1) (4 2 1) (4 3 1) (4 3 2) (5 2 1) (5 3 1) (5 3 2) (5 4 1) (5 4 2) (5 4 3) (6 2 1) (6 3 1) (6 3 2) (6 4 1) (6 4 2) (6 4 3) (6 5 1) (6 5 2) (6 5 3) (6 5 4))

我知道这不是一个真正的“问题”，因为我已经设法解决了它（在一些外部帮助下）。我只是好奇这种差异背后的原因。

Answer 1

map 用新元素替换列表中的每个元素：

   1        2        3        4               ...
  10       20       30       40               ...

flatmap 用一些新元素替换列表中的每个元素：

   1        2        3        4               ...
  10 11    20                40 41 42 43      ...

如您所见，如果某些元素被 flatmap 替换为根本没有元素，则与从输入中 过滤掉 相同列表。

并且如果您仅将 flatmap 替换为 map，则列表中的每个元素都将替换为列表中某些新元素的 list地点：

   1        2        3        4               ...
 (10 11)  (20)      ()      (40 41 42 43)     ...

(edit:) 这不是你想要的，在这里，因为你希望空列表消失，以达到过滤效果。

所以你应该在这里做的是有条件地在扩展的最后一步产生它们和splicing-in新值，实现过滤那样，因为

(define (unique-triplets-sum n s)
  (define (unique-triplets-summing-up-to s a) 
     (flatmap (lambda (i)
        (flatmap (lambda (j)
            (flatmap (lambda (k)              ;; NB: flatmap
                       (if (= (+ i j k) s)
                         (list (list i j k))  ;; NB: (list _triplet_)
                         '()))                ;;     OR _empty_list_
                (enumerate-interval 1 (- j 1))))
             (enumerate-interval 1 (- i 1))))
          (enumerate-interval 1 a)))
  (unique-triplets-summing-up-to s n))

>  (unique-triplets-sum 5 8)
'((4 3 1) (5 2 1))

SICP Ex2.41：地图和平面图

SICP Ex2.41: map and flatmap

scheme

filtering

sicp

map-function

flatmap