All possible combinations of Three-valued logic values

Question

Is there an algorithm to lead all possible combinations of given amount of three-valued logic values?

For example, F(2) should return this list:

t t
t u
t f
u t
u u
u f
f t
f u
f f

The function would look like this (in Haskell):

data Tril = FALSE | NULL | TRUE

all :: Int -> [[Tril]]
all amount = ???

all1 :: [Tril]
all1 = join (all 1)

all2 :: [(Tril, Tril)]
all2 = map (\[f, s] -> (f, s)) (all 2)

all3 :: [(Tril, Tril, Tril)]
all3 = map (\[f, s, t] -> (f, s, t)) (all 3)

score 7 · Accepted Answer · answered Mar 03 '15 at 10:16

You can do this very simply as a list comprehension:

all2 = [ (v1, v2) | v1 <- [FALSE, TRUE, NULL], v2 <- [FALSE, TRUE, NULL] ]

You can write it equivalently as a monadic do-block:

all2 = do
  v1 <- [FALSE, TRUE, NULL]
  v2 <- [FALSE, TRUE, NULL]
  return (v1, v2)

And that gives us an idea for how we can write the variable-size one:

all 0 = [[]] -- Note: Empty list with one empty item.
all n = do
  v  <- [FALSE, TRUE, NULL]
  vs <- all (n-1)
  return (v:vs)

As it turns out — and this is slightly mind-bending — this is the net effect of the replicateM function. It takes a monadic action, does it N times, and gathers the results together.

all n = replicateM n [FALSE, TRUE, NULL]

score 4 · Answer 2 · answered Mar 03 '15 at 10:07

replicateM does exactly that:

> import Control.Monad
> replicateM 2 [1,2,3]
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

Hence,

all :: Int -> [[Tril]]
all amount = replicateM amount [FALSE,NULL,TRUE]

I'd suggest to pick anouther name, since all is already taken by Prelude.all.

All possible combinations of Three-valued logic values

2 Answers2