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).

Answer 2

Some Core-flavoured answers:

open Core.Std

let f1 l1 l2 =
  List.map (List.cartesian_product l1 l2) ~f:(fun (x, y) -> x * y)

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

let f4 l1 l2 =
  let open List.Monad_infix in
  l1 >>= fun x ->
  l2 >>| fun y ->
  x * y

The last answer explicitly (and arguably the two other answers implicitly) makes use of the list monad, which this is a textbook use case of. I couldn't find the list monad in Batteries, which is possibly not so surprising as it's much less widely used than (say) the option or result monads.