A Rust implementation of Urns (Lampropulos et al. 2017), a data structure which allows for random sampling and updating discrete distributions in logarithmic time.
For details about the design behind urns, see the original paper or the Haskell Symposium '17 talk.
This implementation has been adapted from:
- Lampropulos et al.'s original Haskell implementation
- Justine Frank's OCaml implementation
(I've tried to follow the Haskell/OCaml implementations as close as possible.)
To compile, run cargo build.
To run unit tests + QuickCheck tests, run cargo test.
types.rs: Type definitionsurn.rs: Methods for interacting with urnsalmost_perfect.rs: Almost perfect trees (used in the construction of urns)quickcheck_tests.rs: QuickCheck properties for urns
Dependencies:
rand(for random number generation)quickcheck(only used for testing internal functions)