Scheme 列出两个等长列表中元素的所有对排列

Question

我正在尝试将两个 x 坐标和 y 坐标列表组合成方案中的对，我很接近，但无法获得返回的对列表。以下可以使用嵌套循环匹配所有对，但我不确定输出它们的最佳方式，现在我只是将它们显示到控制台。

(define X (list 1 2 3 4 5))
(define Y (list 6 7 8 9 10))
(define (map2d X Y)
    (do ((a  0 (+ a 1)))               ; Count a upwards from 0
        ((= a (length X) ) )           ; Stop when a = length of list
      (do ((b 0 (+ b 1)))              ; Count b upwards from 0
          ((= b (length Y) ) )         ; Stop when  b = length of second list
          (display (cons (list-ref X a) (list-ref Y b))) (newline)
        ))
)
(map2d X Y)

我期待这个函数输出

((1 . 6) (1 . 7) (1 . 8) ... (2 . 6) (2 . 7) ... (5 . 10))

然后我将使用 map 将此列表提供给另一个接受对的函数。

如果你能帮助我使它更具递归性（do 不是 'pure' 函数式的，对吧？）加分，这是我第一次使用函数式编程，递归并不容易掌握。谢谢！

Answer 1

使用 do 不是很地道。您可以尝试嵌套 maps，这更符合 Scheme 的精神 - 使用内置的高阶过程是可行的方法！

; this is required to flatten the list
(define (flatmap proc seq)
  (fold-right append '() (map proc seq)))

(define (map2d X Y)
  (flatmap
   (lambda (i)
     (map (lambda (j)
            (cons i j))
          Y))
   X))

很遗憾你没有使用 Racket，这样会更好：

(define (map2d X Y)
  (for*/list ([i X] [j Y])
    (cons i j)))

Answer 2

Óscar López 的解决方案正确而优雅，并向您介绍了使用函数式语言进行编程的“正确”方式。不过，既然你开始研究递归，我就提出一个简单的递归方案，没有高级函数：

(define (prepend-to-all value y)
  (if (null? y)
      '()
      (cons (cons value (car y)) (prepend-to-all value (cdr y)))))

(define (map2d x y)
  (if (null? x)
      '()
      (append (prepend-to-all (car x) y) (map2d (cdr x) y))))

函数map2d在第一个列表上重复出现：如果为空，则笛卡尔积为空；否则，它将收集通过将 x 的第一个元素添加到 y 的所有元素之前获得的所有对，以及通过将自身应用于 x 的其余部分和所有元素获得的所有对y.

的元素

函数 prepend-to-all 将生成由单个值 value 和列表 y 的所有元素构建的所有对。它在第二个参数列表上重复出现。当 y 为空时，结果是空的对列表，否则，它会用 value 和 y 的第一个元素构建一个对，并将其“conses”在前面的结果上value 到 y.

的所有剩余元素

当你掌握了递归之后，你可以进入下一步，通过学习尾递归，其中对函数的调用不包含在其他一些“构建”形式中，而是第一个递归调用。这种形式的优点是编译器可以将其转换为（多）更高效的迭代程序。以下是此技术应用于您的问题的示例：

(define (map2d x y)
  (define (prepend-to-all value y pairs)
    (if (null? y)
        pairs
        (prepend-to-all value (cdr y) (cons (cons value (car y)) pairs)))) 
  (define (cross-product x y all-pairs)
    (if (null? x)
        (reverse all-pairs)
        (cross-product (cdr x) y (prepend-to-all (car x) y all-pairs))))
  (cross-product x y '()))

关键思想是定义一个带有新参数的辅助函数，该参数在构建时“累积”结果。这个在辅助函数调用中用 () 初始化的“累加器”将被 returned 作为递归的最终情况。在这种情况下，情况更加复杂，因为有两个函数，但您可以研究 prepend-to-all 的新版本以了解其工作原理。请注意，对于 return 自然顺序中的所有对，在 cross-product 函数的末尾，结果是相反的。如果你不需要这个命令，你可以省略reverse以提高函数的效率。

Scheme 列出两个等长列表中元素的所有对排列

Scheme Make list of all pair permutations of elements in two equal length lists

recursion

scheme

nested-loops

mit-scheme