An efficient membership-testing module, for types that can be mapped into
The implementation is quite simple: we rely on the
Bits Integer instance
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
Integer, and thus requires that
Integer to have at least that many
bits. Don't shoot yourself in the foot.
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 your equivalence relation is
==, the following quickcheck
test should pass, for arbitrary
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
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.