Data.BitSet

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.

Documentation

data BitSet a

Instances

Typeable1 BitSet

Eq (BitSet a)

Data a => Data (BitSet a)

Ord (BitSet a)

(Enum a, Show a) => Show (BitSet a)

empty :: BitSet a

The empty bit set.

null :: BitSet a -> Bool

Is the bit set empty?

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

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

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

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

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

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

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

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

size :: BitSet a -> Int

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