Creating all combinations of a set of logical variables in Haskell

Question

I am trying to bow my head to list monads in haskell. I tried to create a list of all possible sentences with a list of strings representing logical variables.

For example, a call:

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

will give the following result:

 [("a",True),("b",True)] [("a",True),("b",False)] [("a",False),("b",True)] [("a",False),("b",False)] 

I managed to do this using lists 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 this using type notations similar to the snippet below, but with a variable number of inputs. Is there any way to do this (nested monads, ...)?

 allPropositions' = do a <- [True, False] b <- [True, False] return([("a",a),("b",b)]) 

Answer 1

You need sequence :: Monad m => [ma] -> m [a] .

In particular, for the monad [] sequence takes a list of lists n and returns all lists of length n that draw one element from each list.

 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 specific case, because if you have a list of n lines, you can easily create features for each line:

 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 select one from each list to get your sentences containing the 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) appears often enough to have a name there:

 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

Here's how I do it:

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

You do not need the full power of monads. All you need is applicative functions .

Here's what happens:

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

Although the ramp answer is correct, it uses sequence and mapM , which are monadic functions. However, as I said, you do not need the full strength of the monads in this case.