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

user_2584427 0
Viewed 581

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.

enter image description here

matrix haskell
3 Answers

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
user_41689720

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.

user_86085140

If you are limited to 4x4 matrices, you can use !! ("Get the Nth element out of a list"):

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

output = [
    [e 0 0,  e 0 1,  e 1 0,  e 1 1],
    [e 0 2,  e 0 3,  e 1 2,  e 1 3],
    [e 2 0,  e 2 1,  e 3 0,  e 3 1],
    [e 2 2,  e 2 3,  e 3 2,  e 3 3]
  ]
    where e i j = mat!!i!!j

General solution

filterByIndex :: (Int -> Bool) -> [a] -> [a]
filterByIndex p xs = [x | (x,i) <- zip xs [0..], p i]

filterByIndex2D :: (Int -> Bool) -> (Int -> Bool) -> [[a]] -> [[a]]
filterByIndex2D pr pc rows = [filterByIndex pc row | (row, i) <- zip rows [0..], pr i]

f :: [[a]] -> [[a]]
f matrix = [
    filterMatrix ( <m) ( <m),
    filterMatrix ( <m) (>=m),
    filterMatrix (>=m) ( <m),
    filterMatrix (>=m) (>=m)
  ]
  where m = (length matrix) `div` 2
        filterMatrix fi fj = concat $ filterByIndex2D fi fj matrix


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

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

Run it

We assume that matrix is a square matrix, and find the index m of a middle element. Then we filter the matrix four times based on this index. Note that this probably is less performant than the 4x4 matrix specific solution above.

user_62313760
Related