SICP Ex2.41: mapa e mapa plano

Question

No Exercício 2.41 do SICP, os autores pedem que você projete um procedimento que faça listas de três números diferentes que são menores do que um determinado número e que "filtre" os tripletos cujas somas são iguais a outro número arbitrário.

Este é meu programa:

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

e aqui está o flatmapprocedimento conforme descrito no livro:

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

e o resultado de um exemplo:

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

Como você pode ver, não há nada de errado com esse código, porém quando eu mudo o " flatmap" antes (lambda (j)...)para simplesmente " map", algo estranho acontece:

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

mas o código original funciona bem:

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

Eu entendo que este não é um "problema" real, pois já consegui resolvê-lo (com alguma ajuda externa). Estou apenas curioso para saber a razão por trás dessa diferença.

Answer 1

map substitui cada elemento de uma lista por um novo elemento em seu lugar:

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

flatmap substitui cada elemento de uma lista por alguns novos elementos em seu lugar:

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

Como você pode ver, se algum elemento for substituído sem nenhum elemento por flatmap, é o mesmo como se fosse filtrado da lista de entrada.

E se você substituir flatmapapenas map, cada elemento de uma lista será substituído por uma lista de alguns novos elementos em seu lugar:

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

(edite :) e não é isso que você deseja, aqui, porque deseja que as listas vazias desapareçam, para obter o efeito de filtragem.

Então, o que você deveria fazer aqui, é produzi-los condicionalmente na última etapa de expansão e junção nos novos valores, conseguindo a filtragem dessa forma , como

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