Generating all the combinations of a set of boolean variables in Haskell

Question

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.

For instance calling :

mapM_ print $ allPropositions ["a","b"]

would yield the following result :

[("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]

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)])

Answer 1

What you need is sequence :: Monad m => [m a] -> m [a].

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] ]

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) 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

So your desired function is just

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]

Answer 2

This is how I would do it:

allPropositions :: [a] -> [[(a, Bool)]]
allPropositions = foldr (\x xs -> (:) <$> [(x,True),(x,False)] <*> xs) [[]]

You don't need the full power of monads at all. All you need are applicative functors.

Here's whats happening:

1. For the basis case the result is [[]] (i.e. allPropositions [] = [[]]).
2. For the inductive case the result is ⟦(:) [(x,True),(x,False)] xs⟧. Note that the double square brackets (i.e. ⟦⟧) denote the context of an applicative functor (in this case, []).

Although rampion's answer is correct, it makes use of sequence and mapM which are monadic functions. However, as I stated before you don't need the full power of monads in this case.