HyperLogLog

SigHash Key

Promote a SipKey to the type level for use as part of a HyperLogLog type.

Initialize a new counter:

>>> runHyperLogLog (mempty :: DefaultHyperLogLog 3) == V.fromList [0,0,0,0,0,0,0,0]
True

Please note how you specify a counter size with the n invocation. Sizes of up to 16 are valid, with 7 being a likely good minimum for decent accuracy.

Let's count a list of unique items and get the latest estimate:

>>> size (foldr insert mempty [1..10] :: DefaultHyperLogLog 4)
Approximate {_confidence = 0.9972, _lo = 2, _estimate = 9, _hi = 17}

Note how insert can be used to add new observations to the approximate counter.

The s type parameter configures the SipKey that is passed to the hash function when inserting a new value. Note that if cryptographic security is a primary consideration, it is recommended that you create HyperLogLog values using generateHyperLogLog so that the SipKey is randomly generated using system entropy. In contrast, the HyperLogLog data constructor and the mempty method allow constructing HyperLogLog values with fixed SipKeys, which can result in exponentially inaccurate estimates if exploited by an adversary. (See https://eprint.iacr.org/2021/1139.)

Generate a fresh HyperLogLog value using a randomly generated SipKey:

>>> generateHyperLogLog $ \(m :: HyperLogLog s 3) -> pure (runHyperLogLog m == V.fromList [0,0,0,0,0,0,0,0])
True

The SipKey is generated using system entropy, so if cryptographic security is a primary consideration, use this function to create a HyperLogLog value instead of manually building one (e.g., by using the HyperLogLog data constructor or by using mempty).

Approximate size of our set

Insert a value that has already been hashed by whatever user defined hash function you want.

If the two types p and q reify the same configuration, and if the two types r and s reify the same SipKey, then we can coerce between HyperLogLog r p and HyperLogLog s q. We do this by building a hole in the nominal role for the configuration parameter.