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

You are looking for the Cartesian product of two sets.

This question has been asked in a thread on the OCaml mailing list. This answer is offered by Brian Hurt: For

module TypeSet = Set.Make(Type);;

Create, to represent the product:

module TypeType = struct
    type t = Type.t * Type.t;;
    let compare (x1, x2) (y1, y2) =
     let r = Type.compare x1 y1 in
     if r == 0 then
      Type.compare x2 y2
     else
      r
    ;;
end;;

module TypeTypeSet = Set.Make(TypeType);;

Then generate the product with:

let cartesian_product s1 s2 =
    let f x y t = TypeTypeSet.add (x, y) t in
    let g x t = TypeSet.fold (f x) s2 t in
    TypeSet.fold g s1 TypeTypeSet.empty
;;

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

Answer 3

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