1

我很不擅长措辞,所以请多多包涵。

我正在做一个问题,需要我在 Haskell 中以列表列表的形式生成所有可能的数字。

例如,如果我有 x = 3 和 y = 2,我必须生成这样的列表列表:

[[1,1,1], [1,2,1], [2,1,1], [2,2,1], [1,1,2], [1,2,2], [2,1,2], [2,2,2]]

x 和 y 被传递到函数中,它必须与任何非零正整数 x 和 y 一起工作。

我完全迷失了,甚至不知道如何开始。

对于任何好心帮助我的人,请尽量使任何涉及数学的解释尽可能容易理解。我真的不擅长数学。

4

2 回答 2

3

假设这是作业,我会给你答案的一部分,并告诉你我是如何思考这个问题的。在 GHCi 中进行实验并构建我们需要的部分很有帮助。我们需要的一件事是能够生成从 1 到 的数字列表y。假设y是 7。那么:

λ> [1..7]
[1,2,3,4,5,6,7]

但是正如您稍后会看到的,我们真正需要的不是一个简单的列表,而是一个我们可以在其上构建的列表。像这样:

λ> map (:[]) [1..7]
[[1],[2],[3],[4],[5],[6],[7]]

这基本上是说获取数组中的每个元素,并将其添加到空列表中[]。所以现在我们可以编写一个函数来为我们做这件事。

makeListOfLists y = map (:[]) [1..y]

接下来,我们需要一种方法来为列表列表中的每个元素添加一个新元素。像这样的东西:

λ> map (99:) [[1],[2],[3],[4],[5],[6],[7]]
[[99,1],[99,2],[99,3],[99,4],[99,5],[99,6],[99,7]]

(我在这里用了 99 而不是 1,这样你就可以很容易地看到这些数字是从哪里来的。)所以我们可以编写一个函数来做到这一点:

prepend x yss = map (x:) yss

最终,我们希望能够获取一个列表和一个列表列表,并prepend在列表中的每个元素上调用列表列表中的每个元素。map我们可以再次使用该函数来做到这一点。但事实证明,如果我们将参数的顺序切换为 ,这样做会更容易一些prepend,如下所示:

prepend2 yss x = map (x:) yss

然后我们可以这样做:

λ>  map (prepend2 [[1],[2],[3],[4],[5],[6],[7]]) [97,98,99]
[[[97,1],[97,2],[97,3],[97,4],[97,5],[97,6],[97,7]],[[98,1],[98,2],[98,3],[98,4],[98,5],[98,6],[98,7]],[[99,1],[99,2],[99,3],[99,4],[99,5],[99,6],[99,7]]]

所以现在我们可以编写该函数:

supermap xs yss = map (prepend2 yss) xs

使用您的示例,如果 x=2 和 y=3,那么我们需要的答案是:

λ> let yss = makeListOfLists 3
λ> supermap [1..3] yss
[[[1,1],[1,2],[1,3]],[[2,1],[2,2],[2,3]],[[3,1],[3,2],[3,3]]]

(如果这就是我们所需要的,我们可以使用列表推导更轻松地做到这一点。但由于我们需要能够对任意 x 执行此操作,列表推导将不起作用。)

希望您可以从这里获取它,并将其扩展到任意 x。

于 2013-02-04T12:03:00.830 回答
1

对于特定的 x,如前所述,列表推导可以解决问题,假设 x 等于 3,可以编写以下内容:

 generate y = [[a,b,c] | a<-[1..y], b<-[1..y], c <-[1..y]]

但是当 x 不是预先确定的时,生活会变得更加复杂。我没有太多的Haskell编程经验,对库函数不熟悉,我的方法远不是最有效的解决方案,所以不要太苛刻地判断它。

我的解决方案包括两个功能:

strip [] = []
strip (h:t) = h ++ strip t

populate y 2 = strip( map (\a-> map (:a:[]) [1..y]) [1..y])
populate y x = strip( map (\a-> map (:a) [1..y]) ( populate y ( x - 1) ))

strip 是为嵌套列表定义的。通过合并列表项,可以说它减少了层次结构。例如调用

strip [[1],[2],[3]]

生成输出:

[1,2,3]

填充是一个棘手的问题。

在递归的最后一步,当第二个参数等于 2 时,该函数将 [1..y] 的每个项目与同一列表的每个元素映射到一个新列表。例如

map (\a-> map (:a:[]) [1..2]) [1..2])

生成输出:

[[[1,1],[2,1]],[[1,2],[2,2]]]

strip 函数将其变为:

[[1,1],[2,1],[1,2],[2,2]]

至于递归的初始步骤,当 x 大于 2 时,populate 执行几乎相同的操作,只是这次它将列表中的项目与递归调用生成的列表进行映射。最后:

populate 2 3

给了我们想要的结果:

[[1,1,1],[2,1,1],[1,2,1],[2,2,1],[1,1,2],[2,1,2],[1,2,2],[2,2,2]]

正如我上面提到的,这种方法既不是最有效的也不是最易读的方法,但我认为它解决了问题。实际上,从理论上讲,在不大量使用递归的情况下解决此问题的唯一方法是在其中构建带有列表理解语句的字符串,而不是动态编译该字符串,根据我作为程序员的短暂经验,这从来都不是一个好的解决方案。

于 2013-02-04T21:46:05.953 回答