Thanks for the reply. This is how I thought of doing it, but in the module TypeType, type t should be a list of types( the list has to be ref, so that it can change its length). This way, you can do the cartesian product of an arbitrary number of sets, not only of 2.

Ligia

On Thu, Jul 30, 2009 at 9:22 PM, Brian Hurt <bhurt@spnz.org> wrote:


On Thu, 30 Jul 2009, Ligia Nistor wrote:

Hi,

Is there an already implemented way of doing the Cartesian product of 2 sets
in OCaml? My sets are of type Set.Make(Types), where Types is a module I
have defined.

The biggest problem with implementing the cartesian product is that the type t*t is not the same as the type t.  But it's still not that hard. Say you have:

module Type : sig
       type t;;
       val compare : t -> t -> int;;
end = struct
       ...
end;;

module TypeSet = Set.Make(Type);;

Then you could do:

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

As a side note, you could simply use Pervasives.compare there instead of the code I wrote, but that wouldn't necessarily preserve the ordering given by Type.compare.

Once you have the set module for the cartesian products, you can use nested folds to create one:

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
;;

Hope this helps.

Brian