An efficient membership-testing module, for types that can be mapped into
Int
s.
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
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
The Show
instance kind of sucks. It just shows the Integer
representation. A good show would probably show all the present hashes.
insert :: Hash a => a -> BitSet a -> BitSet aSource
O(setBit on Integer) Insert an item into the bit set.