在 Haskell 中生成笛卡尔积
Generating Cartesian products in Haskell
我正在尝试生成 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)，等等
谁能给我指出正确的方向？理想情况下，我宁愿不使用内置函数，因为我正在尝试学习 Haskell，我宁愿花时间去理解一段代码，而不是只使用别人编写的包。不需要元组，列表也可以。
三位数字的组合有哪些？手动写几个出来吧。
000, 001, 002 ... 009, 010, 011 ... 099, 100, 101 ... 998, 999
我们最终 计数 ！我们列举了 0 到 999 之间的所有数字。对于任意数量的数字，这直接概括为：上限为 10^n（不含），其中 n 是数字的数量。
数字是故意这样设计的。如果有可能的三位数字组合不是有效数字，或者如果有一个小于 1000 的数字不能用三位数字组合来表示，那就太奇怪了！
这对我来说是一个简单的计划，只涉及算术，不需要深入理解Haskell*:
- 生成 0 到
10^n 之间的数字列表
- 将每个数字转换为数字列表。
第 2 步是有趣的部分。要提取三位数的数字（以 10 为基数），you do this:
- 取你的数除以 100 的商和余数。商是数字的第一位数字。
- 取第1步的余数，取其对10的商和余数，商为第二位
- 第 2 步的余数是第三位数字。这与对 1 取商相同。
对于 n 位数，我们取商 n 次，从 10^(n-1) 开始到 1 结束。每次，我们都使用上一步的余数作为下一步的输入。这表明我们将数字转换为数字列表的函数应该作为折叠来实现：我们将通过操作对余数进行线程化，并在进行时构建一个列表。 （如果你不是以 10 为基数，我会留给你来弄清楚这个算法是如何变化的！）
现在让我们来实现这个想法。我们想要计算给定数字的指定位数，必要时补零。 digits 的类型应该是什么？
digits :: Int -> Int -> [Int]
嗯，它接受了一些数字和一个整数，并生成了一个整数列表，表示输入整数的数字。该列表将包含一位整数，每个整数都是输入数字的一位。
digits numberOfDigits theNumber = reverse $ fst $ foldr step ([], theNumber) powersOfTen
where step exponent (digits, remainder) =
let (digit, newRemainder) = remainder `divMod` exponent
in (digit : digits, newRemainder)
powersOfTen = [10^n | n <- [0..(numberOfDigits-1)]]
令我吃惊的是，这段代码看起来与我对要执行的算术的英文描述非常相似。我们通过从 0 向上取幂来生成十的幂 table。然后我们将 table 折叠起来；在每一步中，我们将商放在数字列表中，并将余数发送到下一步。我们必须 reverse 最后输出列表，因为它是从右到左构建的。
顺便说一句，生成列表、转换列表然后将其折叠起来的模式在 Haskell 中是惯用的做法。它甚至有自己的夸张的数学名称，hylomorphism。 GHC knows about this pattern too 并且可以将其编译成一个紧密循环，优化您正在使用的列表的存在。
我们来测试一下！
ghci> digits 3 123
[1, 2, 3]
ghci> digits 5 10101
[1, 0, 1, 0, 1]
ghci> digits 6 99
[0, 0, 0, 0, 9, 9]
它就像一个魅力！ （好吧，当 numberOfDigits 对于 theNumber 来说太小时它会表现不正常，但不要在意这一点。）现在我们只需要生成一个使用 digits 的数字列表。
combinationsOfDigits :: Int -> [[Int]]
combinationsOfDigits numberOfDigits = map (digits numberOfDigits) [0..(10^numberOfDigits)-1]
...我们完成了！
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,7],[9,8],[9,9]]
* 对于 需要深入理解 Haskell 的版本，请参阅 。
我的给出了一个算术算法来枚举所有数字的组合。这是通过概括您的示例而产生的替代解决方案。它也适用于非数字，因为它只使用列表结构。
首先，让我们提醒自己如何对三位数组合使用列表理解。
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 comprehensions.
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 大致相同，但有一个额外的语句。再次重写...
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]]
它有效，但我们还没有完成。我想向您展示这是一个更通用的单子模式的实例。首先，我将更改 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]] 的定义，我们可以看到它实际上并不需要使用 lists 本身：它只使用 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 - 尽管 "combinations" 解释仅在你的 monad 代表选择时才有意义。
这段代码确实非常简洁！如此之多，以至于我认为它的工作原理并不完全明显，这与我在其他答案中向您展示的算术版本不同。列表 monad 一直是我发现不太直观的 monad 之一，至少当你使用高阶 monad 组合器而不是 do-notation 时是这样。
另一方面，它的运行速度比数字运算版本快得多。在我的（高规格）MacBook Pro 上，使用 -O2 编译，这个版本计算 5 位数组合的速度比计算数字的版本快 4 倍。 （如果有人能解释我正在听的原因！）
combos 1 list = map (\x -> [x]) list
combos n list = foldl (++) [] $ map (\x -> map (\y -> x:y) nxt) list
where nxt = combos (n-1) list
你的情况
combos 3 [0..9]
我正在尝试生成 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)，等等
谁能给我指出正确的方向？理想情况下，我宁愿不使用内置函数，因为我正在尝试学习 Haskell，我宁愿花时间去理解一段代码，而不是只使用别人编写的包。不需要元组，列表也可以。
三位数字的组合有哪些？手动写几个出来吧。
000, 001, 002 ... 009, 010, 011 ... 099, 100, 101 ... 998, 999
我们最终 计数 ！我们列举了 0 到 999 之间的所有数字。对于任意数量的数字，这直接概括为：上限为 10^n（不含），其中 n 是数字的数量。
数字是故意这样设计的。如果有可能的三位数字组合不是有效数字，或者如果有一个小于 1000 的数字不能用三位数字组合来表示，那就太奇怪了！
这对我来说是一个简单的计划，只涉及算术，不需要深入理解Haskell*:
- 生成 0 到
10^n 之间的数字列表
- 将每个数字转换为数字列表。
第 2 步是有趣的部分。要提取三位数的数字（以 10 为基数），you do this:
- 取你的数除以 100 的商和余数。商是数字的第一位数字。
- 取第1步的余数，取其对10的商和余数，商为第二位
- 第 2 步的余数是第三位数字。这与对 1 取商相同。
对于 n 位数，我们取商 n 次，从 10^(n-1) 开始到 1 结束。每次，我们都使用上一步的余数作为下一步的输入。这表明我们将数字转换为数字列表的函数应该作为折叠来实现：我们将通过操作对余数进行线程化，并在进行时构建一个列表。 （如果你不是以 10 为基数，我会留给你来弄清楚这个算法是如何变化的！）
现在让我们来实现这个想法。我们想要计算给定数字的指定位数，必要时补零。 digits 的类型应该是什么？
digits :: Int -> Int -> [Int]
嗯，它接受了一些数字和一个整数，并生成了一个整数列表，表示输入整数的数字。该列表将包含一位整数，每个整数都是输入数字的一位。
digits numberOfDigits theNumber = reverse $ fst $ foldr step ([], theNumber) powersOfTen
where step exponent (digits, remainder) =
let (digit, newRemainder) = remainder `divMod` exponent
in (digit : digits, newRemainder)
powersOfTen = [10^n | n <- [0..(numberOfDigits-1)]]
令我吃惊的是，这段代码看起来与我对要执行的算术的英文描述非常相似。我们通过从 0 向上取幂来生成十的幂 table。然后我们将 table 折叠起来；在每一步中，我们将商放在数字列表中，并将余数发送到下一步。我们必须 reverse 最后输出列表，因为它是从右到左构建的。
顺便说一句，生成列表、转换列表然后将其折叠起来的模式在 Haskell 中是惯用的做法。它甚至有自己的夸张的数学名称，hylomorphism。 GHC knows about this pattern too 并且可以将其编译成一个紧密循环，优化您正在使用的列表的存在。
我们来测试一下！
ghci> digits 3 123
[1, 2, 3]
ghci> digits 5 10101
[1, 0, 1, 0, 1]
ghci> digits 6 99
[0, 0, 0, 0, 9, 9]
它就像一个魅力！ （好吧，当 numberOfDigits 对于 theNumber 来说太小时它会表现不正常，但不要在意这一点。）现在我们只需要生成一个使用 digits 的数字列表。
combinationsOfDigits :: Int -> [[Int]]
combinationsOfDigits numberOfDigits = map (digits numberOfDigits) [0..(10^numberOfDigits)-1]
...我们完成了！
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,7],[9,8],[9,9]]
* 对于 需要深入理解 Haskell 的版本，请参阅
我的
首先，让我们提醒自己如何对三位数组合使用列表理解。
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 comprehensions.
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 大致相同，但有一个额外的语句。再次重写...
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]]
它有效，但我们还没有完成。我想向您展示这是一个更通用的单子模式的实例。首先，我将更改 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]] 的定义，我们可以看到它实际上并不需要使用 lists 本身：它只使用 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 - 尽管 "combinations" 解释仅在你的 monad 代表选择时才有意义。
这段代码确实非常简洁！如此之多，以至于我认为它的工作原理并不完全明显，这与我在其他答案中向您展示的算术版本不同。列表 monad 一直是我发现不太直观的 monad 之一，至少当你使用高阶 monad 组合器而不是 do-notation 时是这样。
另一方面，它的运行速度比数字运算版本快得多。在我的（高规格）MacBook Pro 上，使用 -O2 编译，这个版本计算 5 位数组合的速度比计算数字的版本快 4 倍。 （如果有人能解释我正在听的原因！）
combos 1 list = map (\x -> [x]) list
combos n list = foldl (++) [] $ map (\x -> map (\y -> x:y) nxt) list
where nxt = combos (n-1) list
你的情况
combos 3 [0..9]