From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 3005CBBBB for ; Fri, 31 Mar 2006 13:56:30 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id k2VBuTAF026549 for ; Fri, 31 Mar 2006 13:56:29 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA22759 for ; Fri, 31 Mar 2006 13:56:29 +0200 (MET DST) Received: from justus.rz.uni-saarland.de (justus.rz.uni-saarland.de [134.96.7.31]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k2VBuSd4018734 for ; Fri, 31 Mar 2006 13:56:28 +0200 Received: from uni-sb.de (uni-sb.de [134.96.7.230]) by justus.rz.uni-saarland.de (8.12.11.20060308/8.12.10) with ESMTP id k2VBuQpZ23448820 for ; Fri, 31 Mar 2006 13:56:26 +0200 (CEST) Received: from mail.cs.uni-sb.de (mail.cs.uni-sb.de [134.96.254.200]) by uni-sb.de (8.13.6/2006032300) with ESMTP id k2VBuQg0023481 for ; Fri, 31 Mar 2006 13:56:26 +0200 (CEST) Received: from mail.st.cs.uni-sb.de (goscinny.cs.uni-sb.de [134.96.235.32]) by mail.cs.uni-sb.de (8.13.6/2006032300) with ESMTP id k2VBuPK2021824 for ; Fri, 31 Mar 2006 13:56:25 +0200 (CEST) Received: from [134.96.235.101] (jonagold.cs.uni-sb.de [134.96.235.101]) by mail.st.cs.uni-sb.de (Postfix) with ESMTP id B9E6E1BD87 for ; Fri, 31 Mar 2006 13:56:25 +0200 (CEST) Mime-Version: 1.0 (Apple Message framework v623) Content-Transfer-Encoding: 7bit Message-Id: <4120ea8c70420ccd2f670bd9e4433527@cs.uni-sb.de> Content-Type: text/plain; charset=US-ASCII; format=flowed To: Caml List From: Christian Lindig Subject: efficient binary relations? Date: Fri, 31 Mar 2006 13:56:24 +0200 X-Mailer: Apple Mail (2.623) X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.5.1 (justus.rz.uni-saarland.de [134.96.7.31]); Fri, 31 Mar 2006 13:56:26 +0200 (CEST) X-AntiVirus: checked by AntiVir Milter (version: 1.1.1-9; AVE: 6.34.0.14; VDF: 6.34.0.124; host: AntiVir2) X-Miltered: at concorde with ID 442D18ED.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 442D18EC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; lindig:01 lindig:01 binary:01 binary:01 ocaml:01 bitvectors:01 high-level:01 computed:01 intersection:01 bitvectors:01 uni-sb:01 uni-sb:01 imperative:01 data:02 data:02 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 I am looking for an efficient representation of binary relations in OCaml. I have used bitvectors in the past but would like to use a more high-level and less imperative data structure. The most important operation is the following. For a binary relation R over \X x \Y compute for a set X the set X' = { y | (x,y) in R for all x in X}. In other words, X' is the set of y that are common to all x in X. Likewise, Y' must be computed. This operation requires to compute the intersection of sets and was the main reason I chose bitvectors. If you know about a suitable data structure I would glad to hear about it. -- Christian -- http://www.st.cs.uni-sb.de/~lindig/