OCaml: Permutation of every value in two sets? (how to translate this from Java)

Question

I have two sets, returned by Set.Make(t). I would like to generate every possible combination of the values in the two. How can I do this?

This works to generate some pairs, but not all:

List.combine (IntSet.elements odp) (IntSet.elements ftw)

This would do it in Java:

for (int i : ktr) {
     for (int m : mnx) {
       System.out.println(i + ", " + m);
     }
}

Answer 1

Combining @David Crawshaw's solution (which is tail-recursive) with @newacct's (which is fully generic):

let cartesian_product xs ys =
  List.fold_left (fun acc x -> 
    List.fold_left (fun acc y -> 
      (x,y) :: acc) 
      acc ys) 
    [] xs

let product = 
  cartesian_product (IntSet.elements odb) (IntSet.elements ftw)

This will reverse the natural ordering. It can be regained by applying List.rev to the result (List.rev is also tail-recursive).

Answer 2

If xs and ys are two lists, then their cartesian product (returning a list of pairs) can be computed as follows:

List.concat (List.map (fun x -> List.map (fun y -> (x, y))
                                         ys)
                      xs)

In this case your xs and ys are IntSet.elements odp and IntSet.elements ftw