bitset-1.1: A functional data structure for efficient membership testing.



A bit set maintains a record of members from a type that can be mapped into (non-negative) Ints. 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.



data BitSet a Source


Typeable1 BitSet 
Eq (BitSet a) 
Data a => Data (BitSet a) 
Ord (BitSet a) 
(Enum a, Show a) => Show (BitSet a) 

empty :: BitSet aSource

The empty bit set.

null :: BitSet a -> BoolSource

Is the bit set empty?

insert :: Enum a => a -> BitSet a -> BitSet aSource

O(setBit on Integer) Insert an item into the bit set.

fromList :: Enum a => [a] -> BitSet aSource

O(n * setBit on Integer) Make a BitSet from a list of items.

delete :: Enum a => a -> BitSet a -> BitSet aSource

O(clearBit on Integer) Delete an item from the bit set.

member :: Enum a => a -> BitSet a -> BoolSource

O(testBit on Integer) Ask whether the item is in the bit set.

size :: BitSet a -> IntSource

O(1) The number of elements in the bit set.

toIntegral :: Integral b => BitSet a -> bSource

O(1) Project a bit set to an integer.

unsafeFromIntegral :: Integral b => b -> BitSet aSource

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.