Cartesian product

Ligia Nistor
 Peng Zang
 Brian Hurt
 Damien Guichard
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Damien Guichard <alphablock@o...> 
Subject:  Re: [Camllist] Cartesian product 
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 20090730 En réponse au message de : Ligia Nistor du : 20090730 19:56:57 À : camllist@yquem.inria.fr CC : Sujet : [Camllist] 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