任何人都可以将此代码转换为伪代码

Question

#lang racket
(define (cartesian-product . lists)
(foldr (lambda (xs ys)
            (append-map (lambda (x)
                          (map (lambda (y)
                                 (cons x y))
                               ys))
                        xs))
          '(())
          lists))

(cartesian-product '(1 2 3) '(5 6))

我有球拍朗码，可以计算两个集合或列表的笛卡尔乘积，我不太理解这个代码，谁能把代码转换成伪代码。

Answer 1

该函数对应于笛卡尔积的this定义。

1. The dot . in the argument表示lists将收集所有参数(在一个列表中)，无论传入多少个参数。
2. 如何调用这样的函数？使用apply。它应用了一个使用列表中的项作为参数的函数：(apply f (list x-1 ... x-n)) = (f x-1 ... x-n)
3. foldr只是列表

上自然递归的抽象

; my-foldr : [X Y] [X Y -> Y] Y [List-of X] -> Y
; applies fun from right to left to each item in lx and base
(define (my-foldr combine base lx)
  (cond [(empty? lx) base]
        [else (combine (first lx) (my-foldr func base (rest lx)))]))

应用1)、2)和3)中的简化，并将foldr中的“组合”函数转换为单独的辅助对象：

(define (cartesian-product2 . lists)
  (cond [(empty? lists) '(())]
        [else (combine-cartesian (first lists)
                                 (apply cartesian-product2 (rest lists)))]))

(define (combine-cartesian fst cart-rst)
  (append-map (lambda (x)
                (map (lambda (y)
                       (cons x y))
                     cart-rst))
              fst))

(cartesian-product2 '(1 2 3) '(5 6))

让我们考虑一下combine-cartesian的作用:它只是将n元笛卡尔乘积转换为n元笛卡尔乘积。

我们想要：

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

我们有(first lists) = '(1 2)和递归调用的结果(归纳)：

(cartesian-product '(3 4) '(5 6))
; = 
; '((3 5) (3 6) (4 5) (4 6))

为了从我们拥有的(递归的结果)到我们想要的，我们需要在每个元素上加上cons 1，在每个元素上加上cons 2，并附加这些列表。概括一下，我们得到了使用嵌套循环的组合函数的更简单的重构：

(define (combine-cartesian fst cart)
  (apply append
         (for/list ([elem-fst fst])
           (for/list ([elem-cart cart])
             (cons elem-fst elem-cart)))))

为了增加维度，我们将(first lists)的每个元素都归结到其余元素的笛卡尔乘积的每个元素上。

伪码：

  cartesian product <- takes in 0 or more lists to compute the set of all 
                       ordered pairs
    - cartesian product of no list is a list containing an empty list.
    - otherwise: take the cartesian product of all but one list
                 and add each element of that one list to every 
                 element of the cartesian product and put all 
                 those lists together.