OCaml: Combination of elements in Lists, functional reasoning

Question

I am back to coding in OCaml and I missed it so much. I missed it so much I completely lost my reasoning in this language and I hit a wall today.

What I want to do is the combination of elements between a set of n lists. I decomposed the problem by first attempting the combination of elements between two list of arbitrary sizes.

Assume we have to lists: l1 = [1;2;3] and l2 = [10,20].

What I want to do is obtain the following list:

 l_res = [10;20;20;40;30;60]

I know how to do this using loop structures, but I really want to solve this without them.

I tried the following:

       let f l1 l2 = 
         List.map (fun y -> (List.map (fun x -> x * y) l1) l2

But this does not seem to work. The type I get is f : int list -> int list -> int list list but I want f : int list -> int list -> int list

I tried already many different approaches I feel I am over complicating.

What did I miss?

Answer 1

What you are missing is that List.map f [a; b; c] gives [f a; f b; f c] so what you'll get from your function will be

f [a; b; c] [d; e] = [[ad; ae]; [bd; be]; [cd; ce]]

but you want

 f [a; b; c] [d; e] = [ad; ae; bd; be; cd; ce]

so you need to use an other iterator, i.e. :

 let f l1 l2 = 
   let res = List.fold_left (fun acc x ->
     List.fold_left (fun acc y -> (x * y) :: acc) acc l2
   ) [] l1 in
   List.rev res

or to flatten your result :

val concat : 'a list list -> 'a list

Concatenate a list of lists. The elements of the argument are all concatenated together (in the same order) to give the result. Not tail-recursive (length of the argument + length of the longest sub-list).

 val flatten : 'a list list -> 'a list

Same as concat. Not tail-recursive (length of the argument + length of the longest sub-list).