Bloom

Elm Bloom filter implementation using Murmur3. It may not be the fastest implementation, but it is simple and easy to use. This blog post with rules of thumb for choosing m and k might be helpful.

Use it as follows:

import Bloom exposing (empty, add, test)


-- create an empty filter with m elements and k hashes
emptyFilter = empty 1000 4


-- add elements to the filter
filter = 
  List.foldr 
    add
    emptyFilter 
    ["foo", "bar", "baz", ... ]


-- check if elements are recognized by the filter
test "bar" filter == True
test "barr" filter == False

Data

type alias Filter =

{ set : Array Int

, m : Int

, k : Int

}

The Filter struct holds an array containing the actual filter, but also the values for m and k (for simplicity).

Create, manipulate and test

empty : Int -> Int -> Filter

Creates an empty Filter, containing m elements and using k hashes.

import Bloom


Bloom.empty 10 3 |> Array.toList


-- {m=10, k=3, set=[0,0,0,0,0,0,0,0,0,0]}

add : String -> Filter -> Filter

Adds elements to an existing Filter.

import Bloom exposing (add, empty)


t = List.foldr add (empty 20 3) ["foo", "bar", "baz"]

test : String -> Filter -> Bool

Tests if a filter contains an element. By its probalistic nature this function may yield false positive results.

import Bloom exposing (add, empty)


-- create filter t


test "foo" t == True
test "fou" t == False

Modules

Bloom

ggb/elm-bloom/1.0.1

Bloom

Data

Create, manipulate and test

Modules