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.
Here's my program:
(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)))
and here's the flatmap procedure as described in the book:
(define (flatmap proc seq) (accumulate append nil (map proc seq)))
and the result of an example:
(unique-pair-sum 6 9) ; ((4 3 2) (5 3 1) (6 2 1))
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 replaces each element of a list with a new element in its place:
1 2 3 4 ...
10 20 30 40 ...
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 ...
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.
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:) 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))