Cartesian product

Cartesian product

[Ligia Nistor]

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

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.

Thanks,

Ligia

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

Re: [Caml-list] Cartesian product

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Not that I know of.  But you can use this general implementation.  It assumes 
you have Enum (from Batteries, and ExtLib before).  The (~~) prefix operator 
is "Obj.magic".


Peng


  (* makes the cross product of the given array of enumerations *)
  let crossproductM enums initcount = 
    let numenums = Array.length enums in
    let clean = Array.map clone enums in
    let initstate = enums in

    let rec cpmk cur curcount =
      let reseti i = cur.(i) <- clone clean.(i) in

      let tick () = 
        let rec tick_aux place = 
          if place >= numenums then ()
          else
            let ple = cur.(place) in
            ignore (get ple);
            if is_empty ple then (
              reseti place;
              tick_aux (place + 1)
            )
        in tick_aux 0; decr curcount in

      let get () = Array.init numenums (fun i -> Option.get (peek cur.(i))) in

      let nx () = match !curcount with
        | 0 -> raise No_more_elements
        | 1 -> decr curcount; get ()
        | x -> assert (x >= 0); let ans = get () in tick (); ans in

      let ct () = !curcount in

      let cl () = cpmk (Array.init numenums (fun i -> clone cur.(i))) 
(ref !curcount) in
        make nx ct cl
    in
    ( if initcount == 0 then empty ()
      else cpmk initstate (ref initcount) )
 

  let crossproduct enums = 
    let copy = Array.copy enums in
    let initcount = Array.fold_left (fun acc e -> count e * acc) 1 copy in
    crossproductM copy initcount


  let cross2 (t1:'a t) (t2:'b t) : ('a * 'b) t = 
    ~~(crossproduct [|~~t1; ~~t2|])

  let cross3 (t1:'a t) (t2:'b t) (t3:'c t) : ('a * 'b * 'c) t = 
    ~~(crossproduct [|~~t1; ~~t2; ~~t3|])



On Thursday 30 July 2009 01:56:50 pm 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.
>
> Thanks,
>
> Ligia
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFKceqXfIRcEFL/JewRAnM5AKC3dnxh9uWl7kdRBKW68koS1f3dhACgxau4
ubBf3OXzaxkMeU3Cb848lJY=
=XZ4Q
-----END PGP SIGNATURE-----

Re: [Caml-list] Cartesian product

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I really should provide a bit more context.  It's a general implementation for 
crossing [Enum.t]s.  Eg.

  let a = List.enum [1;2;3;4]
  let b = List.enum ['a'; 'b'; 'c']

  let c = cross2 a b

yields [(1,'a'); (2,'a'); (3,'a'); (4,'a'); (1,'b'); ..]


There are implementations for converting Set to Enum in the same library(s) 
that provide Enum.

Peng

On Thursday 30 July 2009 02:46:41 pm Peng Zang wrote:
> Not that I know of.  But you can use this general implementation.  It
> assumes you have Enum (from Batteries, and ExtLib before).  The (~~) prefix
> operator is "Obj.magic".
>
>
> Peng
>
>
>   (* makes the cross product of the given array of enumerations *)
>   let crossproductM enums initcount =
>     let numenums = Array.length enums in
>     let clean = Array.map clone enums in
>     let initstate = enums in
>
>     let rec cpmk cur curcount =
>       let reseti i = cur.(i) <- clone clean.(i) in
>
>       let tick () =
>         let rec tick_aux place =
>           if place >= numenums then ()
>           else
>             let ple = cur.(place) in
>             ignore (get ple);
>             if is_empty ple then (
>               reseti place;
>               tick_aux (place + 1)
>             )
>         in tick_aux 0; decr curcount in
>
>       let get () = Array.init numenums (fun i -> Option.get (peek cur.(i)))
> in
>
>       let nx () = match !curcount with
>
>         | 0 -> raise No_more_elements
>         | 1 -> decr curcount; get ()
>         | x -> assert (x >= 0); let ans = get () in tick (); ans in
>
>       let ct () = !curcount in
>
>       let cl () = cpmk (Array.init numenums (fun i -> clone cur.(i)))
> (ref !curcount) in
>         make nx ct cl
>     in
>     ( if initcount == 0 then empty ()
>       else cpmk initstate (ref initcount) )
>
>
>   let crossproduct enums =
>     let copy = Array.copy enums in
>     let initcount = Array.fold_left (fun acc e -> count e * acc) 1 copy in
>     crossproductM copy initcount
>
>
>   let cross2 (t1:'a t) (t2:'b t) : ('a * 'b) t =
>     ~~(crossproduct [|~~t1; ~~t2|])
>
>   let cross3 (t1:'a t) (t2:'b t) (t3:'c t) : ('a * 'b * 'c) t =
>     ~~(crossproduct [|~~t1; ~~t2; ~~t3|])
>
> On Thursday 30 July 2009 01:56:50 pm 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.
> >
> > Thanks,
> >
> > Ligia
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFKcew1fIRcEFL/JewRArLiAKCYGbfEHY5igi0IlM6f71tNAL2OqACeMUPR
qR8nC+F5QNRgaX19gSVtMsA=
=8JeB
-----END PGP SIGNATURE-----

Re: [Caml-list] Cartesian product

[Erick Matsen]

Hello Ligia---


The following code takes cartesian products of lists:


let listListPrepend x ll = List.map (fun l -> x :: l) ll

let rec cartesianProduct = function
  | aList :: listList ->
      let prev = cartesianProduct listList in
      List.flatten (
	List.map (fun x -> listListPrepend x prev) aList)
  | [] -> [[]]


and could be easily adapted to the case of sets.


Erick


On Thu, Jul 30, 2009 at 11:53 AM, Peng Zang<peng.zang@gmail.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> I really should provide a bit more context.  It's a general implementation for
> crossing [Enum.t]s.  Eg.
>
>  let a = List.enum [1;2;3;4]
>  let b = List.enum ['a'; 'b'; 'c']
>
>  let c = cross2 a b
>
> yields [(1,'a'); (2,'a'); (3,'a'); (4,'a'); (1,'b'); ..]
>
>
> There are implementations for converting Set to Enum in the same library(s)
> that provide Enum.
>
> Peng
>
> On Thursday 30 July 2009 02:46:41 pm Peng Zang wrote:
>> Not that I know of.  But you can use this general implementation.  It
>> assumes you have Enum (from Batteries, and ExtLib before).  The (~~) prefix
>> operator is "Obj.magic".
>>
>>
>> Peng
>>
>>
>>   (* makes the cross product of the given array of enumerations *)
>>   let crossproductM enums initcount =
>>     let numenums = Array.length enums in
>>     let clean = Array.map clone enums in
>>     let initstate = enums in
>>
>>     let rec cpmk cur curcount =
>>       let reseti i = cur.(i) <- clone clean.(i) in
>>
>>       let tick () =
>>         let rec tick_aux place =
>>           if place >= numenums then ()
>>           else
>>             let ple = cur.(place) in
>>             ignore (get ple);
>>             if is_empty ple then (
>>               reseti place;
>>               tick_aux (place + 1)
>>             )
>>         in tick_aux 0; decr curcount in
>>
>>       let get () = Array.init numenums (fun i -> Option.get (peek cur.(i)))
>> in
>>
>>       let nx () = match !curcount with
>>
>>         | 0 -> raise No_more_elements
>>         | 1 -> decr curcount; get ()
>>         | x -> assert (x >= 0); let ans = get () in tick (); ans in
>>
>>       let ct () = !curcount in
>>
>>       let cl () = cpmk (Array.init numenums (fun i -> clone cur.(i)))
>> (ref !curcount) in
>>         make nx ct cl
>>     in
>>     ( if initcount == 0 then empty ()
>>       else cpmk initstate (ref initcount) )
>>
>>
>>   let crossproduct enums =
>>     let copy = Array.copy enums in
>>     let initcount = Array.fold_left (fun acc e -> count e * acc) 1 copy in
>>     crossproductM copy initcount
>>
>>
>>   let cross2 (t1:'a t) (t2:'b t) : ('a * 'b) t =
>>     ~~(crossproduct [|~~t1; ~~t2|])
>>
>>   let cross3 (t1:'a t) (t2:'b t) (t3:'c t) : ('a * 'b * 'c) t =
>>     ~~(crossproduct [|~~t1; ~~t2; ~~t3|])
>>
>> On Thursday 30 July 2009 01:56:50 pm 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.
>> >
>> > Thanks,
>> >
>> > Ligia
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.7 (GNU/Linux)
>
> iD8DBQFKcew1fIRcEFL/JewRArLiAKCYGbfEHY5igi0IlM6f71tNAL2OqACeMUPR
> qR8nC+F5QNRgaX19gSVtMsA=
> =8JeB
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Cartesian product

[Brian Hurt]

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

Re: [Caml-list] Cartesian product

[Ligia Nistor]

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

Re: Cartesian product

[Michael Ekstrand]

Ligia Nistor wrote:
> 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.

That would be possible (use a type of Type.t list), but the resulting
set types would have a static typing hole: you would not be guaranteed
that all elements would have the same length.

Another way to do it would be to have a Product functor, like so:

module Product = functor (T1: Set.ORDERED_TYPE) -> functor (T2:
Set.ORDERED_TYPE) -> struct
    type t = T1.t * T2.t
    let compare (a1,b1) (a2,b2) =
        let r = T1.compare a1 a2 in
          if r = 0 then T2.compare b1 b2
          else r
end

Then you can create a 2-ary product set type:

module Set2 = Set.Make(Product(Type)(Type))

and build further sets by constructing products of products:

module Set3 = Set.Make(Product(Product(Type))(Type)))

That would allow you to construct arbitrarily high-dimensional product
set types that still remain type-safe.

- Michael

Re: [Caml-list] Cartesian product

[Damien Guichard]

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


Hi Ligia Nistor,

Supposing you want to implement the Cartesian product of 2 sets, and supposing you implement sets as (balanced) sorted binary trees, here is how i would do that :

implement a functor that, given x:A and a set B, maps B to a new set of pairs (x,y), y:B  
this functor transforms each item of A into a new balanced tree
if you map this functor to A the result is a tree of trees
supposing you can merge all these trees you then get the cartesian product
howewer you don't actually need the tree of trees, all you need is the merged result
thus, instead of doing (3) you apply the (1) functor as f argument of the following flatten_map function :

  type 'a set =
    tree option
  and tree =
    {left: 'a set; item: 'a; right: 'a set}

  let rec flatten_map f p = function
    | None -> p
    | Some n ->
        union
        (flatten_map f p n.left)
        (flatten_map f (f n.item) n.right)

  let flatten_map f = flatten_map f None

It seems to me that my solution gives you the cartesian product as an ordered (balanced) binary tree set in optimal time.

- damien





Damien Guichard
2009-07-30



En réponse au message
de : Ligia Nistor
du : 2009-07-30 19:56:57
À : caml-list@yquem.inria.fr
CC : 
Sujet : [Caml-list] Cartesian product

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.

Thanks,

Ligia

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