Add `disjoint` for Data.Set
authorVíctor López Juan <victor@lopezjuan.com>
Fri, 19 Jan 2018 21:19:00 +0000 (22:19 +0100)
committerVíctor López Juan <victor@lopezjuan.com>
Sun, 21 Jan 2018 16:19:58 +0000 (17:19 +0100)
This is added mostly for consistency with `IntSet.disjoint`.
Performance also improves compared to the corresponding
`(null.).intersection` implementation.

Benchmark set-benchmarks: RUNNING...
[...]
benchmarking disjoint:false
time                 69.64 ns   (68.87 ns .. 70.69 ns)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 69.39 ns   (68.31 ns .. 70.86 ns)
std dev              3.819 ns   (2.979 ns .. 4.857 ns)
variance introduced by outliers: 75% (severely inflated)

benchmarking disjoint:true
time                 611.5 μs   (606.6 μs .. 618.0 μs)
                     0.999 R²   (0.997 R² .. 1.000 R²)
mean                 620.2 μs   (608.3 μs .. 664.9 μs)
std dev              68.26 μs   (14.09 μs .. 140.9 μs)
variance introduced by outliers: 79% (severely inflated)

benchmarking null.intersection:false
time                 234.9 μs   (227.3 μs .. 241.2 μs)
                     0.995 R²   (0.993 R² .. 0.998 R²)
mean                 218.8 μs   (214.7 μs .. 224.3 μs)
std dev              14.66 μs   (11.51 μs .. 18.56 μs)
variance introduced by outliers: 62% (severely inflated)

benchmarking null.intersection:true
time                 732.3 μs   (701.0 μs .. 767.7 μs)
                     0.989 R²   (0.983 R² .. 0.996 R²)
mean                 726.3 μs   (711.1 μs .. 742.9 μs)
std dev              50.46 μs   (38.81 μs .. 63.17 μs)
variance introduced by outliers: 58% (severely inflated)

Data/Set.hs
Data/Set/Internal.hs
benchmarks/Set.hs
tests/set-properties.hs

index f330a1e..c0396b0 100644 (file)
@@ -74,6 +74,7 @@ module Data.Set (
             , lookupGE
             , isSubsetOf
             , isProperSubsetOf
+            , disjoint
 
             -- * Construction
             , empty
index c000392..816d9c0 100644 (file)
@@ -141,6 +141,7 @@ module Data.Set.Internal (
             , lookupGE
             , isSubsetOf
             , isProperSubsetOf
+            , disjoint
 
             -- * Construction
             , empty
@@ -622,6 +623,27 @@ isSubsetOfX (Bin _ x l r) t
 {-# INLINABLE isSubsetOfX #-}
 #endif
 
+{--------------------------------------------------------------------
+  Disjoint
+--------------------------------------------------------------------}
+-- | /O(n+m)/. Check whether two sets are disjoint (i.e. their intersection
+--   is empty).
+--
+-- > disjoint (fromList [2,4,6])   (fromList [1,3])     == True
+-- > disjoint (fromList [2,4,6,8]) (fromList [2,3,5,7]) == False
+-- > disjoint (fromList [1,2])     (fromList [1,2,3,4]) == False
+-- > disjoint (fromList [])        (fromList [])        == True
+--
+-- @since 0.5.11
+
+disjoint :: Ord a => Set a -> Set a -> Bool
+disjoint Tip _ = True
+disjoint _ Tip = True
+disjoint (Bin _ x l r) t
+  -- Analogous implementation to `subsetOfX`
+  = not found && disjoint l lt && disjoint r gt
+  where
+    (lt,found,gt) = splitMember x t
 
 {--------------------------------------------------------------------
   Minimal, Maximal
index 67ef835..d0086b9 100644 (file)
@@ -33,6 +33,10 @@ main = do
         , bench "fromList-desc" $ whnf S.fromList (reverse elems)
         , bench "fromAscList" $ whnf S.fromAscList elems
         , bench "fromDistinctAscList" $ whnf S.fromDistinctAscList elems
+        , bench "disjoint:false" $ whnf (S.disjoint s) s_even
+        , bench "disjoint:true" $ whnf (S.disjoint s_odd) s_even
+        , bench "null.intersection:false" $ whnf (S.null. S.intersection s) s_even
+        , bench "null.intersection:true" $ whnf (S.null. S.intersection s_odd) s_even
         ]
   where
     elems = [1..2^12]
index 46ae416..e235c0a 100644 (file)
@@ -67,6 +67,7 @@ main = defaultMain [ testCase "lookupLT" test_lookupLT
                    , testProperty "prop_isProperSubsetOf2" prop_isProperSubsetOf2
                    , testProperty "prop_isSubsetOf" prop_isSubsetOf
                    , testProperty "prop_isSubsetOf2" prop_isSubsetOf2
+                   , testProperty "prop_disjoint" prop_disjoint
                    , testProperty "prop_size" prop_size
                    , testProperty "prop_lookupMax" prop_lookupMax
                    , testProperty "prop_lookupMin" prop_lookupMin
@@ -426,6 +427,9 @@ prop_Int :: [Int] -> [Int] -> Bool
 prop_Int xs ys = toAscList (intersection (fromList xs) (fromList ys))
                  == List.sort (nub ((List.intersect) (xs)  (ys)))
 
+prop_disjoint :: Set Int -> Set Int -> Bool
+prop_disjoint a b = a `disjoint` b == null (a `intersection` b)
+
 {--------------------------------------------------------------------
   Lists
 --------------------------------------------------------------------}