From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <bhurt@spnz.org>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by yquem.inria.fr (Postfix) with ESMTP id 5CB72BBAF
	for <caml-list@yquem.inria.fr>; Thu, 30 Jul 2009 22:22:45 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AhwCAF6dcUrYi40EmWdsb2JhbACBUphBAQEBAQEICwoHE7lVhBcF
X-IronPort-AV: E=Sophos;i="4.43,297,1246831200"; 
   d="scan'208";a="33850535"
Received: from mail-out4.nyct.net (HELO mail.nyct.net) ([216.139.141.4])
  by mail1-smtp-roc.national.inria.fr with ESMTP; 30 Jul 2009 22:22:44 +0200
Received: from sergyar.local (pool-96-246-6-198.nycmny.east.verizon.net [96.246.6.198])
	(authenticated bits=0)
	by mail.nyct.net (8.14.3/8.14.1) with ESMTP id n6UKMf7s061437
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
	Thu, 30 Jul 2009 16:22:43 -0400 (EDT)
	(envelope-from bhurt@spnz.org)
Date: Thu, 30 Jul 2009 16:22:35 -0400 (EDT)
From: Brian Hurt <bhurt@spnz.org>
X-X-Sender: bhurt@sergyar
To: Ligia Nistor <ligia.nicoleta@gmail.com>
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Cartesian product
In-Reply-To: <8401c38a0907301056x470687aah94b2b1295c6d1068@mail.gmail.com>
Message-ID: <alpine.DEB.2.00.0907301612210.19900@sergyar>
References: <8401c38a0907301056x470687aah94b2b1295c6d1068@mail.gmail.com>
User-Agent: Alpine 2.00 (DEB 1167 2008-08-23)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
X-Spam: no; 0.00; ocaml:01 sig:01 val:01 struct:01 struct:01 pervasives:01 wrote:01 wrote:01 caml-list:01 int:01 defined:02 implemented:02 preserve:03 module:03 module:03 



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