A bit set maintains a record of members from a type that can be mapped
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.
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
n corresponds to bit location
n in an
Integer, and thus
Integer to have at least
n bits. Don't shoot yourself in
the foot by
hashing to big
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.
Map a value to an non-negative
For the implementation to give reliable results, it must be that if
== hash y,
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
y of type
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
Show instance kind of sucks. It just shows the size paired with
Integer representation. A good show would probably show all
the present hashes.
O(setBit on Integer) Insert an item into the bit set.
O(clearBit on Integer) Delete an item from the bit set.
O(testBit on Integer) Ask whether the item is in the bit set.