SICP Ex2.41: mappa e flatmap

Question

Nell'Esercizio 2.41 SICP gli autori chiedono di progettare una procedura che crei elenchi di tre numeri diversi che sono più piccoli di un certo numero, e che "filtri" le terzine le cui somme sono uguali a un altro numero arbitrario.

Ecco il mio programma:

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

ed ecco la flatmapprocedura descritta nel libro:

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

e il risultato di un esempio:

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

Come puoi vedere non c'è niente di sbagliato in questo codice, tuttavia quando cambio il " flatmap" prima (lambda (j)...)in semplicemente " map", accade qualcosa di strano:

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

ma il codice originale funziona bene:

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

Capisco che questo non sia un vero "problema" dato che sono già riuscito a risolverlo (con qualche aiuto esterno). Sono solo curioso del motivo alla base di questa differenza.

Answer 1

map sostituisce ogni elemento di una lista con un nuovo elemento al suo posto:

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

flatmap sostituisce ogni elemento di un elenco con alcuni nuovi elementi al suo posto:

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

Come puoi vedere, se un elemento viene sostituito senza alcun elemento da flatmap, è come se fosse filtrato dall'elenco di input.

E se sostituisci flatmapcon solo map, ogni elemento di un elenco verrà sostituito con un elenco di alcuni nuovi elementi al suo posto:

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

(modifica :) e non è quello che vuoi, qui, perché vuoi che gli elenchi vuoti scompaiano, per ottenere l'effetto di filtraggio.

Quindi quello che avresti dovuto fare qui, è di produrli in modo condizionale nell'ultima fase di espansione e unione dei nuovi valori, ottenendo il filtro in quel modo , come

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