Haskell - How can I divide a matrix (2-D array) into groups

Question

I have a 2-D Matrix below:

mat = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

I want to translate it to 4 groups:

output = [[1,2,5,6],[3,4,7,8],[9,10,13,14],[11,12,15,16]]

In other (imperative) programming languages like Java or Python, I can easily create 4 new lists and iterate from the top left position (i,j) of each sub matrix to add the elements in. But in Haskell, I have no ideas how to achieve what I want because it does not support for loop and the recursive loop (x:xs) seems not help this case.

Answer 1

It's useful to write chunksOf which breaks a list into parts, each of a given size.

chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs = ys : chunksOf n zs
  where
    (ys, zs) = splitAt n xs

For example:

> chunksOf 2 "potato"
["po","ta","to"]

(If you know about unfoldr, you can also write chunksOf nicely using that.)

We can use chunksOf 2 to get groups of two rows each, [[1,2,3,4], [5,6,7,8]] and [[9,10,11,12], [13,14,15,16]].

From these we want to group the columns - we can do this by transposing, grouping rows, then transposing each group back again.

(transpose is in Data.List.)

For example, on the first row group, we transpose to get

[[1, 5], [2, 6], [3, 7], [4, 8]]

Then chunksOf 2 gives us

[[[1, 5], [2, 6]], [[3, 7], [4, 8]]]

Then we map transpose to get

[[[1, 2], [5, 6]], [[3, 4], [7, 8]]]

So now we have 2x2 submatrices and the only thing left to get what you wanted is to flatten each one with concat.

Putting it all together:

f :: Int -> [[a]] -> [[a]]
f size = map concat . subMatrices size

subMatrices :: Int -> [[a]] -> [[[a]]]
subMatrices size = concatMap subsFromRowGroup . rowGroups
  where
    rowGroups = chunksOf size
    subsFromRowGroup = map transpose . chunksOf size . transpose

Answer 2

Not very elegant but I think it works. First we define a function to split the rows in half

half xs = (take n xs, drop n xs) 
         where l = length xs `div` 2
               n = if even l then l else l+1

So then we merge the list of pairs like so

merge []        = []
merge [x]       = fst x : snd x : []
merge (x:y:xss) = (fst x ++ fst y) : (snd x ++ snd y) : merge xss

This way we get

> merge $ map half [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
[[1,2,5,6],[3,4,7,8],[9,10,13,14],[11,12,15,16]]

and

> merge $ map half [[1,2,3],[5,6,7],[9,10,11]]
[[1,2,5,6],[3,7],[9,10],[11]]

Which seems to be in accord with the picture you provide.