SICP Ex2.41:地图和平面图 [英] SICP Ex2.41: map and flatmap

问题描述

在SICP练习2.41中，作者要求您设计一种程序，该程序将三个不同数字的列表组成，这些列表小于某个数字，并且比过滤器"小.三元组的总和等于另一个任意数.

In SICP Exercise 2.41 the authors ask you to design a procedure that makes lists of three different numbers that are smaller than a certain number, and than "filter" the triplets whose sums are equal to another arbitrary number.

这是我的程序:

(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过程:

and here's the flatmap procedure as described in the book:

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

和示例结果:

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

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

As you can see the there's nothing wrong with this code, however when I change the "flatmap" before (lambda (j)...) to simply "map", something weird happens:

(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)))

但是原始代码可以正常工作:

but the original code works just fine:

(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))

我了解这不是一个真正的问题".因为我已经设法解决了它(需要一些外部帮助).我很好奇这种差异背后的原因.

I understand that this is not a real "problem" since I've already managed to solve it (with some external help). I'm just curious about the reason behind this difference.

推荐答案

map将列表中的每个元素替换为一个新元素:

map replaces each element of a list with a new element in its place:

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

flatmap将列表中的每个元素替换为一些新元素:

flatmap replaces each element of a list with some new elements in its place:

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

如您所见，如果某些元素被flatmap完全替换为没有元素，则与从输入列表中过滤掉一样.

As you can see, if some element is replaced with no elements at all by flatmap, it is the same as if it were filtered out from the input list.

如果仅将flatmap替换为map，则列表中的每个元素都将被替换为 list 的一些新元素:

And if you substitute flatmap with just map, then each element of a list will be replaced with a list of some new elements in its place:

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

(edit :)并不是您想要的，因为您希望空列表消失以达到过滤效果.

(edit:) and that's not what you want, here, because you want the empty lists to disappear, to achieve the filtering effect.

因此，您应该在扩展和扩展新值的最后一步有条件地生成它们，从而实现过滤 ，为

So what you were supposed to do here, is to conditionally produce them at the last step of expansion and splicing-in the new values, achieving the filtering that way, as

(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:地图和平面图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！