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

这显然不起作用，我尝试过其他几种方法也不行。我在处理两个列表的隐式递归时遇到了麻烦 - 有什么建议吗？

- David

Answer 1

这里展示的是两个复杂参数的递归，参见《如何设计程序》的第17节。如果需要提示，我可以告诉你这是其中的哪一种情况。

- John Clements

---

嗨John，谢谢回复。我已经看了一下，我相信我正在处理第三种情况。我以前设计过递归函数来解决这种问题，但我不知道如何使用lambda和foldr来做到这一点。我知道foldr如何内在地处理递归，但我只是不知道如何同时在两个列表上工作。 - David

我觉得我需要再想一下，好好休息一下！ - David

我已经想出如何获取 (list (list 'symbol1 1) (list 'symbol1 2))。 - David

不是第三种情况；如果我没记错的话，应该是第一种情况；对于第一个列表中的每个元素，您都希望将其与第二个列表中的所有元素配对。实际上，看起来您上面的评论已经发现了这一点。 - John Clements

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。

我希望这能帮助你，我不想直接给你答案（至少现在不想）——我希望你能自己找出解决方案。

- Óscar López

---

感谢所有提供帮助的人！Oscar，我同意那是一个很好的解决方案，但我需要找到一个使用lambda和foldr的解决方案。幸运的是，我设法解决了...不断地将一个函数包裹在另一个函数内！非常感谢！ - David

Answer 3

这里可能会让人感到困惑的一件事是过度使用list。我将开始使用Haskell符号来解决您的问题。 ::表示“具有类型”，[Foo]表示“Foo列表”。

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

现在看起来你想用foldr来处理list2的问题。

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

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

- Dan Burton