transpose of a list of lists

Question

I'm trying to make a recursive function to get the transpose of a list of lists, n x p to p x n. But i'm unable to do so. I've been able to make a function to transpose a 3 x n list of lists to an n x 3 one:

let rec drop1 list=
    [(match (List.nth list 0) with [] -> [] | a::b -> b);
     (match (List.nth list 1) with [] -> [] | a::b -> b);
     (match (List.nth list 2) with [] -> [] | a::b -> b);]

let rec transpose list=
    if List.length (List.nth list 0) == 0 then []
    else [(match (List.nth list 0) with [] -> 0 | a::b -> a);
          (match (List.nth list 1) with [] -> 0 | a::b -> a);
          (match (List.nth list 2) with [] -> 0 | a::b -> a)]
         :: transpose (drop1 list)

But I'm not able to generalize it. I'm surely thinking in the wrong direction. Is this generalizable? Is there a better solution? Please help.

Hinson

Answer 1

let rec transpose list = match list with
| []             -> []
| []   :: xss    -> transpose xss
| (x::xs) :: xss ->
    (x :: List.map List.hd xss) :: transpose (xs :: List.map List.tl xss)

Taking advantage of syntax changes since answer first posted:

let rec transpose list = match list with
| []             -> []
| []      :: xss -> transpose xss
| (x::xs) :: xss ->
    List.(
      (x :: map hd xss) :: transpose (xs :: map tl xss)
    )

Mondrian

+1, Wow! I was not aware of List.map function. The manual says its not tail-recursive. What effect can that have if I use this in a bigger code? – Hinson

@lalli: For very large lists it can cause a stack overflow. In that case, you should use List.rev_map instead and then go through the lists at the end and reverse them. Note however that my definition of transpose is also not tail recursive (neither is yours). – Mondrian

You should not worry about tail-recursivity at first; try to have a simple and clear implementation. Using a "transpose" function on ('a list list) with very big lists is probably a very bad idea anyway. If you have lots of data, an other data structure (eg. a matrix indexed by (int * int), which has a constant-time transpose function) is probably more appropriate. – Limiting

Note that this fails with inputs such as [[0]; []] – Infighting

Answer 2

I know this is an old question, but I recently had to solve this as part of an exercise I was doing, and I came across @sepp2k's solution, but I couldn't understand how it worked, so I tried to arrive at it by myself.

This is essentially the same algorithm, but a little bit more terse, as it does not destructure the list of lists. I thought I would post it here in case anyone else is searching, and might find this way of expressing it useful:

let rec transpose = function
   | [] 
   | [] :: _ -> []
   | rows    -> 
       List.map List.hd rows :: transpose (List.map List.tl rows)

Trincomalee

Answer 3

Assuming the matrix is rectangular (otherwise Invalid_argument "map2" will be raised):

let transpose m =
  if m = [] then [] else
  List.(fold_right (map2 cons) m @@ map (fun _ -> []) (hd m))

Note that map (fun _ -> []) (hd m) just creates a list of empty lists, of length equal to the number of columns in m.

So a clearer representation of this code would be:

let transpose m =
  if m = [] then [] else
  let open List in
  let empty_rows = map (fun _ -> []) (hd m) in
  fold_right (map2 cons) m empty_rows

Hildebrand