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 :
 
  1. implement a functor that, given x:A and a set B, maps B to a new set of pairs (x,y), y:B  
  2. this functor transforms each item of A into a new balanced tree
  3. if you map this functor to A the result is a tree of trees
  4. supposing you can merge all these trees you then get the cartesian product
  5. howewer you don't actually need the tree of trees, all you need is the merged result
  6. 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