How to Transform a List of Integers to a Matrix of True and False in Haskell

Question

In this exercise I should write a function which receives a list of integers as argument and gives a matrix or list of lists. The point in making the matrix is that the integers represent the number of Trues in each column of the matrix. For example

[2,4,1]

must be translated to:

which in the system is represented as a list of lists:

[ [0,1,0], [0,1,0], [1,1,0], [1,1,1] ]

As it's not easy to manipulate matrices (list of lists) by columns I used a trick and rotate the matrix by 90 degree to the left using transpose which makes the matrix looks like below:

Then I developed the following algorithm to solve the problem:

1. Take the first element of the input list
2. Create a list of length maximum xs (the length of each list is equal to the maximum element in the list)
3. Put so many True in the list as the first element determines.
4. Fill in the the rest of the list with False
5. Do the same for all elements and rotate the matrix

I have tried to implement two solutions but each one has a problem which I cannot solve:

1. This one works for the first element just fine but I do not know how to apply it to all elements of the input list

   listToMatrix x = (replicate ((maximum x) - (head x)) False) ++ (replicate (head x) True)`
   

2. This works for all elements but can not keep the length of the inner list so the lists have different lengths.

   listToMatrix lst@(x:xs) = ((replicate ((maximum lst) - x) False) ++ (replicate x True)) : listToMatrix xs`
   

Question 1: How can I make these functions work with minimal changes?

Question 2: Are more elegant and compact solutions?

P.S. I used 1 and 0 in the matrices to make them more readable but they are in fact True and False

Answer 1

I'd use the following approach, which is compatible with yours.

As you proposed, we use transpose at the end, since the transposed matrix looks easier to generate.

f :: [Int] -> [[Bool]]
f xs = transpose (...)

Then, each element of xs has to generate a new row. We can either use a list comprehension (done below), or alternatively use map.

f :: [Int] -> [[Bool]]
f xs = transpose [ row x | x <- xs ]
  where row :: Int -> [Bool]
        row x = ...

As you suggest, we also need maximum to generate each row, so we compute it once:

f :: [Int] -> [[Bool]]
f xs = transpose [ row x | x <- xs ]
  where m = maximum xs
        row :: Int -> [Bool]
        row x = ...   -- we know x and m, we need m-x Falses and x Trues

Now, you just need to adapt your code.

Answer 2

This is how I would do it:

toMatrix' :: [[Bool]] -> [Int] -> [[Bool]]
toMatrix' acc xs
    | or  bools = toMatrix' (bools : acc) (map pred xs)
    | otherwise = acc
    where bools = map (> 0) xs

toMatrix :: [Int] -> [[Bool]]
toMatrix = toMatrix' []

Simple and straightforward. No need to transpose.

Here's the visualization of my program. I'll use 0 and 1 for False and True respectively.

toMatrix [2,4,1] = toMatrix' []                                [ 2, 4, 1]
                 = toMatrix' [[1,1,1]]                         [ 1, 3, 0]
                 = toMatrix' [[1,1,0],[1,1,1]]                 [ 0, 2,-1]
                 = toMatrix' [[0,1,0],[1,1,0],[1,1,1]]         [-1, 1,-2]
                 = toMatrix' [[0,1,0],[0,1,0],[1,1,0],[1,1,1]] [-2, 0,-3]
                 = [[0,1,0],
                    [0,1,0],
                    [1,1,0],
                    [1,1,1]]

When we call toMatrix' acc xs we first compute bools = map (> 0) xs. If all the elements of bools are False then we're done. We simple return acc. Otherwise we add bools to the beginning of acc and subtract one from each element of xs. Rinse and repeat.

No need to keep track of the biggest element of xs and no need to transpose the matrix. Simple.