SICP Ex2.41: map dan flatmap

Question

Dalam SICP Latihan 2.41, penulis meminta Anda untuk merancang prosedur yang membuat daftar tiga bilangan berbeda yang lebih kecil dari bilangan tertentu, dan daripada "menyaring" triplet yang jumlahnya sama dengan bilangan sembarang lainnya.

Inilah program saya:

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

dan berikut flatmapprosedurnya seperti yang dijelaskan di buku:

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

dan hasil contoh:

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

Seperti yang Anda lihat, tidak ada yang salah dengan kode ini, namun ketika saya mengubah " flatmap" sebelumnya (lambda (j)...)menjadi " map", sesuatu yang aneh terjadi:

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

tetapi kode aslinya berfungsi dengan baik:

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

Saya memahami bahwa ini bukanlah "masalah" yang nyata karena saya sudah berhasil menyelesaikannya (dengan bantuan eksternal). Saya hanya ingin tahu tentang alasan di balik perbedaan ini.

Answer 1

map mengganti setiap elemen daftar dengan elemen baru di tempatnya:

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

flatmap mengganti setiap elemen daftar dengan beberapa elemen baru di tempatnya:

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

Seperti yang Anda lihat, jika beberapa elemen diganti tanpa elemen sama sekali oleh flatmap, itu sama seperti jika itu disaring dari daftar input.

Dan jika Anda menggantinya flatmapdengan just map, maka setiap elemen dari list akan diganti dengan list dari beberapa elemen baru sebagai gantinya:

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

(edit :) dan bukan itu yang Anda inginkan, di sini, karena Anda ingin daftar kosong menghilang, untuk mendapatkan efek pemfilteran.

Jadi apa yang seharusnya Anda lakukan di sini, adalah memproduksinya secara kondisional pada langkah terakhir perluasan dan menyambung ke dalam nilai-nilai baru, mencapai pemfilteran seperti itu , seperti

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