Re: [Caml-list] Cartesian product

[Brian Hurt <bhurt@spnz.org>]

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