CODEWITHSUNDEEP
haskellmatrix
John Bugner
John Bugner

Reputation: 103

How to Transform a Matrix According to Chunks in Haskell

I want a function that takes a integer n, and a square matrix of size (n*n) x (n*n), and returns a matrix where each chunk (of size n x n) is now a row, ordering chunks by going from left-to-right, then top-to-bottom.

For example:

type Matrix a = [[a]]

chunks :: Int -> Matrix a -> Matrix a
chunks n = ...

Example : chunks 2 a == b

   a           b
+--+--+     +--+--+
|ab|cd|     |ab|ef|
|ef|gh|     |cd|gh|
+--+--+ --> +--+--+
|ij|kl|     |ij|mn|
|mn|op|     |kl|op|
+--+--+     +--+--+

Example : chunks 3 c == d

      c                 d
+---+---+---+     +---+---+---+
|abc|def|ghi|     |abc|jkl|stu|
|jkl|mno|pqr|     |def|mno|vwx|
|stu|vwx|yzA|     |ghi|pqr|yzA|
+---+---+---+     +---+---+---+
|BCD|EFG|HIJ|     |BCD|KLM|TUV|
|KLM|NOP|QRS| --> |EFG|NOP|WXY|
|TUV|WXY|Z$%|     |HIJ|QRS|Z$%|
+---+---+---+     +---+---+---+
|...|...|...|     |...|...|...|
|...|...|...|     |...|...|...|
|...|...|...|     |...|...|...|
+---+---+---+     +---+---+---+

*** Edit:

The answer:

chunks :: Int -> [[a]] -> [[a]]
chunks n m = concat (map chunks' (splitEvery n m))
    where
        chunks' :: [[a]] -> [[a]]
        chunks' m = map concat (transpose (map (splitEvery n) m))

I suppose I should define splitEvery too:

splitEvery :: Int -> [a] -> [[a]]
splitEvery _ [] = []
splitEvery n xs = chunk : (splitEvery n xxs)
    where
        (chunk, xxs) = splitAt n xs

Upvotes: 1

Views: 129

Answers (1)

ErikR
ErikR

Reputation: 52029

Here are some hints:

Note that some elements always stay together. For example, in the 2x2 case "ab" stays together, as does "cd", "ef", "gh", etc. In fact, you canvisualize the transformation this way:

+---+---+          +---+---+
| 1 | 2 |          | 1 | 3 |        1 = ab
| 3 | 4 |          | 2 | 4 |        2 = cd
+---+---+   --->   +---+---+        3 = ef
| 5 | 6 |          | 5 | 7 |        4 = gh
| 7 | 8 |          | 6 | 8 |        5 = ...
+---+---+          +---+---+

And observe how each row gets transformed:

1 2   ->   1 3
3 4        2 4

5 6   ->   5 7
7 8        6 8

Think about your linear algebra class. Do these transformations look familiar? Note that the diagonal elements don't move.

Now have a look at this section from the Data.List docs, and see if one of those functions seems applicable:

https://hackage.haskell.org/package/base-4.8.1.0/docs/Data-List.html#g:2

Upvotes: 2

Related Questions