# How to transpose an m*n matrix using recursion?

I'm trying to transpose a matrix using recursion. Now, I know that under normal circumstances this isn't a good idea and a nested loop/nested map, or a similar approach is superior, but I need to learn this for educational purposes.

To show that I did my homework, here is the nested loop approach:

``````const arrMatrix = [
[3, 6, 7, 34],
[6, 3, 5, 2],
[2, 6, 8, 3]
];

const transposedMatrix = []

for (let i = 0; i < arrMatrix.length; i++) {
const tempCol = [];
for (let j = 0; j < arrMatrix.length; j++) {
tempCol.push(arrMatrix[j][i]);
}
transposedMatrix.push(tempCol);
}

console.log(transposedMatrix);``````

Here's another approach using nested `map`s:

``````    const arrMatrix = [
[3, 6, 7, 34],
[6, 3, 5, 2],
[2, 6, 8, 3]
];

const transposedMatrix = arrMatrix.map((_, i) =>
arrMatrix.map((_, j) => arrMatrix[j][i])
);

console.log(transposedMatrix);``````

Here are some resources that I went through but didn't manage to come up with a solution using them.

``````  const map = ([head, ...tail], mapper) => tail.length ? [mapper(head), ...map(tail, mapper)] : [mapper(head)];

const transpose = matrix =>
matrix.length
? [map(matrix, row => row.shift()), ...transpose(matrix)]
:  [];
``````

How it works:

From a given matrix, we always take out the first column (`matrix.map(row => row.shift())`, then we continue recursively:

`````` [[1, 1, 1],    ->   [[1, 1],    ->  [,   ->   [[],
[2, 2, 2],          [2, 2],         ,         [],
[3, 3, 3]]          [3, 3]]         ]         []]
``````

Then the base case gets reached, the matrix is empty (`matrix.length` is 0 = falsy) and an empty array gets returned. Now at every step, the column taken out gets added to that array, and thus it's a row now:

``````   [[1, 2, 3],    <-    [[1, 2, 3],    <-  [[1, 2, 3]]   <-  []
[1, 2, 3],            [1, 2, 3]]
[1, 2, 3]]
``````

Note: This destroys the original array.

• This looks really good, but can you please give me some context? Explanations? Links maybe? – Alireza Aug 13 '19 at 14:47
• There is still a `map` - you are cheating :D – bob Aug 13 '19 at 14:49
• @JonasWilms thanks that was great. Already accepted as the correct answer. I was wondering if you could also add a variation where no `map` is used for completeness' sake. – Alireza Aug 13 '19 at 14:59
• @alireza sure. I'll also add a non mutating version – Jonas Wilms Aug 13 '19 at 15:03
``````const transpose = matrix => {
const row = (x) => x >= matrix.length ? [] : [col(x, 0), ...row(x + 1)];
const col = (x, y) => y >= matrix.length ? [] : [matrix[y][x], ...col(x, y + 1)];
return row(0);
};
``````

That version does not mutate the original array. You can take that even a step further, than it is purely functional, but thats a bit overkill:

`````` const transpose = matrix => (
(row, col) => row(row)(col)(0)
)(
row => col => (x) => x >= matrix.length ? [] : [col(col)(x, 0), ...row(row)(col)(x + 1)],
col => (x, y) => y >= matrix.length ? [] : [matrix[y][x], ...col(col)(x, y + 1)]
);
``````
• I see that U combinator :) – Thank you Aug 14 '19 at 18:08
• @user633183 to be honest I failed doing that with a real U combinator function ... – Jonas Wilms Aug 14 '19 at 18:19
• All `x(x)...` can be replaced with `U(x)` where `U = f => f (f)` - on a side note, this `transpose` drops the last column. Ie, using `arrMatrix` in the OP, the output is `[[3,6,2],[6,3,6],[7,5,8]]`; missing `...[34,2,3]]`. This is because `matrix.length` is used as a constant, so `3` is used for the exit condition in both rows and cols. – Thank you Aug 14 '19 at 18:47
• Ah right, should be fixed... Yeah, but U introduces another variable. – Jonas Wilms Aug 14 '19 at 18:54

This is very similar to hitmands' solution, and would likely be less performant, but I think it's slightly cleaner to avoid working with column indices:

``````const head = xs => xs
const tail = xs => xs.slice(1)

const transpose = (m) => head(m).length
: []

const matrix = [
[3, 6, 7, 34],
[6, 3, 5, 2],
[2, 6, 8, 3]
]

console .log (
transpose (matrix)
)``````

This version transposes the first column into a row (via `.map(head)`) and then recurs on the remaining matrix (via `.map(tail)`), bottoming out when the first row is empty. You can inline those helper functions if you choose, so that it looks like this:

``````const transpose = (m) => m.length
? [m.map(xs => xs), ...transpose(m.map(xs => xs.slice(1)))]
: []
``````

..but I wouldn't recommend it. The first version seems more readable, and `head` and `tail` are easily reusable.

## Update

user633183 suggests an alternative escape condition. It's a good question whether or not it's a better result for ill-formed data, but it's certainly a useful possible variant:

``````const head = xs => xs
const tail = xs => xs.slice(1)
const empty = xs => xs.length == 0

const transpose = (m) => m.some(empty)
? []
``````

(This could also be done with `m.every(nonempty)` by reversing the consequent and alternative in the conditional expression, but I think it would be slightly harder to read.)

• So much cleaner than the `transpose` I wrote two years ago. One thing I'd change now is the exit condition `head(m).length` to `m.every(x => x.length)` -- `head(m).length` is vulnerable when we imagine input like `[[1,2,3], , [5, 6, 7]]`. The first recursive call will be `[[2,3], [], [6,7]]` where `head([])` is `undefined` -- `m.every(...)` avoids the pitfall. – Thank you Aug 19 '19 at 15:39
• @user633183: Yes, I've written several versions of `transpose` over the years, but this is the first time I tried explicitly to do it via recursion. Unsurprisingly, this leads to more readable code. I've updated to include your suggestion as an alternative, but it's an interesting question whether the result should be `[[1, 4, 5]]` as you propose or the current `[[1,4, 5], [2, null, 6], [3, null, 7]]` with this ill-formed (?) data. – Scott Sauyet Aug 19 '19 at 16:04
• It's a great answer, Scott. I should've said so first. Recursion is a helluva drug ^_^ I think `nulls` are OK; it's sparse arrays with `undefined` we have to watch out for, ie `[ 1, 2, , 4 ]`. I had an idea to use `Maybe` for this and added my answer to this thread. Later today I'll see if I can tweak it to better handle sparse arrays. – Thank you Aug 19 '19 at 16:27
• Yes, recursion is a hell of (a hell of (a hell of (a hell of a ... drug))...) ! – Scott Sauyet Aug 19 '19 at 16:33
• Unless I'm trying to ensure a total function (as your excellent answer does), I try to pretend that sparse arrays do not exist and figure those who supply one simply deserve what they get! :-) – Scott Sauyet Aug 19 '19 at 16:37

I would write it like this, assuming that all the rows inside the matrix have the same length:

1. check if there still are rows to process
2. create a row from each colum at the given index
3. increment column index by 1
4. call transpose with the new index

``````const transpose = (m, ci = 0) => ci >= m.length
? []
: [m.map(r => r[ci]), ...transpose(m, ci + 1)]
;

const matrix = [
[3, 6, 7, 34],
[6, 3, 5, 2],
[2, 6, 8, 3]
];

console.log(
transpose(matrix),
);``````

• Nice and concise explanation, bro :) – Alireza Aug 19 '19 at 14:37

I had an idea to write `transpose` using the `Maybe` monad. I'll start using functional operations and then refactor to clean up the code -

Dependencies -

``````const { Just, Nothing } =
require("data.maybe")

const safeHead = (a = []) =>
a.length
? Just(a)
: Nothing()

const tail = (a = []) =>
a.slice(1)
``````

Without refactors -

``````const column = (matrix = []) =>
matrix.reduce
( (r, x) =>
r.chain(a => safeHead(x).map(x => [ ...a, x ]))
, Just([])
)

const transpose = (matrix = []) =>
column(matrix)
.map(col =>
[ col, ...transpose(matrix.map(tail)) ]
)
.getOrElse([])
``````

Refactor `column` using generic `append` and `lift2` -

``````const append = (a = [], x) =>
[ ...a, x ]

const lift2 = f =>
(mx, my) =>
mx.chain(x => my.map(y => f(x, y)))

const column = (matrix = []) =>
matrix.reduce
( (r, x) =>
, Just([])
)

const transpose = (matrix = []) =>
column(matrix)
.map(col =>
[ col, ...transpose(matrix.map(tail)) ]
)
.getOrElse([])
``````

Refactor `column` again using generic transducer `mapReduce` -

``````const mapReduce = (map, reduce) =>
(r, x) => reduce(r, map(x))

const column = (matrix = []) =>
matrix.reduce
, Just([])
)

const transpose = (matrix = []) =>
column(matrix)
.map(col =>
[ col, ...transpose(matrix.map(tail)) ]
)
.getOrElse([])
``````

`transpose` stays the same in each refactoring step. It produces the following outputs -

``````transpose
( [ [ 1, 2, 3, 4 ]
, [ 5, 6, 7, 8 ]
, [ 9, 10, 11, 12 ]
]
)
// [ [ 1, 5, 9 ]
// , [ 2, 6, 10 ]
// , [ 3, 7, 11 ]
// , [ 4, 8, 12 ]
// ]

transpose
( [ [ 1, 2, 3, 4 ]
, [ 5 ]
, [ 9, 10, 11, 12 ]
]
)
// [ [ 1, 5, 9 ] ]
``````