Re: [Caml-list] Cartesian product

["Damien Guichard" <alphablock@orange.fr>]

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