How does a function with 'do' work in this context?

user_19129341 0
Viewed 67

So I have found a function on this forum from about 7 years ago and wanted to figure out exactly the way it works as I'm quite new to Haskell and am struggling to understand it.

truths :: Int -> [[Bool]]
truths 0 = [[]]
truths n = do
          x <- [True,False]
          map (x :) (truths (n - 1))

This function basically generates permutations of boolean values of given size n. So truths 3 returns [[True,True,True],[True,True,False],[True,False,True],[True,False,False],[False,True,True],[False,True,False],[False,False,True],[False,False,False]]

I have seen do being used in IO context. But I'm struggling to understand why it works the way it does here.

haskell
1 Answers

For a list, it works equivalent to list comprehension, so:

truths :: Int -> [[Bool]]
truths 0 = [[]]
truths n = [ y | x <- [True,False], y <- map (x :) (truths (n - 1))]

It will thus select True and False for x, and then for each item of the truths (n-1) prepend the items with that x and for each such list return that list as sublist in a list.

You can however here work with replicateM :: Applicative f => Int -> f a -> f [a], indeed:

import Control.Monad(replicateM)

truths :: Int -> [[Bool]]
truths = (`replicateM` [True, False])
user_675790
Related