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.