* disjoint test in set.
@ 2008-01-24 22:38 Christophe Raffalli
0 siblings, 0 replies; only message in thread
From: Christophe Raffalli @ 2008-01-24 22:38 UTC (permalink / raw)
To: caml-list
Dear list member,
I think a function testing if two sets are disjoint is really simple,
more efficient than building the intersection, and missing in the
standard library ?
I may be wrong ?
Here it is if someone wants to copy it in set.ml :
let rec disjoint t1 t2 =
match (t1, t2) with
(Empty, _) | (_, Empty) ->
true
| (Node (l1, v1, r1, _), Node (l2, v2, r2, _)) ->
let c = Ord.compare v1 v2 in
if c = 0 then
false
else if c < 0 then
disjoint (Node (l1, v1, Empty, 0)) l2 && disjoint r1 t2
else
disjoint l1 (Node (l2, v2, Empty, 0)) && disjoint t1 r2
+ the necessary lignes in signatures ...
Then, a small question:
Can we make disjoint (and subset) do no allocation in the heap (That is
remove Node (l1, v1, Empty, 0) and the symmetric
from the code without loss of performance ? (checking v1 and l1
separately is surely a bad idea) ...
Best Regards,
Christophe
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2008-01-24 22:34 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-01-24 22:38 disjoint test in set Christophe Raffalli
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).