为什么在递归笛卡尔积函数中用追加映射代替映射?

Question

笛卡尔积函数接受一个列表的列表，并返回一个元组列表，其中第一个列表中的元素位于第一个位置，第二个列表中的元素位于第二个位置，等等。如下所示:

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

我正在看我的一些旧代码，不能弄清楚为什么它在外部循环中是追加映射，而不仅仅是映射?有更有球拍经验的人能给我解释一下吗?

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

将其与列表变平的结果进行比较:

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