SICP Ex2.41: Karte und Flatmap

Question

In SICP-Übung 2.41 bitten Sie die Autoren, ein Verfahren zu entwerfen, das Listen mit drei verschiedenen Zahlen erstellt, die kleiner als eine bestimmte Zahl sind, und dann die Tripletts "zu filtern", deren Summen einer anderen beliebigen Zahl entsprechen.

Hier ist mein Programm:

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

und hier ist das flatmapim Buch beschriebene Verfahren:

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

und das Ergebnis eines Beispiels:

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

Wie Sie sehen können, ist an diesem Code nichts auszusetzen. Wenn ich jedoch das " flatmap" vorher (lambda (j)...)in " map" " ändere , passiert etwas Seltsames:

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

aber der ursprüngliche Code funktioniert gut:

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

Ich verstehe, dass dies kein echtes "Problem" ist, da ich es bereits geschafft habe, es zu lösen (mit externer Hilfe). Ich bin nur neugierig auf den Grund für diesen Unterschied.

Answer 1

map Ersetzt jedes Element einer Liste durch ein neues Element an seiner Stelle:

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

flatmap Ersetzt jedes Element einer Liste durch einige neue Elemente an seiner Stelle:

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

Wie Sie sehen können, ist flatmapes dasselbe , wenn ein Element durch überhaupt kein Element ersetzt wird , als ob es aus der Eingabeliste herausgefiltert worden wäre .

Und wenn Sie flatmapdurch just ersetzen map, wird jedes Element einer Liste durch eine Liste einiger neuer Elemente an seiner Stelle ersetzt:

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

(bearbeiten :) und das ist hier nicht das, was Sie wollen, weil Sie möchten, dass die leeren Listen verschwinden, um den Filtereffekt zu erzielen.

Was Sie hier also tun sollten, ist , sie im letzten Schritt der Erweiterung und des Einspleißens der neuen Werte bedingt zu erzeugen und die Filterung auf diese Weise zu erreichen

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