Haskell 列表理解创建所有可能的值组合

Question

我想创建一个列表列表，其中包含大小为 n

的较小列表中所有可能的值组合

例如，假设我有列表 [1,2,3]，并且 n 等于 2。输出将是： [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[ 3,3]]

对于固定的 N 听起来很容易，但是对于不确定的 N 值它如何工作？

到目前为止我已经尝试过：

[[x,y] | x <- [1,2,3], y <- [1,2,3]]

这适用于固定为 2 的 n。但我不知道如何让它依赖于 N。

Answer 1

有一个库函数可以做到这一点：它是 Control.Monad 包中的 replicateM：

> import Control.Monad
> replicateM 2 [1,2,3]
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
> replicateM 5 [1,2,3]
[[1,1,1,1,1],[1,1,1,1,2],[1,1,1,1,3],[1,1,1,2,1],....]

但是，如果您有兴趣自己定义它，那么对于未确定的 N 使用单个列表推导式确实无法做到这一点是对的。相反，您需要编写一个递归版本。这个想法是，如果我们已经有了一些 n 的答案，比如 n=2:

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

然后我们可以通过在所有这些列表前加上第一个元素来生成下一个 n (n=3) 的答案：

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

与第二个和第三个元素类似：

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

生成完整的结果列表。

作为列表理解，它看起来像：

combos n lst = [x:xs | x <- lst, xs <- combos (n-1) lst]

我们还需要递归的基本情况。我们可以使用：

combos 0 lst = [[]]

完整的定义是：

combos :: Int -> [a] -> [[a]]
combos 0 lst = [[]]
combos n lst = [x:xs | x <- lst, xs <- combos (n-1) lst]

这按预期工作：

> combos 3 [1,2,3]
[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3]
,[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3]
,[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]

Haskell 列表理解创建所有可能的值组合

Haskell list comprehension creating all possible combinations of values

combinations

haskell

list-comprehension

list