SICP Ex2.41: mapa i mapa płaska

Question

W ćwiczeniu SICP 2.41 autorzy proszą cię o zaprojektowanie procedury, która tworzy listy trzech różnych liczb, które są mniejsze od określonej liczby, a następnie „filtruje” trojaczki, których sumy są równe innej dowolnej liczbie.

Oto mój 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)))

a oto flatmapprocedura opisana w książce:

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

i wynik przykładu:

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

Jak widać, nie ma nic złego w tym kodzie, jednak kiedy zmieniam " flatmap" przed (lambda (j)...)po prostu map", dzieje się coś dziwnego:

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

ale oryginalny kod działa dobrze:

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

Rozumiem, że to nie jest prawdziwy „problem”, ponieważ udało mi się go już rozwiązać (z jakąś pomocą z zewnątrz). Ciekawi mnie tylko powód tej różnicy.

Answer 1

map zastępuje każdy element listy nowym elementem w jego miejsce:

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

flatmap zastępuje każdy element listy nowymi elementami w jego miejsce:

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

Jak widać, jeśli jakiś element zostanie zastąpiony bez żadnych elementów przez flatmap, wygląda to tak samo, jakby został odfiltrowany z listy wejściowej.

A jeśli zastąpisz flatmapjust map, to każdy element listy zostanie zastąpiony listą nowych elementów:

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

(edytuj :) i nie tego chcesz tutaj, ponieważ chcesz, aby puste listy zniknęły, aby uzyskać efekt filtrowania.

Więc to, co miałeś tutaj zrobić, to warunkowo wytworzyć je na ostatnim etapie rozszerzania i dołączania nowych wartości, uzyskując filtrowanie w ten sposób , jak

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