Почему append-map вместо карты в рекурсивной декартовой функции продукта?

Question

декартовой функции продукта принимает список списков и возвращает список кортежей с элементом из первого списка в первом положении, элемент из второго в втором положении, и т.д., как показано ниже:

((1 2 3)) -> ((1) (2) (3)) 
((1 2) (3 4)) -> ((1 3) (1 4) (2 3) (2 4)) 

I» m глядя на некоторые из моего старого кода и не могу понять, почему это append-map во внешнем цикле, а не только в карте? Может ли кто-нибудь с большим опытом работы в Racket объяснить это мне?

(define cartesian-product 
    (lambda (s) 
    (if (null? s) 
     '(()) 
     (append-map (lambda (el1) 
         (map (lambda (el2) 
          (cons el1 el2)) 
          (cartesian-product (cdr s)))) 
        (car s))))) 

Answer 1

Потому что вам нужно расплющить список возвращенное рекурсивного вызова cartesian-product, в противном случае вы получите массу нежелательных подсписков, посмотрим, что произойдет, если мы не используем append-map:

(define cartesian-product 
    (lambda (s) 
    (if (null? s) 
     '(()) 
     (map (lambda (el1) 
       (map (lambda (el2) 
         (cons el1 el2)) 
        (cartesian-product (cdr s)))) 
      (car s))))) 

(cartesian-product '((1 2 3) (4 5 6))) 
=> '(((1 (4)) (1 (5)) (1 (6))) ((2 (4)) (2 (5)) (2 (6))) ((3 (4)) (3 (5)) (3 (6)))) 

Сравните это с результатом flattenning списка:

(define cartesian-product 
    (lambda (s) 
    (if (null? s) 
     '(()) 
     (append-map (lambda (el1) 
         (map (lambda (el2) 
          (cons el1 el2)) 
          (cartesian-product (cdr s)))) 
        (car s))))) 

(cartesian-product '((1 2 3) (4 5 6))) 
=> '((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))