Random Urns

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.)

Code overview

To compile, run cargo build.
To run unit tests + QuickCheck tests, run cargo test.

• types.rs: Type definitions
• urn.rs: Methods for interacting with urns
• almost_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)