3

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[0].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 maps:

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

    const transposedMatrix = arrMatrix[0].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.

If possible, in addition to the algorithm/code, please give me some explanation and resources to learn more about it.

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

  const transpose = matrix =>
    matrix[0].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],    ->  [[1],   ->   [[],
  [2, 2, 2],          [2, 2],         [2],         [],
  [3, 3, 3]]          [3, 3]]         [3]]         []]

Then the base case gets reached, the matrix is empty (matrix[0].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 at 14:47
  • There is still a map - you are cheating :D – bob Aug 13 at 14:49
  • @Alireza yeah, that ASCII art took some time ;) hope it helps ... – Jonas Wilms Aug 13 at 14:53
  • @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 at 14:59
  • @alireza sure. I'll also add a non mutating version – Jonas Wilms Aug 13 at 15:03
3
const transpose = matrix => {
  const row = (x) => x >= matrix[0].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[0].length ? [] : [col(col)(x, 0), ...row(row)(col)(x + 1)],
    col => (x, y) => y >= matrix.length ? [] : [matrix[y][x], ...col(col)(x, y + 1)]
 );
  • For good reasons :) – Jonas Wilms Aug 13 at 15:58
  • 2
    I see that U combinator :) – user633183 Aug 14 at 18:08
  • @user633183 to be honest I failed doing that with a real U combinator function ... – Jonas Wilms Aug 14 at 18:19
  • 1
    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. – user633183 Aug 14 at 18:47
  • 1
    Ah right, should be fixed... Yeah, but U introduces another variable. – Jonas Wilms Aug 14 at 18:54
3

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[0]
const tail = xs => xs.slice(1)

const transpose = (m) => head(m).length
  ? [m.map(head), ...transpose(m.map(tail))]
  : []

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[0].length
  ? [m.map(xs => xs[0]), ...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[0]
const tail = xs => xs.slice(1)
const empty = xs => xs.length == 0

const transpose = (m) => m.some(empty)
  ? []
  : [m.map(head), ...transpose(m.map(tail))]

(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], [4], [5, 6, 7]]. The first recursive call will be [[2,3], [], [6,7]] where head([]) is undefined -- m.every(...) avoids the pitfall. – user633183 Aug 19 at 15:39
  • 1
    @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 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. – user633183 Aug 19 at 16:27
  • 1
    Yes, recursion is a hell of (a hell of (a hell of (a hell of a ... drug))...) ! – Scott Sauyet Aug 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 at 16:37
1

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[0].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 at 14:37
1

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[0])
    : 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) =>
        lift2(append)(r, safeHead(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
    ( mapReduce(safeHead, lift2(append))
    , 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 ] ]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.