Thinking out of Prolog and into Haskell - Generating Lists of Truth-Value Combinations

Question

I know a bit of a Prolog and have just started some self-study in Haskell. I have been working through the 99 Problems for Haskell, learning much along the way and really enjoying Haskell. Sometimes I try to clarify my understanding of a problem space by coding something in Prolog and then thinking how that solution might relate to a functional approach in Haskell. Tonight, while working on the problems about logic (problems 47 and 48), I got distracted trying to accomplish the simple task of building up a list of the lists of all truth-value combinations with n values. I want a function tValues :: Int -> [[Bool]]. This problem can be solved in a very straightforward and declarative way in Prolog, e.g.:

combinations_of_n_truth_values(N, AllValues) :-
    findall(Values, n_truth_values(N, Values), AllValues).

n_truth_values(N, TruthValues) :-
    length(TruthValues, N),
    maplist(truth_value, TruthValues).

truth_value(true).
truth_value(false).

When used, the variable AllValues will unify with the desired list of lists of truth-values. I would like to know how an experienced Haskell programmer would go about solving this same problem. I would expect there is an equally straightforward and declarative solution, but I can't seem to get my Haskell brain functioning in the right way.

I have fiddled with some semi-analogs using list comprehensions, such as the following:

tValues:: Int -> [[Bool]]
tValues 0 = []
tValues n = [v:vs | v  <- tValue
                  , vs <- tValues (n-1) ] 

tValue :: [Bool]
tValue = [True, False]

but tValues only returns []. I think I just need some human-to-human engagement to help shake my head clear and maybe grace me with a deeper insight.

Many thanks.

Answer 1

In pseudo-code, your list comprehension

[v:vs | v  <- tValue
      , vs <- tValues (n-1) ] 

equals

for any combination of two elements in `tValue`  and `tValues (n-1)`
    cons the first onto the latter

However, tValues has no elements to begin with, it is an empty list. Lets simulate this for n = 1:

tValues 1 = [v:vs | v  <- tValue
                  , vs <- tValues 0 ] 
          = [v:vs | v  <- [True, False]
                  , vs <- [] ] 
            -- since there is no vs
          = []

This propagates throughout the whole recursion. The solution is quite simple: change the base case to contain an empty combination:

tValues 0 = [[]] -- or: return []

Now the simulation yields:

tValues 1 = [v:vs | v  <- tValue
                  , vs <- tValues 0 ] 
          = [v:vs | v  <- [True, False]
                  , vs <- [[]]] 
            -- vs is []
          = [True:[],False:[]]
          = [[True],[False]]

Which is just what we wanted.

Answer 2

With the list monad,

g n = mapM (\_-> [True, False]) [1..n]

About your function's base case. As the function returns a list containing all truth-values lists of length n, it follows that for n=0 it should return a list containing all truth-values lists of length 0, i.e. a list containing one empty list.

Answer 3

truths :: [[Bool]]
truths = [True] : [False] : concatMap (\bs -> [True:bs, False:bs]) truths

truthValues :: Int -> [[Bool]]
truthValues n = dropWhile ((< n) . length) . takeWhile ((<= n) . length) $ truths

truths is an infinite list of all truth value combos, because the lengths increase monotonically we can just take the front part of the list while the lengths are less than or equal to the sets we're looking for, then drop the front of that whose lengths are less.

The reason you are only getting the empty list back is that eventually tValues (n-1) evaluates to tValues 0 which is of course the empty list. Trying to draw from the empty list in a list comprehension causes that iteration to fail. This propagates up the chain of comprehensions. Change the base case to tValues 1 = [[True], [False]] and it will work.

Answer 4

Not a complete answer per se, but if it interests you, with the list monad:

truthValues ∷ Int → [[Bool]]
truthValues 0 = return []
truthValues n = truthValues (n - 1) >>= (\l → [True:l, False:l])

or

truthValues n = foldM (\l _ -> [True:l, False:l]) [] [1..n]

or

truthValues = flip replicateM [True, False]

See also Will Ness' answer and the comments attached :)