From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=3.0 required=5.0 tests=AWL,DNS_FROM_RFC_POST, HTML_MESSAGE,SPF_NEUTRAL 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 5F556BBAF for ; Thu, 30 Jul 2009 23:54:57 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AuYBAJOzcUrRVdzdkWdsb2JhbACCJTCWfz8BAQEBCQkMBxGnIIEfkDQBAwIEhBMF X-IronPort-AV: E=Sophos;i="4.43,297,1246831200"; d="scan'208";a="33852671" Received: from mail-fx0-f221.google.com ([209.85.220.221]) by mail1-smtp-roc.national.inria.fr with ESMTP; 30 Jul 2009 23:54:57 +0200 Received: by fxm21 with SMTP id 21so961165fxm.27 for ; Thu, 30 Jul 2009 14:54:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:cc:content-type; bh=0McB6+u1KX6xKMBUdh3KhwcOWAkemA50mpLxZkLqJDQ=; b=g06Y9a2QiOKXL3pdLM9QchM1sIbGpl3MBed6GbXzau9Dnh61EX/mQdNDj1YFmWyrYE AIWG0GEScC3CjeCNZ2FNnGmFYJmNSjli5hEmGdvhYsIZps5UUjcJHA+3M8Czo1kSaZIh DHKdrAdPBd0nI3X2z9xosAqWrZwyocag2ZdDI= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=VqtMQW3UWD9yvrg07VuY/FVv41JI/9okF6bkZCnaFX/W1HcZrqMvoHXAThsBmsq06U eFZPIPieyIFSHBhuePVY4np7CMW5Y/ug02GmJYw00ZKTtNInV12QCvK24tzkusCw29q7 uMWXArEF1pLXZ6Adhk7KsTo5r3gJopRGlXpUM= MIME-Version: 1.0 Received: by 10.239.129.208 with SMTP id 16mr183922hbg.131.1248990895816; Thu, 30 Jul 2009 14:54:55 -0700 (PDT) In-Reply-To: References: <8401c38a0907301056x470687aah94b2b1295c6d1068@mail.gmail.com> Date: Thu, 30 Jul 2009 22:54:55 +0100 Message-ID: <8401c38a0907301454q1c60ac2frf8b0ab9027a6475d@mail.gmail.com> Subject: Re: [Caml-list] Cartesian product From: Ligia Nistor To: Brian Hurt Cc: caml-list@yquem.inria.fr Content-Type: multipart/alternative; boundary=001485f44e94ac3f55046ff35a8b X-Spam: no; 0.00; ocaml:01 sig:01 val:01 struct:01 struct:01 pervasives:01 ocaml:01 sig:01 val:01 pervasives:01 2009:98 2009:98 wrote:01 wrote:01 caml-list:01 --001485f44e94ac3f55046ff35a8b Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit 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 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 > > --001485f44e94ac3f55046ff35a8b Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable 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 a= n 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 set= s
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 typ= e t*t is not the same as the type t. =A0But it's still not that hard. S= ay you have:

module Type : sig
=A0 =A0 =A0 =A0type t;;
=A0 =A0 =A0 =A0val compare : t -> t -> int;;
end =3D struct
=A0 =A0 =A0 =A0...
end;;

module TypeSet =3D Set.Make(Type);;

Then you could do:

module TypeType =3D struct
=A0 =A0 =A0 =A0type t =3D Type.t * Type.t;;
=A0 =A0 =A0 =A0let compare (x1, x2) (y1, y2) =3D
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0let r =3D Type.compare x1 y1 in
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0if r =3D=3D 0 then
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0Type.compare x2 y2
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0else
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0r
=A0 =A0 =A0 =A0;;
end;;

module TypeTypeSet =3D Set.Make(TypeType);;

As a side note, you could simply use Pervasives.compare there instead of th= e code I wrote, but that wouldn't necessarily preserve the ordering giv= en 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 =3D
=A0 =A0 =A0 =A0let f x y t =3D TypeTypeSet.add (x, y) t in
=A0 =A0 =A0 =A0let g x t =3D TypeSet.fold (f x) s2 t in
=A0 =A0 =A0 =A0TypeSet.fold g s1 TypeTypeSet.empty
;;

Hope this helps.

Brian


--001485f44e94ac3f55046ff35a8b--