OCaml function help involving parsing a list of lists

Question

I am trying to create an OCaml function rv that will go through a list of lists and reorganize the elements into another list of lists such that the first list is comprised of the first element of each of the original lists, the second list is comprised of the second element of each list etc.

An example:
[["a"; "b"; "c"]; ["d"; "e"; "f"]] becomes [["a"; "d"]; ["b"; "e"]; ["c"; "f"]]

I already have a function gather that will take a list of lists and extract the elements of a certain index from each list. So basically using the previous example I could say gather(list, 1) and get ["b"; "e"] back. I need a way to go through List.length times and use gather for each element index.

The reason this is causing me so much trouble is because of the limitations applied (yes, this is for school). I am not allowed to use loops or local/global variables. I am also not allowed to use 'let' within the body of a function. Is there another way to recursively use gather for each element index? Is there another function I should make that will recursively use gather and then re-use that function in rv? If so, how would you go about that?

Answer 1

To overcome the restriction against loops, use recursive functions.

The restriction about using let is a little silly. You can work around it by passing arguments to a function, to some extent, writing (function x -> e) v instead of let x = v in e. But think of it as a hint that you're supposed to leverage functions such as List.map and List.fold_left and so on.

Generally speaking, lists are not arrays; they're not meant to be accessed with the index of an element. Sure, you can do it, but it's cumbersome and inefficient. The natural way to access a list is to use pattern matching or the List.hd and List.tl functions to split out the first element and the remainder of the list, or to use functions such as List.map to traverse the whole list.

For example, if all you needed was the first element of each list, then you could use

List.map List.hd lists

And List.map List.tl lists gives the remainder of each list. This suggests a recursive method: the head of the result is List.map List.hd lists, and the tail of the result is the transposition of List.map List.tl lists.

let rec transpose lists =
  List.map List.hd lists :: transpose (List.map List.tl lists)

Now, obviously, we need to terminate at some point. Assuming all lists have the same length, we need to stop when the lists are empty, which we can test by looking at the first list. I will leave this as an exercise.

To understand what this code is doing, I recommend typing it in the Ocaml toplevel, using the #trace directive and watching the operation on a few examples. For this, it will help if you make the transpose function monomorphic.

# let rec tranpose (lists : string list list) = …;;
val transpose : string list list -> string list list = <fun>
# #trace transpose;;
transpose is now traced.
# transpose [["a"; "b"; "c"]; ["d"; "e"; "f"]];;
transpose <-- [["a"; "b"; "c"]; ["d"; "e"; "f"]]
transpose <-- [["b"; "c"]; ["e"; "f"]]
transpose <-- [["c"]; ["f"]]
transpose <-- [[]; []]
transpose --> []
transpose --> [["c"; "f"]]
transpose --> [["b"; "e"]; ["c"; "f"]]
transpose --> [["a"; "d"]; ["b"; "e"]; ["c"; "f"]]
- : string list list = [["a"; "d"]; ["b"; "e"]; ["c"; "f"]]