The story begins with writing a test that checks if two boolean expressions are the same.

A boolean expressions may not be easy to transform to canonical form and the code that was being tested did not ensure a canonical form of the statements.

In such situation, writing a “brute force” algorithm that checks if statement A and B result in the same Bool value for all possible combinations of Bool values was the best idea. As a part of the solution, an algorithm that generates a list of lists of all possible combinations of True/False for an arbitrary list length n was needed.

First few values of such function:

combinations 0 = [[]]
combinations 1 = [[True],[False]]
combinations 2 = [[True,True], [True,False], [False,True], [False,False]]

Checking statements A(x,y) == B(x,y) would be equivalent to taking all elements of combinations 2 , substitute for [x,y] and check if statement A gives the same value as B for each element.

Solution

After some time of brain gymnastic I found a solution! It worked, but extremely inefficient…

Using library functions from Data.List we may write a clever code that works, but is quite complicated and slow:

import Data.List ( nub, permutations )

combinations 0 = [[]]
combinations n = nub $ fmap (take n) (permutations $ replicate n True <> replicate n False)

The idea is to take two vectors of length n - one contains only True the other only False, join them together and get all the permutations. Joining those two vectors allows to reach all possible variations of True and False in the vector of size n. Then take only first n elements of each variation vector and remove duplicates.

The obvious drawback is that we permute list of size 2n which we do not need.

General

Other idea is to use list comprehension to expand each of 2^n generated vectors.

combinations' :: Int -> [a] -> [[a]]
combinations' 0 _ = [[]]
combinations' 1 ls = fmap (:[]) ls
combinations' n ls = [x:xs | x <- ls, xs <- combinations' (n-1) ls]

It also does not explicitly use True and False values, but ls, and the function call would be:

> combinations' 3 [True, False]

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

That works well, but is not lazy. An in case of longer variations vectors we would like it to be lazy not to clutter the memory with 2^n vectors.

Elegant

So how can we construct a lazy function for an arbitrary number n?

Let’s outline how this solution would look like.

c0 _ = [[]]
c1 xs = [[x] | x <- xs]

for n=2 we would have

c2 xs = [[x1, x2] | x1 <- xs, x2 <- xs]

We can see where this is going. In fact list comprehension is a syntactic sugar for:

c2 xs = do
  x1 <- xs
  x2 <- xs
  pure [x1, x2]

which is a usecase of replicateM from Control.Monad.

The final, most conicise and lazy solution to our problem is:

combinationsM :: Int -> [[a]]
combinationsM n = replicateM n [True, False]

Lesson learned

By iterative process of writing an algorithm for generating a Cartesian product in n dimensional space, we arrived at a neat and elegant solution - valid for all monads. This is a nice example of why monads are a natural consequence of a thought process of solving some problems.

Another take-away is that it may be a good idea, knowing that a structure you are using (in this case a list) has Applicative instance, to check what functions are already defined and have interesting usecases.