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.

Manos

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.

Hoch

Thank you for the answer! I think this clarifies several problems I was having when trying to work with list comprehensions. It is also encouraging to learn that I was overlooking a minor detail, rather than fundamentally misconceiving the issue. I also appreciate the natural language translation, as my studies in Prolog have habituated me to formulating answers in simple declarative statements and constructing algorithms on this basis. – Manos

Would you be interested in weighing in on the relation between this approach and the others offered here? E.g., is there an ideological difference motivating the explicit use of the list monad as opposed to sticking with the list-builder syntax, or is it a mere matter of style/convenience? Regardless, thanks again! – Manos

@aBathologist: I still call myself a Haskell beginner, so my point of view is probably not really a professional one. For me, it's more or less a matter of convenience: the list comprehension syntax is easy to read and can be understood by Haskell beginners. It can even be translated to a monadic form immediately: do { v <- [True, False]; vs <- tValues (n-1); return (v:vs);} (predicates can be done via guard from Control.Monad). This intermediate monadic version can help you to find such elegant ones as m09's flip replicateM [True, False]. At the end it's up to you. – Hoch

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.

Divinity

very nice indeed, better than my version, +1 :) – Asha

and to explicit the part that "uses the monad", we could write it sequence . replicate n $ [True, False] – Asha

Delving even deeper into the monadic library functions, your sequence . replicate n already exists as Control.Monad.replicateM n. – Biliary

so replicateM n [True, False] certainly wins the shortness contest! – Asha

Thank you very much for the answer and for helping rectify my erroneous base case. I will need to do a bit of reading on the list monad to understand how mapM combines the number list and the lambda to generate permutations, and I appreciate the spur to further study. Cheers. – Manos

actually, this is exactly the translation of your Prolog code, maplist(truth_value, N_long_list), because Haskell's list monad expresses nondeterminism by collecting a list of all solutions for a predicate, as if by an implicit findall. So it's exactly the same code, map for map. :) and you're welcome. :) – Divinity

and the numbers in the numbers list are of course ignored by the lambda function with the wild card argument, (\_ -> ...). [1..n] is just "a list of length n". --- as to how it works, i.e. its translation into basic (>>=)-using code, it's equivalent to g 0 = return []; g n = [True, False] >>= (\x-> g (n-1) >>= (\xs-> return (x:xs))), very close to the initial code in m09's answer, and exactly equivalent to your list comprehension code actually. – Divinity

These explanations are very helpful! (With this explicit translation from Prolog add in, your answer ought to be the most "accept"-worthy, but I feel silly shuffling the "award" around, since it's the inessential thing.) Your explanation also helps me appreciate monads as more than just a convoluted notation to accommodate imperative constructs: they seem to facilitate the encapsulation of alternative computational strategies? Many, many thanks for these insightful elucidations. – Manos

"alternative computational strategies" is exactly how monads are usually viewed: list type [] for nondeterminism, Maybe for possibility of failure, Either allows failure to carry its own information, etc. – Divinity

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.

Xylina

Thank you very much for your interesting solution and for giving such an understandable diagnoses of the problem with my base condition. The other answers didn't point out the fact that v <- [] is a failing condition, and understanding this really helps clarify the issue for me. I really like this approach, which generates an abstract object consisting of all possible series of truth values. I do balk a bit at the overhead of having slice the desired sets out of the middle of the infinite list though. But this might be more a psychological issue than a computational one? Many thanks! – Manos

Glad you found value in it! You're correct though, this is definitely not the most efficient solution that has been given here. It's mostly a clever novelty using the same pattern as my favorite definition of the Fibonacci sequence, fibs = 1 : 1 : zipWith (+) fibs (tail fibs) – Xylina

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

Asha

Thank you very much for the answers. My afternoon plan revolves around studying your solutions to understand clearly what's going on. Your list-monad answers do indeed interest me: I would be particularly interested in hearing a bit about the motivation for working with the list monad directly as opposed to just using the list-builder syntax. Are there particular use-cases which lead you one way or the other, or is it more a matter of principle? – Manos

Judging superficially, it looks to like working with the monad leads to a more imperative style what with the binding and return and flip etc.). Is this a common feature of working directly with monads, or am I perhaps misreading here? Many thanks! – Manos

return is not imperative in nature. It's not the same thing as return in an imperative language: it just puts the value it's given into the monad. Here return [] could have been written [[]] as well. flip was just used here to achieve a point-free style, we could have written truthValues n = replicateM n [True, False] instead. Here what is nice about the list monad is that its core --- its bind operation --- does precisely what you want: ie it combines two values in a non-deterministic fashion (a la Prolog). That's why the last solution is so short and to the point. – Asha

yes, replicateM n [True,False] practically says in English, "n non-deterministic Boolean values". very nice indeed. :) --- about return, better name could've been inject - or yield even. – Divinity