cabal-version: 3.4 name: bloomfilter-blocked version: 0.1.0.1 synopsis: Fast, compact Bloom filters description: This library provides [Bloom filters](https://en.wikipedia.org/wiki/Bloom_filter). A Bloom filter is a compact but probabilistic set-like data structure, supporting fast insert and membership operations. Bloom filters are probabilistic in the sense that when querying for set membership, they can (with some probability) falsely report that an element is present when it is not present. On the other hand it will /never/ falsely report that an element is not present when in fact it is present. That is, it can have false positives but not false negatives. The false positive rate (FPR) can be adjusted. Bloom filters are compact, needing only a few /bits/ per element. For example 10 bits per element is enough for a false positive rate (FPR) of 1%, and 15 bits for 0.1%. The library includes two implementations of Bloom filters: [classic]: in "Data.BloomFilter.Classic": a default implementation that is faithful to the classical description of a Bloom filter data structure. [block-structured]: in "Data.BloomFilter.Blocked": a cache optimised representation that is faster, at the cost of needing a few more bits per element to achieve a target FPR. Features of the library: * Fast. See the benchmark results. * Compact. It uses optimal sized bit arrays: no bigger than necessary. * Faster still: the block-structured Bloom filters are even faster, at the expense of needing more bits per entry. * Supports very large Bloom filters, bigger than 2^32 bits. * Simple API for specifying the size of Bloom filters. * Support for hash salting, for using Bloom filters with untrusted inputs. * Serialisation support with format version tracking. license: Apache-2.0 license-files: LICENSE NOTICE author: Duncan Coutts, Joris Dral, Matthias Heinzel, Wen Kokke maintainer: duncan@well-typed.com, joris@well-typed.com copyright: (c) 2023-2025 Cardano Development Foundation (c) 2025 Well-Typed LLP category: Data build-type: Simple tested-with: GHC ==9.2 || ==9.4 || ==9.6 || ==9.8 || ==9.10 || ==9.12 extra-doc-files: CHANGELOG.md README.md extra-source-files: xxhash/include/HsXXHash.h xxhash/xxHash-0.8.2/xxhash.h license-files: xxhash/xxHash-0.8.2/LICENSE-xxHash source-repository head type: git location: https://github.com/well-typed/bloomfilter-blocked source-repository this type: git location: https://github.com/well-typed/bloomfilter-blocked tag: bloomfilter-blocked-0.1.0.1 common warnings ghc-options: -Wall -Wcompat -Wincomplete-uni-patterns -Wincomplete-record-updates -Wpartial-fields -Widentities -Wredundant-constraints -Wmissing-export-lists -Wno-unticked-promoted-constructors -Wunused-packages ghc-options: -Werror=missing-deriving-strategies common language default-language: GHC2021 default-extensions: DerivingStrategies RecordWildCards RoleAnnotations library import: language, warnings hs-source-dirs: src build-depends: , base >=4.16 && <4.22 , bloomfilter-blocked:xxhash , bytestring ^>=0.11 || ^>=0.12 , deepseq ^>=1.4 || ^>=1.5 , primitive ^>=0.9 exposed-modules: Data.BloomFilter Data.BloomFilter.Blocked Data.BloomFilter.Classic Data.BloomFilter.Hash other-modules: Data.BloomFilter.Blocked.BitArray Data.BloomFilter.Blocked.Calc Data.BloomFilter.Blocked.Internal Data.BloomFilter.Classic.BitArray Data.BloomFilter.Classic.Calc Data.BloomFilter.Classic.Internal ghc-options: -O2 test-suite tests import: language, warnings type: exitcode-stdio-1.0 hs-source-dirs: tests main-is: bloomfilter-tests.hs build-depends: , base <5 , bloomfilter-blocked , bytestring , quickcheck-instances , tasty , tasty-quickcheck benchmark bench import: language, warnings type: exitcode-stdio-1.0 hs-source-dirs: bench main-is: bloomfilter-bench.hs build-depends: , base , bloomfilter-blocked , criterion , random -- It's not really a test suite, but if we make it an executable then its -- dependencies will be included for dependency resolution when building the -- main library. As a test-suite, it's more accurately represented as an -- internal component. test-suite fpr-calc import: language, warnings type: exitcode-stdio-1.0 hs-source-dirs: tests main-is: fpr-calc.hs build-depends: , base , bloomfilter-blocked , containers , parallel , random >=1.3 , regression-simple ghc-options: -threaded -rtsopts -- It's not really a test suite, but if we make it an executable then its -- dependencies will be included for dependency resolution when building the -- main library. As a test-suite, it's more accurately represented as an -- internal component. test-suite spell import: language, warnings type: exitcode-stdio-1.0 hs-source-dirs: examples main-is: spell.hs build-depends: , base , bloomfilter-blocked , directory library xxhash import: language, warnings visibility: private include-dirs: xxhash/xxHash-0.8.2/ xxhash/include/ includes: HsXXHash.h xxhash.h exposed-modules: Data.Digest.XXH3 if (arch(x86_64) && !os(osx)) -- Cabal doesn't pass cc-options to "ordinary" Haskell source compilation -- https://github.com/haskell/cabal/issues/9801 ghc-options: -optc=-mavx2 -optc=-O3 other-modules: Data.Digest.XXH3.FFI hs-source-dirs: xxhash/src build-depends: , base <5 , bytestring ^>=0.11 || ^>=0.12 , primitive ^>=0.9 test-suite xxhash-tests import: language, warnings type: exitcode-stdio-1.0 hs-source-dirs: xxhash/tests main-is: xxhash-tests.hs build-depends: , base <5 , bloomfilter-blocked:xxhash , bytestring , primitive , tasty , tasty-hunit , tasty-quickcheck