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