/usr/share/doc/libghc-bloomfilter-doc/html/Data-BloomFilter-Mutable.html is in libghc-bloomfilter-doc 2.0.1.0-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Data.BloomFilter.Mutable</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script src="file:///usr/share/javascript/mathjax/MathJax.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-BloomFilter-Mutable.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-BloomFilter-Mutable.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">bloomfilter-2.0.1.0: Pure and impure Bloom Filter implementations.</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Copyright</th><td>Bryan O'Sullivan</td></tr><tr><th>License</th><td>BSD3</td></tr><tr><th>Maintainer</th><td>Bryan O'Sullivan <bos@serpentine.com></td></tr><tr><th>Stability</th><td>unstable</td></tr><tr><th>Portability</th><td>portable</td></tr><tr><th>Safe Haskell</th><td>None</td></tr><tr><th>Language</th><td>Haskell98</td></tr></table><p class="caption">Data.BloomFilter.Mutable</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Overview</a><ul><li><a href="#g:2">Ease of use</a></li><li><a href="#g:3">Performance</a></li></ul></li><li><a href="#g:4">Types</a></li><li><a href="#g:5">Mutable Bloom filters</a><ul><li><a href="#g:6">Creation</a></li><li><a href="#g:7">Accessors</a></li><li><a href="#g:8">Mutation</a></li></ul></li><li><a href="#g:9">The underlying representation</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>A fast, space efficient Bloom filter implementation. A Bloom
filter is a set-like data structure that provides a probabilistic
membership test.</p><ul><li>Queries do not give false negatives. When an element is added to
a filter, a subsequent membership test will definitely return
<code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#v:True">True</a></code>.</li><li>False positives <em>are</em> possible. If an element has not been added
to a filter, a membership test <em>may</em> nevertheless indicate that
the element is present.</li></ul><p>This module provides low-level control. For an easier to use
interface, see the <a href="Data-BloomFilter-Easy.html">Data.BloomFilter.Easy</a> module.</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">type</span> <a href="#t:Hash">Hash</a> = <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Word.html#t:Word32">Word32</a></li><li class="src short"><span class="keyword">data</span> <a href="#t:MBloom">MBloom</a> s a</li><li class="src short"><a href="#v:new">new</a> :: (a -> [<a href="Data-BloomFilter-Mutable.html#t:Hash">Hash</a>]) -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Control-Monad-ST.html#t:ST">ST</a> s (<a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a)</li><li class="src short"><a href="#v:length">length</a> :: <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:elem">elem</a> :: a -> <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Control-Monad-ST.html#t:ST">ST</a> s <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:insert">insert</a> :: <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Control-Monad-ST.html#t:ST">ST</a> s ()</li><li class="src short"><a href="#v:bitArray">bitArray</a> :: <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/array-0.5.1.1/Data-Array-ST.html#t:STUArray">STUArray</a> s <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> <a href="Data-BloomFilter-Mutable.html#t:Hash">Hash</a></li></ul></div><div id="interface"><h1 id="g:1">Overview</h1><div class="doc"><p>Each of the functions for creating Bloom filters accepts two parameters:</p><ul><li>The number of bits that should be used for the filter. Note that
a filter is fixed in size; it cannot be resized after creation.</li><li>A function that accepts a value, and should return a fixed-size
list of hashes of that value. To keep the false positive rate
low, the hashes computes should, as far as possible, be
independent.</li></ul><p>By choosing these parameters with care, it is possible to tune for
a particular false positive rate. The <code>suggestSizing</code> function in
the <a href="Data-BloomFilter-Easy.html">Data.BloomFilter.Easy</a> module calculates useful estimates for
these parameters.</p></div><h2 id="g:2">Ease of use</h2><div class="doc"><p>This module provides both mutable interfaces for creating and
querying a Bloom filter. It is most useful as a low-level way to
manage a Bloom filter with a custom set of characteristics.</p></div><h2 id="g:3">Performance</h2><div class="doc"><p>The implementation has been carefully tuned for high performance
and low space consumption.</p><p>For efficiency, the number of bits requested when creating a Bloom
filter is rounded up to the nearest power of two. This lets the
implementation use bitwise operations internally, instead of much
more expensive multiplication, division, and modulus operations.</p></div><h1 id="g:4">Types</h1><div class="top"><p class="src"><span class="keyword">type</span> <a id="t:Hash" class="def">Hash</a> = <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Word.html#t:Word32">Word32</a> <a href="src/Data-BloomFilter-Mutable-Internal.html#Hash" class="link">Source</a> <a href="#t:Hash" class="selflink">#</a></p><div class="doc"><p>A hash value is 32 bits wide. This limits the maximum size of a
filter to about four billion elements, or 512 megabytes of memory.</p></div></div><div class="top"><p class="src"><span class="keyword">data</span> <a id="t:MBloom" class="def">MBloom</a> s a <a href="src/Data-BloomFilter-Mutable-Internal.html#MBloom" class="link">Source</a> <a href="#t:MBloom" class="selflink">#</a></p><div class="doc"><p>A mutable Bloom filter, for use within the <code>ST</code> monad.</p></div><div class="subs instances"><p id="control.i:MBloom" class="caption collapser" onclick="toggleSection('i:MBloom')">Instances</p><div id="section.i:MBloom" class="show"><table><tr><td class="src clearfix"><span class="inst-left"><span id="control.i:id:MBloom:Show:1" class="instance expander" onclick="toggleSection('i:id:MBloom:Show:1')"></span> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:Show">Show</a> (<a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a)</span> <a href="src/Data-BloomFilter-Mutable-Internal.html#line-36" class="link">Source</a> <a href="#t:MBloom" class="selflink">#</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div id="section.i:id:MBloom:Show:1" class="inst-details hide"><div class="subs methods"><p class="caption">Methods</p><p class="src"><a href="#v:showsPrec">showsPrec</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:ShowS">ShowS</a> <a href="#v:showsPrec" class="selflink">#</a></p><p class="src"><a href="#v:show">show</a> :: <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-String.html#t:String">String</a> <a href="#v:show" class="selflink">#</a></p><p class="src"><a href="#v:showList">showList</a> :: [<a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a] -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:ShowS">ShowS</a> <a href="#v:showList" class="selflink">#</a></p></div></div></td></tr></table></div></div></div><h1 id="g:5">Mutable Bloom filters</h1><h2 id="g:6">Creation</h2><div class="top"><p class="src"><a id="v:new" class="def">new</a> <a href="src/Data-BloomFilter-Mutable.html#new" class="link">Source</a> <a href="#v:new" class="selflink">#</a></p><div class="subs arguments"><p class="caption">Arguments</p><table><tr><td class="src">:: (a -> [<a href="Data-BloomFilter-Mutable.html#t:Hash">Hash</a>])</td><td class="doc"><p>family of hash functions to use</p></td></tr><tr><td class="src">-> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a></td><td class="doc"><p>number of bits in filter</p></td></tr><tr><td class="src">-> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Control-Monad-ST.html#t:ST">ST</a> s (<a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a)</td><td class="doc empty"> </td></tr></table></div><div class="doc"><p>Create a new mutable Bloom filter. For efficiency, the number of
bits used may be larger than the number requested. It is always
rounded up to the nearest higher power of two, but will be clamped
at a maximum of 4 gigabits, since hashes are 32 bits in size.</p></div></div><h2 id="g:7">Accessors</h2><div class="top"><p class="src"><a id="v:length" class="def">length</a> :: <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> <a href="src/Data-BloomFilter-Mutable.html#length" class="link">Source</a> <a href="#v:length" class="selflink">#</a></p><div class="doc"><p>Return the size of a mutable Bloom filter, in bits.</p></div></div><div class="top"><p class="src"><a id="v:elem" class="def">elem</a> :: a -> <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Control-Monad-ST.html#t:ST">ST</a> s <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a> <a href="src/Data-BloomFilter-Mutable.html#elem" class="link">Source</a> <a href="#v:elem" class="selflink">#</a></p><div class="doc"><p>Query a mutable Bloom filter for membership. If the value is
present, return <code>True</code>. If the value is not present, there is
<em>still</em> some possibility that <code>True</code> will be returned.</p></div></div><h2 id="g:8">Mutation</h2><div class="top"><p class="src"><a id="v:insert" class="def">insert</a> :: <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Control-Monad-ST.html#t:ST">ST</a> s () <a href="src/Data-BloomFilter-Mutable.html#insert" class="link">Source</a> <a href="#v:insert" class="selflink">#</a></p><div class="doc"><p>Insert a value into a mutable Bloom filter. Afterwards, a
membership query for the same value is guaranteed to return <code>True</code>.</p></div></div><h1 id="g:9">The underlying representation</h1><div class="doc"><p>If you serialize the raw bit arrays below to disk, do not
expect them to be portable to systems with different
conventions for endianness or word size.</p></div><div class="doc"><p>The raw bit array used by the mutable <code><a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a></code> type.</p></div><div class="top"><p class="src"><a id="v:bitArray" class="def">bitArray</a> :: <a href="Data-BloomFilter-Mutable.html#t:MBloom">MBloom</a> s a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/array-0.5.1.1/Data-Array-ST.html#t:STUArray">STUArray</a> s <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> <a href="Data-BloomFilter-Mutable.html#t:Hash">Hash</a> <a href="src/Data-BloomFilter-Mutable-Internal.html#bitArray" class="link">Source</a> <a href="#v:bitArray" class="selflink">#</a></p></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.17.2</p></div></body></html>
|