bitset 1.1 → 1.2

raw patch · 9 files changed

+453/−262 lines, 9 filesdep +bitsetdep +criteriondep +deepseqdep ~QuickCheckdep ~basesetup-changednew-uploaderPVP ok

version bump matches the API change (PVP)

Dependencies added: bitset, criterion, deepseq, test-framework, test-framework-quickcheck2

Dependency ranges changed: QuickCheck, base

API changes (from Hackage documentation)

Files

• CHANGES +6/−8
• Data/BitSet.hs +0/−108
• LICENSE +13/−27
• Setup.hs +5/−1
• benchmarks/Benchmarks.hs +14/−0
• bitset.cabal +58/−21
• src/Data/BitSet.hs +184/−0
• tests/Properties.hs +0/−97
• tests/Tests.hs +173/−0

@@ -1,11 +1,9 @@--*- mode: outline -*-+bitset Changelog+================ -* 1.1-Added conversion to and from the underlying Integral value (thanks to Mathieu-Boespflug).+Here you can see the full list of changes between each bitset release. -* 1.0-Instead of a custom Hash typeclass, we now use Enum.  It's standard and it gives-us exactly what we need, so it's a win-win.+Version 1.2+----------- -Also, use unboxed tuples to represent the bitset.+Initial release, released on March 22th, 2013

@@ -1,108 +0,0 @@--- | A /bit set/ maintains a record of members from a type that can be mapped--- into (non-negative) @Int@s. The maximum number of elements that can be--- stored is @maxbound :: Int@. Supports insertion, deletion, size, and--- membership testing, and is completely pure (functional).------ To use this library, simply supply a `Enum' instance for your data type or--- have it derived. It is important that the values you intend to keep track--- of start from 0 and go up. A value for which @fromEnum x@ is @n@--- corresponds to bit location @n@ in an @Integer@, and thus requires that--- @Integer@ to have at least @n@ bits.------ The implementation is quite simple: we rely on the @Bits Integer@ instance--- from @Data.Bits@.  An advantage of this library over simply using that--- @Bits@ instance is the phantom type parameter used in the `BitSet' type.--- The interface we expose ensures client code will not typecheck if it--- confuses two bit sets intended to keep track of different types.-module Data.BitSet-    ( BitSet-    , empty-    , null-    , insert-    , fromList-    , delete-    , member-    , size-    , toIntegral-    , unsafeFromIntegral-    ) where--import Prelude hiding ( null )-import Data.Bits-import Data.Data---data BitSet a = BS {-# UNPACK #-} !Int {-# UNPACK #-} !Integer-                deriving (Eq, Ord, Data, Typeable)--instance (Enum a, Show a) => Show (BitSet a) where-    show (BS _ i :: BitSet a) = "fromList " ++ show (f 0 i)-        where f _ 0 = []-              f n x = if testBit x 0-                      then (toEnum n :: a) : f (n+1) (shiftR x 1)-                      else f (n+1) (shiftR x 1)---- | The empty bit set.-empty :: BitSet a---- | Is the bit set empty?-null :: BitSet a -> Bool---- | /O(setBit on Integer)/ Insert an item into the bit set.-insert :: Enum a => a -> BitSet a -> BitSet a---- | /O(n * setBit on Integer)/ Make a @BitSet@ from a list of items.-fromList :: Enum a => [a] -> BitSet a---- | /O(clearBit on Integer)/ Delete an item from the bit set.-delete :: Enum a => a -> BitSet a -> BitSet a---- | /O(testBit on Integer)/ Ask whether the item is in the bit set.-member :: Enum a => a -> BitSet a -> Bool---- | /O(1)/ The number of elements in the bit set.-size :: BitSet a -> Int---- | /O(1)/ Project a bit set to an integer.-toIntegral :: Integral b => BitSet a -> b---- | /O(n)/ Make a bit set of type @BitSet a@ from an integer. This is unsafe--- because it is not checked whether the bits set in the integer correspond to--- values of type @a@. This is only useful as a more efficient alternative to--- fromList.-unsafeFromIntegral :: Integral b => b -> BitSet a---- * Implementation--{-# INLINE empty #-}-empty = BS 0 0--{-# INLINE null #-}-null (BS n _) = n == 0--{-# INLINE insert #-}-insert x (BS count i) = BS count' (setBit i e)-    where count' = if testBit i e then count else count+1-          e      = fromEnum x--fromList xs = BS (length xs) (foldl (\i x -> setBit i (fromEnum x)) 0 xs)--{-# INLINE delete #-}-delete x (BS count i) = BS count' (clearBit i e)-    where count' = if testBit i e then count-1 else count-          e      = fromEnum x--{-# INLINE member #-}-member x (BS _ i) = testBit i (fromEnum x)--{-# INLINE size #-}-size (BS count _) = count--{-# INLINE toIntegral #-}-toIntegral (BS _ i) = fromIntegral i--{-# INLINE unsafeFromIntegral #-}-unsafeFromIntegral x = let i = fromIntegral x in BS (count i) i-    where count 0 = 0-          count z | z `mod` 2 == 0 = 1 + count (shiftR z 1)-                  | otherwise = count (shiftR z 1)

@@ -1,30 +1,16 @@-Copyright (c) 2009 Denis Bueno-All rights reserved.--Redistribution and use in source and binary forms, with or without-modification, are permitted provided that the following conditions are-met:--    * Redistributions of source code must retain the above copyright-      notice, this list of conditions and the following disclaimer.+Copyright (c) 2013 Sergei Lebedev -    * Redistributions in binary form must reproduce the above-      copyright notice, this list of conditions and the following-      disclaimer in the documentation and/or other materials provided-      with the distribution.+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and+associated documentation files (the "Software"), to deal in the Software without restriction,+including without limitation the rights to use, copy, modify, merge, publish, distribute,+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions: -    * Neither the name of Denis Bueno nor the names of other-      contributors may be used to endorse or promote products derived-      from this software without specific prior written permission.+The above copyright notice and this permission notice shall be included in all copies or substantial+portions of the Software. -THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS-"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT-LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR-A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT-OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,-SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT-LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,-DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY-THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT-(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES+OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

@@ -1,2 +1,6 @@-import Distribution.Simple+#!/usr/bin/env runhaskell++import Distribution.Simple (defaultMain)++main :: IO () main = defaultMain

@@ -0,0 +1,14 @@+module Main (main) where++import Criterion.Main (defaultMain, bench, nf)++import qualified Data.BitSet as BitSet++main :: IO ()+main = do+    defaultMain+        [ bench "fromList" (nf BitSet.fromList [1..n])+        ]+  where+    n :: Int+    n = 1024

@@ -1,24 +1,61 @@-Name:                bitset-Version:             1.1-Synopsis:            A functional data structure for efficient membership testing.+Name:                 bitset+Version:              1.2+Synopsis:             A compact functional set data structure. Description:-        A /bit set/ maintains a record of members from a type that can be mapped-        into (non-negative) @Int@s.  Supports insertion, deletion, size, and-        membership testing, and is completely pure (functional).-Category:            Data Structures-License:             BSD3-License-file:        LICENSE-Data-files:          CHANGES-Author:              Denis Bueno-Maintainer:          Denis Bueno <dbueno@gmail.com>-Stability:           provisional-Cabal-Version:       >= 1.2.3-Build-type:          Simple-Extra-source-files:  tests/Properties.hs+  A /bit set/ is a compact data structure, which maintains a set of members+  from a type that can be enumerated (i. e. has an `Enum' instance). Current+  implementations uses @Integer@ for as bit storage and provides most of the+  expected set operations: insertion, deletion, intersection, membership+  testing etc.+Category:             Data Structures+License:              MIT+License-file:         LICENSE+Data-files:           CHANGES+Author:               Sergei Lebedev <superbobry@gmail.com>+Maintainer:           Sergei Lebedev <superbobry@gmail.com>+Stability:            Alpha+Cabal-Version:        >= 1.12+Build-type:           Simple+Tested-with:          GHC >= 7.4.2  Library-  Exposed-modules:     Data.BitSet-  Build-depends:       base >= 4.0.0 && < 5, QuickCheck >= 2 && < 3-  Extensions:          ScopedTypeVariables, DeriveDataTypeable-  Ghc-options:         -Wall -O2-  Ghc-prof-options:    -prof -auto-all+  Hs-source-dirs:     src+  Ghc-options:        -Wall+  Default-language:   Haskell2010++  Build-depends:      base                    >= 4.5.1 && < 4.7+                    , deepseq                 == 1.3.*++  Exposed-modules:    Data.BitSet+++Test-suite bitset-tests+  Hs-source-dirs:     tests+  Ghc-options:        -Wall -O2 -fno-warn-orphans+  Default-language:   Haskell2010++  Type:               exitcode-stdio-1.0+  Main-is:            Tests.hs++  Build-depends:      base                       >= 4.5.1 && < 4.7+                    , QuickCheck                 == 2.5.*+                    , test-framework             == 0.6.*+                    , test-framework-quickcheck2 == 0.2.*+                    , bitset++Benchmark bitset-benchmarks+  Main-is: Benchmarks.hs+  Hs-source-dirs:     tests, benchmarks+  Default-language:   Haskell2010+  Type:               exitcode-stdio-1.0++  Build-depends:      base                        >= 4.5.1 || < 4.7+                    , deepseq                     == 1.3.*+                    , bitset++                    , criterion                   == 0.6.*+++Source-repository head+  Type:     git+  Location: https://github.com/superbobry/bitset

@@ -0,0 +1,184 @@+{-# LANGUAGE DeriveDataTypeable #-}++-- | A /bit set/ maintains a record of members from a type that can be+-- enumerated (i. e. has and `Enum' instance). The maximum number of elements+-- that can be stored is @maxBound :: Int@.+--+-- To use this library, define a `Enum' instance for your data type or+-- have it derived. It is important that the values you intend to store+-- in a bit set start from 0 and go up. A value for which @fromEnum x@ is @n@+-- corresponds to bit location @n@ in an @Integer@, and thus requires that+-- @Integer@ to have at least @n@ bits.+--+-- /Note/: The idea of using `Integer' as bit storage for a bit set was+-- borrowed from an unsupported `Data.BitSet' implementation by Denis Bueno.+module Data.BitSet+    (+    -- * Bit set type+      BitSet++    -- * Operators+    , (\\)++    -- * Query+    , null+    , size+    , member+    , notMember+    , isSubsetOf+    , isProperSubsetOf++    -- * Construction+    , empty+    , singleton+    , insert+    , delete++    -- * Combine+    , union+    , unions+    , difference+    , intersection++    -- * Conversion+    -- ** List+    , elems+    , toList+    , fromList+    -- ** Arbitraty integral type+    , toIntegral+    , unsafeFromIntegral+    ) where++import Prelude hiding (null)++import Data.Bits (Bits, (.|.), (.&.), complement,+                  testBit, setBit, clearBit, shiftR, popCount)+import Data.Data (Data, Typeable)+import Data.List (foldl')+import Data.Monoid (Monoid(..))++import Control.DeepSeq (NFData(..))++data BitSet a = BitSet {-# UNPACK #-} !Int !Integer+    deriving (Eq, Ord, Data, Typeable)++instance Enum a => Monoid (BitSet a) where+    mempty  = empty+    mappend = union+    mconcat = unions++instance (Enum a, Show a) => Show (BitSet a) where+    show bs = "fromList " ++ show (elems bs)++instance NFData (BitSet a) where+    rnf (BitSet count i) = rnf count `seq` rnf i `seq` ()+++-- | /O(1)/. Is the bit set empty?+null :: BitSet a -> Bool+null (BitSet _n i) = i == 0+{-# INLINE null #-}++-- | /O(1)/. The number of elements in the bit set.+size :: BitSet a -> Int+size (BitSet n _i) = n+{-# INLINE size #-}++-- | /O(testBit on Integer)/. Ask whether the item is in the bit set.+member :: Enum a => a -> BitSet a -> Bool+member x (BitSet _n i) = testBit i (fromEnum x)+{-# INLINE member #-}++-- | /O(testBit on Integer)/. Ask whether the item is in the bit set.+notMember :: Enum a => a -> BitSet a -> Bool+notMember bs = not . member bs+{-# INLINE notMember #-}++-- | /O(max(n, m))/.. Is this a subset? (@s1 isSubsetOf s2@) tells whether+-- @s1@ is a subset of @s2@.+isSubsetOf :: Enum a => BitSet a -> BitSet a -> Bool+isSubsetOf (BitSet n1 i1) (BitSet n2 i2) = n2 >= n1 && i2 .|. i1 == i2++-- | /O(max(n, m)/.. Is this a proper subset? (ie. a subset but not equal).+isProperSubsetOf :: Enum a => BitSet a -> BitSet a -> Bool+isProperSubsetOf bs1 bs2 = bs1 `isSubsetOf` bs2 && bs1 /= bs2++-- | The empty bit set.+empty :: BitSet a+empty = BitSet 0 0+{-# INLINE empty #-}++-- | O(setBit on Integer). Create a singleton set.+singleton :: Enum a => a -> BitSet a+singleton x = insert x empty+{-# INLINE singleton #-}++-- | /O(setBit on Integer)/. Insert an item into the bit set.+insert :: Enum a => a -> BitSet a -> BitSet a+insert x (BitSet n i) = BitSet n' $ setBit i e where+  n' = if testBit i e then n else n + 1+  e  = fromEnum x+{-# INLINE insert #-}++-- | /O(clearBit on Integer)/. Delete an item from the bit set.+delete :: Enum a => a -> BitSet a -> BitSet a+delete x (BitSet n i) = BitSet n' $ clearBit i e where+  n' = if testBit i e then n - 1 else n+  e  = fromEnum x+{-# INLINE delete #-}++-- | /O(max(m, n))/. The union of two bit sets.+union :: Enum a => BitSet a -> BitSet a -> BitSet a+union (BitSet _n1 i1) (BitSet _n2 i2) = BitSet (popCount i) i where+  i = i1 .|. i2+{-# INLINE union #-}++-- | /O(max(m, n))/. The union of a list of bit sets.+unions :: Enum a => [BitSet a] -> BitSet a+unions = foldl' union empty+{-# INLINE unions #-}++-- | /O(max(m, n))/. Difference of two bit sets.+difference :: Enum a => BitSet a -> BitSet a -> BitSet a+difference (BitSet _n1 i1) (BitSet _n2 i2) = BitSet (popCount i) i where+  i = i1 .&. complement i2++-- | /O(max(m, n))/. See `difference'.+(\\) :: Enum a => BitSet a -> BitSet a -> BitSet a+(\\) = difference++-- | /O(max(m, n))/. The intersection of two bit sets.+intersection :: Enum a => BitSet a -> BitSet a -> BitSet a+intersection (BitSet _n1 i1) (BitSet _n2 i2) = BitSet (popCount i) i where+  i = i1 .&. i2++-- | /O(n * shiftR on Integer)/. An alias to @toList@.+elems :: Enum a => BitSet a -> [a]+elems = toList++-- | /O(n * shiftR on Integer)/. Convert a bit set to a list of elements.+toList :: Enum a => BitSet a -> [a]+toList (BitSet _i n0) = go 0 n0 [] where+  go _i 0 acc = reverse acc+  go i n acc  = if n `testBit` 0+                then go (i + 1) (shiftR n 1) (toEnum i : acc)+                else go (i + 1) (shiftR n 1) acc++-- | /O(n * setBit on Integer)/. Make a bit set from a list of elements.+fromList :: Enum a => [a] -> BitSet a+fromList xs = BitSet (popCount i) i where+  i = foldl' (\b x -> setBit b (fromEnum x)) 0 xs++-- | /O(1)/. Project a bit set to an integral type.+toIntegral :: Integral b => BitSet a -> b+toIntegral (BitSet _n i) = fromIntegral i+{-# INLINE toIntegral #-}++-- | /O(n)/. Make a bit set from an integral. Unsafe because we don't+-- checked whether the bits set in a given value correspond to values+-- of type @a@. This is only useful as a more efficient alternative to+-- fromList.+unsafeFromIntegral :: Integral b => b -> BitSet a+unsafeFromIntegral x = let i = fromIntegral x in BitSet (popCount i) i+{-# INLINE unsafeFromIntegral #-}

@@ -1,97 +0,0 @@-module Properties where--import Control.Monad( liftM )-import Prelude hiding ( null )-import Data.BitSet-import Data.Foldable ( foldl' )-import Data.List ( nub )-import Test.QuickCheck-import System.IO--import qualified Data.List as List----main :: IO ()-main = do-  dbgMsg "prop_size: " >> quickCheckWith myargs prop_size-  dbgMsg "prop_size_insert: " >> quickCheckWith myargs prop_size_insert-  dbgMsg "prop_size_delete: " >> quickCheckWith myargs prop_size_delete-  dbgMsg "prop_insert: " >> quickCheckWith myargs prop_insert-  dbgMsg "prop_delete: " >> quickCheckWith myargs prop_delete-  dbgMsg "prop_insDelIdempotent: " >> quickCheckWith myargs prop_insDelIdempotent-  dbgMsg "prop_delDelIdempotent: " >> quickCheckWith myargs prop_delDelIdempotent-  dbgMsg "prop_insInsIdempotent: " >> quickCheckWith myargs prop_insInsIdempotent-  dbgMsg "prop_extensional: " >> quickCheckWith myargs prop_extensional-  dbgMsg "prop_fromList: " >> quickCheckWith myargs prop_fromList-  dbgMsg "prop_empty: " >> quickCheckWith myargs prop_empty-  dbgMsg "prop_integral: " >> quickCheckWith (myargs{ maxSize = 40 }) prop_integral--dbgMsg = hPutStr stderr--myargs = stdArgs{ maxSize = 64 }---- * Quickcheck properties--trivial test = classify test "trivial"--prop_size xs =-    trivial (List.null uxs) $-    length uxs == size (foldr insert empty uxs)-        where uxs = nub (map abs xs) :: [Int]--prop_size_insert x s =-    trivial (null s) $-    if xa `member` s then size s == size s'-    else size s + 1 == size s'-  where s' = insert xa s-        xa = abs x :: Int--prop_size_delete x s =-    trivial (null s) $-    if xa `member` s then size s - 1 == size s'-    else size s == size s'-  where s' = delete xa s-        xa = abs x :: Int--prop_insert x s = xa `member` insert xa s-    where xa = abs x :: Int--prop_delete x s = not $ xa `member` delete xa s-    where xa = abs x :: Int--prop_insDelIdempotent x s =-    classify (not (xa `member` s)) "passed guard" $-    not (xa `member` s) ==>-    s == (delete xa . insert xa) s-  where xa = abs x :: Int--prop_delDelIdempotent x s =-    classify (xa `member` s) "x in s" $-    classify (not (xa `member` s)) "x not in s" $-    delete xa s == (delete xa . delete xa $ s)-  where xa = abs x :: Int--prop_insInsIdempotent x s = insert xa s == (insert xa . insert xa) s-    where xa = abs x :: Int--prop_extensional xs = and $ map (`member` s) xsa-    where s   = foldr insert empty xsa-          xsa = map abs xs :: [Int]--prop_fromList xs = all (`member` s) xsa-    where s   = fromList xsa-          xsa = map abs xs :: [Int]--prop_empty x = not $ xa `member` empty-    where xa = abs x :: Int--prop_integral x s = trivial (null s) $ xa `member` reconstructed-  where reconstructed = unsafeFromIntegral (toIntegral xs)-        xa = abs x :: Int-        xs = xa `insert` s----instance (Arbitrary a, Enum a) => Arbitrary (BitSet a) where-    arbitrary = sized $ liftM fromList . vector

@@ -0,0 +1,173 @@+module Main (main) where++import Control.Applicative ((<$>))+import Data.List ((\\), intersect, union, nub, sort)+import Data.Monoid (mempty, mappend)+import Data.Word (Word16)++import Test.Framework (Test, defaultMain)+import Test.Framework.Providers.QuickCheck2 (testProperty)+import Test.QuickCheck (Property, Arbitrary(..), (==>), classify)++import Data.BitSet (BitSet)+import qualified Data.BitSet as BitSet++instance (Arbitrary a, Enum a) => Arbitrary (BitSet a) where+    arbitrary = BitSet.fromList <$> arbitrary+++propSize :: [Word16] -> Bool+propSize = go . nub where+  go xs = length xs == BitSet.size (BitSet.fromList xs)++propSizeAfterInsert :: Word16 -> BitSet Word16 -> Bool+propSizeAfterInsert x bs =+    BitSet.size (BitSet.insert x bs) == BitSet.size bs + diff+  where+    diff :: Int+    diff = if x `BitSet.member` bs then 0 else 1++propSizeAfterDelete :: Word16 -> BitSet Word16 -> Bool+propSizeAfterDelete x bs =+    BitSet.size (BitSet.delete x bs) == BitSet.size bs - diff+  where+    diff :: Int+    diff = if x `BitSet.member` bs then 1 else 0++propInsertMember :: Word16 -> BitSet Word16 -> Bool+propInsertMember x bs = x `BitSet.member` BitSet.insert x bs++propDeleteMember :: Word16 -> BitSet Word16 -> Bool+propDeleteMember x bs = x `BitSet.notMember` BitSet.delete x bs++propInsertDeleteIdempotent :: Word16 -> BitSet Word16 -> Property+propInsertDeleteIdempotent x bs =+    x `BitSet.notMember` bs ==> bs == BitSet.delete x (BitSet.insert x bs)++propDeleteIdempotent :: Word16 -> BitSet Word16 -> Property+propDeleteIdempotent x bs =+    classify (x `BitSet.member` bs) "x in bs" $+    classify (x `BitSet.notMember` bs) "x not in bs" $+    BitSet.delete x bs == BitSet.delete x (BitSet.delete x bs)++propInsertIdempotent :: Word16 -> BitSet Word16 -> Bool+propInsertIdempotent x bs =+    BitSet.insert x bs == BitSet.insert x (BitSet.insert x bs)++propToList :: [Word16] -> Bool+propToList xs = nub (sort xs) == BitSet.toList bs where+  bs :: BitSet Word16+  bs = BitSet.fromList xs++propFromList :: [Word16] -> Bool+propFromList xs = all (`BitSet.member` bs) xs where+  bs :: BitSet Word16+  bs = BitSet.fromList xs++propEmpty :: Word16 -> Bool+propEmpty x = x `BitSet.notMember` BitSet.empty++propUnsafeFromIntegral :: Word16 -> Bool+propUnsafeFromIntegral x =+    bs == BitSet.unsafeFromIntegral (BitSet.toIntegral bs :: Integer)+  where+    bs :: BitSet Word16+    bs = BitSet.singleton x++propUnions :: [Word16] -> Bool+propUnions xs = all (`BitSet.member` bs) xs where+  n      = length xs+  (l, r) = splitAt (n `div` 2) xs++  bs :: BitSet Word16+  bs = BitSet.unions $ map BitSet.fromList [l, r, l, r, l]++propIntersectionWithSelf :: [Word16] -> Bool+propIntersectionWithSelf xs = all (`BitSet.member` bs) xs+  where+    bs :: BitSet Word16+    bs = let bs0 = BitSet.fromList xs in bs0 `BitSet.intersection` bs0++propIntersection :: [Word16] -> Bool+propIntersection xs =+    all (`BitSet.member` bs) (l `intersect` r) &&+    all (`BitSet.notMember` bs) (dl `union` dr)+  where+    n      = length xs+    (l, r) = splitAt (n `div` 2) $ nub xs++    dl = l \\ r+    dr = r \\ l++    bs :: BitSet Word16+    bs = let bs1 = BitSet.fromList l+             bs2 = BitSet.fromList r+         in bs1 `BitSet.intersection` bs2++propDifferenceWithSelf :: [Word16] -> Bool+propDifferenceWithSelf xs = bs == BitSet.empty where+  bs :: BitSet Word16+  bs = let bs0 = BitSet.fromList xs in bs0 `BitSet.difference` bs0++propDifference :: [Word16] -> Property+propDifference xs = n > 0 ==>+                    all (`BitSet.member` bs) (l \\ r) &&+                    all (`BitSet.notMember` bs) (l `intersect` r)+  where+    n      = length xs+    (l, r) = splitAt (n `div` 2) $ nub xs++    bs :: BitSet Word16+    bs = let bs1 = BitSet.fromList l+             bs2 = BitSet.fromList r+         in bs1 `BitSet.difference` bs2++propMonoidLaws :: BitSet Word16 -> BitSet Word16 -> BitSet Word16 -> Bool+propMonoidLaws bs1 bs2 bs3 =+    bs1 `mappend` mempty == bs1 &&+    mempty `mappend` bs1 == bs1 &&+    mappend bs1 (bs2 `mappend` bs3) == (bs1 `mappend` bs2) `mappend` bs3++propIsSubsetOfSelf :: BitSet Word16 -> Bool+propIsSubsetOfSelf bs = bs `BitSet.isSubsetOf` bs &&+                        not (bs `BitSet.isProperSubsetOf` bs)++propIsSubsetOf :: [Word16] -> Bool+propIsSubsetOf xs =+    bs1 `BitSet.isSubsetOf` bs && bs2 `BitSet.isSubsetOf` bs+  where+    n = length xs++    bs :: BitSet Word16+    bs = BitSet.fromList xs++    bs1 :: BitSet Word16+    bs1 = BitSet.fromList $ take (n `div` 2) xs++    bs2 :: BitSet Word16+    bs2 = BitSet.fromList $ drop (n `div` 2) xs++main :: IO ()+main = defaultMain tests where+  tests :: [Test]+  tests = [ testProperty "size" propSize+          , testProperty "size after insert" propSizeAfterInsert+          , testProperty "size after delete" propSizeAfterDelete+          , testProperty "insert" propInsertMember+          , testProperty "delete" propDeleteMember+          , testProperty "insert and delete are idempotent" propInsertDeleteIdempotent+          , testProperty "delete is idempotent" propDeleteIdempotent+          , testProperty "insert is idempotent" propInsertIdempotent+          , testProperty "toList" propToList+          , testProperty "fromList" propFromList+          , testProperty "empty" propEmpty+          , testProperty "unsafe construction from integral" propUnsafeFromIntegral+          , testProperty "unions" propUnions+          , testProperty "intersection with self" propIntersectionWithSelf+          , testProperty "intersection" propIntersection+          , testProperty "difference with self" propDifferenceWithSelf+          , testProperty "difference" propDifference+          , testProperty "monoid laws" propMonoidLaws+          , testProperty "is subset of self" propIsSubsetOfSelf+          , testProperty "is subset of" propIsSubsetOf+          ]