Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
efficient binary relations?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-03-31 (11:56)
From: Christian Lindig <lindig@c...>
Subject: efficient binary relations?
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