A bit set maintains a record of members from a type that can be mapped
Ints. The maximum number of elements that can be
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
corresponds to bit location
n in an
Integer, and thus requires that
Integer to have at least
The implementation is quite simple: we rely on the
Bits Integer instance
Data.Bits. An advantage of this library over simply using that
Bits instance is the phantom type parameter used in the
The interface we expose ensures client code will not typecheck if it
confuses two bit sets intended to keep track of different types.
- data BitSet a
- empty :: BitSet a
- null :: BitSet a -> Bool
- insert :: Enum a => a -> BitSet a -> BitSet a
- fromList :: Enum a => [a] -> BitSet a
- delete :: Enum a => a -> BitSet a -> BitSet a
- member :: Enum a => a -> BitSet a -> Bool
- size :: BitSet a -> Int
- toIntegral :: Integral b => BitSet a -> b
- unsafeFromIntegral :: Integral b => b -> BitSet a
O(setBit on Integer) Insert an item into the bit set.
O(n * setBit on Integer) Make a
BitSet from a list of items.
O(clearBit on Integer) Delete an item from the bit set.
O(testBit on Integer) Ask whether the item is in the bit set.