DrRacket 组合列表

Question

我希望有人能引导我走向正确的方向： 我正在寻找两个产生两个列表中所有可能的项目组合：
示例：
给定列表 '(symbol1 symbol2) 和 '(1 2)，我希望生成：
(list (list 'symbol1 1) (list 'symbol1 2) (list 'symbol2 1)(list symbol2 2))

到目前为止我的代码是：

    (define (combiner list1 list2)
    (list
      (foldr (lambda (a b) (foldr (lambda (c d) (list a c)) empty list1)) empty list2)
      (foldr (lambda (a b) (foldr (lambda (c d) (list b d)) empty list1)) empty list2)))

这显然不起作用，我尝试过的其他一些方法也不起作用。我在处理两个列表上的隐式递归时遇到问题 - 有什么想法吗？

Answer 1

您在这里看到的是两个复杂参数的递归， 《如何设计程序》第 17 节。如果您需要其他提示，我会告诉您这是三种情况中的哪一种。

Answer 2

我想到了另一种可能的方法来解决这个问题。这里有一个提示：

(define (combiner list1 list2)
  (define (combine l1 l2)
    (cond ((empty? l1) empty)
          ((empty? l2) XXX)
          (else (cons YYY
                      ZZZ))))
  (combine list1 list2))

在上面的代码中，您必须找出三个问题的答案：

• XXX当您完成对第二个列表的迭代后，如何推进递归，但是第一个列表仍然有元素，并且您还想在第一个列表中前进一个元素吗？
• YYY 如何将第一个列表中的元素与第二个列表中的元素组合起来？
• ZZZ 当两个列表仍有剩余元素时，如何推进递归，但此时您只对推进第二个列表感兴趣？

最后一个提示：请注意，在某些时候您需要“重新启动”第二个列表，为此，您可以参考原始的 list2，它根本没有改变。

我希望这对你有帮助，我不想给你一个直接的答案（还） - 我希望你自己找出解决方案。

Answer 3

似乎这里会增加混乱的一件事是 list 的自由使用。我将开始使用 Haskell 类型表示法来解决您的问题。 :: 表示“有类型”，[Foo] 表示“Foo 列表”。

list1 :: [Symbol]
list2 :: [Number]
type Pair = (Symbol, Number)
(combiner list1 list2) :: [Pair]

现在看来您想通过 list2 上的 foldr 来解决这个问题。

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr 需要 step :: a -> b-> b 和 a start :: b。由于我们希望最终结果是一个[Pair]，这意味着b = [Pair]。那么 start 可能会是空列表。由于 list2 填充了 [a] 槽，这意味着 a = Number。因此，对于我们的问题，step :: Number -> [对]-> [Pair]

combiner :: [Symbol] -> [Number] -> [Pair]
combiner list1 list2 = foldr step start list2
  where step :: Number -> [Pair] -> [Pair]
        step a b = undefined
        start = []

到目前为止，这与您编写的 foldr 相同，只是我尚未定义 step 。那么什么是阶跃函数呢？从类型中，我们知道它必须采用一个 Number 和一个 [Pair] 并生成一个 [Pair]。但这些输入意味着什么？那么 Number 输入将是 list2 的某个元素。 [Pair] 输入将是“到目前为止折叠的结果”。 因此，我们需要获取Number，并执行一些操作来为其创建Pair，然后将它们拍打到到目前为止的结果。 这是我的代码开始与您的代码不同的点。

step a b = append (doSomething a) b
doSomething :: Number -> [Pair]
doSomething a = undefined

由于您使用 Racket 可能会将 doSomething 定义为匿名函数，这意味着 list1 在范围内。 （因为它位于 Haskell 函数的 where 子句中，所以它在作用域内）。您可能会使用该列表来生成组合。

doSomething a = ... a ... list1 ...

实现 doSomething 留给读者作为练习，就像翻译回 Racket 一样。请注意，我在此处定义的 Haskell 函数的类型签名 combiner 可以概括为 [a] -> [b]-> [(a,b)]。