3

我希望有人能指导我正确的方向：我正在寻找两个产生两个列表中所有可能的项目组合：
示例：
给定列表'（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)))

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

4

3 回答 3

4

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

于 2011-11-19T01:14:30.017 回答
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，它根本没有改变。

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

于 2011-11-19T02:16:34.930 回答
0

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

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

现在看起来你想用一个foldrover list2 来解决这个问题。

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

foldr 需要 astep :: a -> b -> b和 a start :: b。由于我们希望最终结果是 a [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。那么什么是阶跃函数呢？从类型中，我们知道它必须采用 aNumber和 a[Pair]并产生 a [Pair]。但是这些输入是什么意思？那么Number输入将是list2. [Pair]输入将是“到目前为止折叠的结果” 。所以我们要使用我们的Number, 并做一些事情来为它创建Pairs ，然后将它们添加到迄今为止的结果上。这就是我的代码开始与你的不同的地方。

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

于 2011-11-19T02:48:31.680 回答