Data.BitSet
Description
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
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 yThe 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.
insert :: Hash a => a -> BitSet a -> BitSet aSource
O(setBit on Integer) Insert an item into the bit set.
delete :: Hash a => a -> BitSet a -> BitSet aSource
O(clearBit on Integer) Delete an item from the bit set.