CODEWITHSUNDEEP
haskellcombinationspermutation
user226447
user226447

Reputation: 55

Generate a truth table of arbitrary length haskell

for an assignment I have to generate a truth table like this:

combinations :: Int -> [[Bool]]

combinations 3 should output:

[[False, False, False],[False, False, True],[False, True, False],[False, True, True][True, False, False][True, False, True],[True, True, False],[True, True, True]]

I can do a list comprehension:

combinations n = [[a,b] | a<-[True,  False], b <-[True, False]]

but that doesn't scale for arbitrary numbers.

Could you please give me a hint?

Upvotes: 1

Views: 974

Answers (2)

AJF
AJF

Reputation: 11913

Adding to @chi 's answer, here's a recursive way of implementing the function. I've renamed it to a snappier truths:

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

those last 3 lines could be rewritten as

truths n = [True,False] >>= \b -> map (b :) (truths (n - 1))

Here we simply append a true/false value to each element in the previous result. The only edge case would be for negative numbers, but you can probably work that out yourself.

I tried this solution out in GHCi, it computes truths 10 in about 0.6 seconds, which is impressive, considering there are 1024 lists, each containing 10 elements.

I also came up with another, more interesting version using sequence from Control.Monad:

import Control.Monad (sequence)

truths :: Int -> [[Bool]]
truths n = sequence (replicate n [True,False])

this will produce the same output. Note that it could also be rewritten in a points-free style as such, to the same effect:

truths = sequence . flip replicate [True,False]

Upvotes: 1

chi
chi

Reputation: 116139

You should reason recursively.

To generate the n-combinations, you can proceed as follows. First, generate all the n-1-combinations: name this list c (this a list of lists of booleans). Then, for every element xs of c (here xs is a list of booleans), generate x:xs where x is an arbitrary boolean. Handle the case n=0 specially, so to provide a base case.

Upvotes: 2

Related Questions