Version française
Home     About     Download     Resources     Contact us    
Browse thread
disjoint test in set.
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Christophe Raffalli <christophe.raffalli@u...>
Subject: disjoint test in set.

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