在Haskell中生成一组布尔变量的所有组合 [英] Generating all the combinations of a set of boolean variables in Haskell
问题描述
我试图绕过Haskell中列出的单子.给定一个指定布尔变量的字符串列表,我试图生成所有可能命题的列表.
I am trying to bend my head around list monads in haskell. I was trying to generate a list of all possible propositions given a list of strings designating boolean variables.
例如调用:
mapM_ print $ allPropositions ["a","b"]
将产生以下结果:
[("a",True),("b",True)]
[("a",True),("b",False)]
[("a",False),("b",True)]
[("a",False),("b",False)]
我已经成功地使用列表推导和以下代码递归了
I have managed to do it using list comprehensions and recursion with the following code
allPropositions :: [String] -> [[(String,Bool)]]
allPropositions [] = [[]]
allPropositions (x:xs) = [(x,True):r | r <- allPropositions xs] ++ [(x,False):r | r <- allPropositions xs]
我正在寻找一种使用do表示法的方式,该方式类似于以下代码片段,但输入数量可变.有办法做到吗(嵌套的monads,...)?
I was looking for a way to do it using the do notation similar to the following snippet but with a variable number of inputs. Is there a way to do it (nested monads,...) ?
allPropositions' = do
a <- [True, False]
b <- [True, False]
return([("a",a),("b",b)])
推荐答案
您需要的是sequence :: Monad m => [m a] -> m [a]
.
特别是对于[]
monad,sequence
获取一个n
列表的列表,并生成所有n
个长度的列表,一次从每个列表中抽取一个元素.
In particular, for the []
monad, sequence
takes a list of n
lists, and produces all n
-length lists drawing one element from each list at a time.
sequence [ [1,2,3], [4,5], [6] ] =
[ [1,4,6], [1,5,6], [2,4,6], [2,5,6], [3,4,6], [3,5,6] ]
这在您的特定情况下有帮助,因为如果您有一个n
字符串列表,则可以轻松地为每个字符串生成可能性:
This helps in your particular case because if you have a list of n
strings, you can produce the possibilities for each string easily:
map (\s -> [(s,True), (s,False)] ["a", "b", "c"] =
[ [("a", True), ("a", False) ]
, [("b", True), ("b", False) ]
, [("c", True), ("c", False) ]
]
现在您只需要从每个列表中选择一个,就可以使每个变量的真值都保持不变:
now you just need to pick one from each list to get your propositions holding a truth value for each variable:
sequence (map (\s -> [(s,True), (s,False)] ["a", "b", "c"]) =
[ [("a", True), ("b", True), ("c", True)]
, [("a", True), ("b", True), ("c", False)]
, [("a", True), ("b", False), ("c", True)]
, [("a", True), ("b", False), ("c", False)]
, [("a", False), ("b", True), ("c", True)]
, [("a", False), ("b", True), ("c", False)]
, [("a", False), ("b", False), ("c", True)]
, [("a", False), ("b", False), ("c", False)]
]
sequence (map f xs)
经常出现,以至于有个名字:
sequence (map f xs)
comes up often enough that there's a name for it:
mapM f xs = sequence (map f xs)
-- or, point-free style
mapM f = sequence . map f
所以您所需的功能就是
allPropositions vs = mapM (\v -> [(v,True),(v,False)]) vs
-- or, equivalently
allPropositions = mapM (\v -> [(v,True),(v,False)])
-- or, equivalently
allPropositions = mapM $ \v -> [(v,True),(v,False)]
-- or, equivalently, with -XTupleSections
allPropositions = mapM $ \v -> map (v,) [True, False]
这篇关于在Haskell中生成一组布尔变量的所有组合的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!