Data.BitSet

A bit set maintains a record of members from a type that can be mapped into (non-negative) Ints. Supports insertion, deletion, size, and membership testing, and is completely pure (functional).

To use this library, simply supply a Hash instance for your data type. (See the Hash class for the relevant laws your instance must obey.) Each operation requires at most one call to hash. It is important that the values you intend to keep track of start from 0 and go up. A value which hashes to n corresponds to bit location n in an Integer, and thus requires that Integer to have at least n bits. Don't shoot yourself in the foot by hashing to big Ints.

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

class Hash a where

Map a value to an non-negative Int.

For the implementation to give reliable results, it must be that if hash x == hash y, x and y are equivalent under the relevant relation used in the client code. (We don't depend on equality, but the client code will certainly want to use the above sort of inference.)

In fact, if the relevant relation is ==, the following quickcheck test should pass, for arbitrary x and y of type a:

prop_hash x y =
     if hash x == hash y then x == y
     else x /= y
     && if x == y then hash x == hash y
        else hash x /= hash y

Methods

hash :: a -> Int

Instances

Hash Int

Hash Integer

data BitSet a

The Show instance kind of sucks. It just shows the size paired with the internal Integer representation. A good show would probably show all the present hashes.

Instances

Eq (BitSet a)

Show (BitSet a)

empty :: BitSet a

The empty bit set.

null :: BitSet a -> Bool

Is the bit set empty?

insert :: Hash a => a -> BitSet a -> BitSet a

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

delete :: Hash a => a -> BitSet a -> BitSet a

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

member :: Hash 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.