haskell - 在 Haskell 中生成笛卡尔积

Question

我正在尝试生成 n 个数字的所有可能组合。例如，如果 n = 3 我想要以下组合:

(0,0,0), (0,0,1), (0,0,2)... (0,0,9), (0,1,0)... (9,9,9).

这个 post描述了如何在 n = 3 时这样做:

[(a,b,c) | m <- [0..9], a <- [0..m], b <- [0..m], c <- [0..m] ]

或者为了避免重复(即同一个 n-uple 的多个副本):

let l = 9; in [(a,b,c) | m <- [0..3*l],
                         a <- [0..l], b <- [0..l], c <- [0..l],
                         a + b + c == m ]

然而，对于 n > 3 来说，遵循相同的模式很快就会变得非常愚蠢。 .假设我想找到所有的组合: (a, b, c, d, e, f, g, h, i, j) ， ETC。

谁能在这里指出我正确的方向？理想情况下，我宁愿不使用内置函数，因为我正在尝试学习 Haskell，我宁愿花时间理解一段代码，而不仅仅是使用别人编写的包。不需要元组，列表也可以。

Answer 1

我的 other answer给出了一个算术算法来枚举所有数字的组合。这是通过概括您的示例而产生的替代解决方案。它也适用于非数字，因为它只使用列表的结构。

首先，让我们提醒自己如何使用列表推导来处理三位数组合。

threeDigitCombinations = [[x, y, z] | x <- [0..9], y <- [0..9], z <- [0..9]]

这里发生了什么？列表推导对应于嵌套循环。 z从 0 计数到 9，然后 y上升到 1 和 z再次从 0 开始计数。 x滴答声最慢。正如您所注意到的，当您需要不同的位数时，列表理解的形状会发生变化(尽管以统一的方式)。我们将利用这种一致性。

twoDigitCombinations = [[x, y] | x <- [0..9], y <- [0..9]]

我们想要抽象列表推导中的变量数量(相当于循环的嵌套)。让我们开始玩弄它。首先，我将把这些列表推导重写为等效的单子(monad)推导。

threeDigitCombinations = do
    x <- [0..9]
    y <- [0..9]
    z <- [0..9]
    return [x, y, z]
twoDigitCombinations = do
    x <- [0..9]
    y <- [0..9]
    return [x, y]

有趣的。看起来像 threeDigitCombinations与 twoDigitCombinations 大致相同的一元 Action ，但有一个额外的声明。再重写...

zeroDigitCombinations = [[]]  -- equivalently, `return []`
oneDigitCombinations = do
    z <- [0..9]
    empty <- zeroDigitCombinations
    return (z : empty)
twoDigitCombinations = do
    y <- [0..9]
    z <- oneDigitCombinations
    return (y : z)
threeDigitCombinations = do
    x <- [0..9]
    yz <- twoDigitCombinations
    return (x : yz)

现在应该清楚我们需要参数化的内容:

combinationsOfDigits 0 = return []
combinationsOfDigits n = do
    x <- [0..9]
    xs <- combinationsOfDigits (n - 1)
    return (x : xs)

ghci> combinationsOfDigits' 2
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,1] ... [9,8],[9,9]]

它有效，但我们还没有完成。我想向您展示这是更一般的单子(monad)模式的一个实例。首先我要更改 combinationsOfDigits 的实现以便它折叠一个常量列表。

combinationsOfDigits n = foldUpList $ replicate n [0..9]
    where foldUpList [] = return []
          foldUpList (xs : xss) = do
              x <- xs
              ys <- foldUpList xss
              return (x : ys)

查看 foldUpList :: [[a]] -> [[a]] 的定义，我们可以看到它实际上并不需要使用列表本身:它只使用列表的 monad-y 部分。它可以在任何单子(monad)上工作，而且确实如此!它在标准库中，名为 sequence :: Monad m => [m a] -> m [a] .如果您对此感到困惑，请替换 m与 []你应该看到这些类型的意思是一样的。

combinationsOfDigits n = sequence $ replicate n [0..9]

最后，注意到 sequence . replicate n是 replicateM 的定义，我们把它归结为一个非常活泼的单线。

combinationsOfDigits n = replicateM n [0..9]

总而言之， replicateM n给出输入列表的 n 元组合.这适用于任何列表，而不仅仅是数字列表。事实上，它适用于任何单子(monad)——尽管“组合”解释只有在你的单子(monad)代表选择时才有意义。

这段代码确实非常简洁!如此之多，以至于我认为它的工作原理并不完全明显，这与我在其他答案中向您展示的算术版本不同。 list monad 一直是我觉得不太直观的 monad 之一，至少当你使用高阶 monad 组合器而不是 do 时。 -符号。

另一方面，它的运行速度比数字运算版本快得多。在我的(高规范)MacBook Pro 上，使用 -O2 编译，这个版本计算 5 位数字组合的速度比处理数字的版本快 4 倍。 (如果有人能解释我正在听的原因!)