Data.BitSet

An efficient membership-testing module, for types that can be mapped into Ints.

The implementation is quite simple: we rely on the Bits Integer instance from Data.Bits for the three main operations. An advantage of this library is the phantom parameter used in the BitSet type. Since there is no exported way to construct a value of type BitSet directly, the interface we expose ensures client code will not typecheck if it confuses two bit sets intended to keep track of different types.

It is important that the values you intend to keep track of start from 0 and go up. Each Int mapped to be hash corresponds to that bit location in an Integer, and thus requires that Integer to have at least that many bits. Don't shoot yourself in the foot.

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 your equivalence relation is ==, the following quickcheck test should pass, for arbitrary x and y:

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 Integer representation. A good show would probably show all the present hashes.

Instances

Eq (BitSet a)

Show (BitSet a)

Arbitrary (BitSet a)

empty :: BitSet a

The empty bit set.

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.