CODEWITHSUNDEEP
listfunctional-programmingocaml
measuretheory
measuretheory

Reputation: 117

Function to flatten `('a list * b' list) list` to `'a list* 'b list` in OCaml

I need a function in OCaml that will take a type of ('a list * b' list) list and make of it
'a list * b' list. I have tried with the built in functions List.flatten and List.concat but they do not work, they require a type of 'c list list. Can someone help me?

Upvotes: 1

Views: 1070

Answers (4)

Çağdaş Bozman
Çağdaş Bozman

Reputation: 2540

You have to use the functions List.split and List.flatten:

 let my_function l =
   let (fst_list, snd_list) = List.split l in
   List.flatten fst_list, List.flatten snd_list ;;

First the split function will generate and 'a list list and a 'b list list, then you just have to flatten them.

Upvotes: 2

lambda.xy.x
lambda.xy.x

Reputation: 4998

Unfortunately there is no map for tuples and you need to decompose - e.g. using using split and flatten:

let splcat x = match List.split x with | (a,b) -> (List.flatten a, List.flatten b) ;;

That's how it looks on the commandline:

utop # splcat [([1;2],["a"]); ([3],["uvw";"xyz"]) ] ;;
- : int list * bytes list = ([1; 2; 3], ["a"; "uvw"; "xyz"])

Upvotes: 1

Reimer Behrends
Reimer Behrends

Reputation: 8720

The following should work:

let split2 l = (List.map fst l, List.map snd l)
let flatten2' (l1, l2) = (List.flatten l1, List.flatten l2)
let flatten2 l = flatten2' (split2 l)

Here, split2 will turn a ('a list * 'b list) list into a ('a list list * 'b list list) (fst and snd return the first and second component of a pair, respectively) and flatten2' will individually flatten the two components. And flatten2 will finally do what you require. You can also pack this into a single function, but I think this is easier to understand.

Note that neither List.map nor List.flatten is tail-recursive; if you need tail-recursive versions, there are other libraries that have them, or you can build them from the standard library using rev_xxx functions or write them from scratch.

Upvotes: 0

alifirat
alifirat

Reputation: 2927

You can do it using the function fold_left like this :

You start with two empty lists working as accumulators. For every sub-lists in your the input list, you add the elements into the respective accumulator (elements of the first sub-list in the first accumulator and same thing for the second sub-list).

# let flatten l =
  let (l1,l2) =
    List.fold_left (fun (l1,l2) (x,y) ->
        (x :: l1, y :: l2)) ([], []) l in
  List.rev (List.flatten l1), List.rev (List.flatten l2);;
        val flatten : ('a list * 'b list) list -> 'a list * 'b list = <fun>
#

Upvotes: 1

Related Questions