Re: [Caml-list] Cartesian product

[Ligia Nistor <ligia.nicoleta@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1763 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 2415 bytes --]