Ode on a random urn (functional pearl)
Abstract
We present the urn, a simple tree-based data structure that supports sampling from and updating discrete probability distributions in logarithmic time. We avoid the usual complexity of traditional self-balancing binary search trees by not keeping values in a specific order. Instead, we keep the tree maximally balanced at all times using a single machine word of overhead: its size.
Urns provide an alternative interface for the frequency combinator from the QuickCheck library that allows for asymptotically more efficient sampling from dynamically-updated distributions. They also facilitate backtracking in property-based random testing, and can be applied to such complex examples from the literature as generating well-typed lambda terms or information flow machine states, demonstrating significant speedups.
References
[1]
A. Chlipala. Certified Programming with Dependent Types: A Pragmatic Introduction to the Coq Proof Assistant . MIT Press, 2013.
[2]
K. Claessen and J. Hughes. QuickCheck: a lightweight tool for random testing of Haskell programs . In 5th ACM SIGPLAN International Conference on Functional Programming (ICFP). 2000.
[3]
R. Durstenfeld. Algorithm 235: Random permutation . Commun. ACM, 7(7):420–, 1964.
[4]
C. Gibbard, B. Yorgey, et al. MonadRandom: Random-number generation monad. http://hackage.haskell.org/package/MonadRandom-0.4.2.3, 2016.
[5]
Haskell Libraries Team and R. Leshchinskiy. vector: Efficient arrays. http: //hackage.haskell.org/package/vector-0.11.0.0, 2015.
[6]
R. Hickey. The Clojure programming language. http://clojure.org, 2012.
[7]
C. Hriţcu, J. Hughes, B. C. Pierce, A. Spector-Zabusky, D. Vytiniotis, A. Azevedo de Amorim, and L. Lampropoulos. Testing noninterference, quickly . In 18th ACM SIGPLAN International Conference on Functional Programming (ICFP). 2013.
[8]
D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098–1101, 1952.
[9]
L. Lampropoulos, D. Gallois-Wong, C. Hritcu, J. Hughes, B. C. Pierce, and L. Xia. Beginner’s Luck: a language for property-based generators . In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017, 2017.
[10]
C. Okasaki. Purely Functional Data Structures. Cambridge University Press, New York, NY, USA, 1998.
[11]
B. O’Sullivan. Criterion: a Haskell microbenchmarking library. http://www. serpentine.com/criterion/, 2014.
[12]
M. H. Pałka. Testing an optimising compiler by generating random lambda terms. http://www.cse.chalmers.se/~palka/testingcompiler/ .
[13]
M. H. Pałka, K. Claessen, A. Russo, and J. Hughes. Testing an optimising compiler by generating random lambda terms . In Proceedings of the 6th International Workshop on Automation of Software Test. 2011.
[14]
Z. Paraskevopoulou, C. Hriţcu, M. Dénès, L. Lampropoulos, and B. C. Pierce. Foundational property-based testing . In C. Urban and X. Zhang, editors, 6th International Conference on Interactive Theorem Proving (ITP). 2015.
[15]
QuickCheck developers, N. Smallbone, B. Bringert, and K. Claessen. QuickCheck: Automatic testing of Haskell programs. http://hackage.haskell.org/package/ QuickCheck-2.8.2, 2016.
[16]
D. Steinitz and J. Cook. random-fu: Random number generation. http://hackage. haskell.org/package/random-fu-0.2.6.2, 2015.
Index Terms
- Ode on a random urn (functional pearl)
Recommendations
Ode on a random urn (functional pearl)
Haskell 2017: Proceedings of the 10th ACM SIGPLAN International Symposium on HaskellWe present the urn, a simple tree-based data structure that supports sampling from and updating discrete probability distributions in logarithmic time. We avoid the usual complexity of traditional self-balancing binary search trees by not keeping ...
ArbitCheck: A Highly Automated Property-Based Testing Tool for Java
ICSTW '14: Proceedings of the 2014 IEEE International Conference on Software Testing, Verification, and Validation WorkshopsLightweight property-based testing tools are becoming popular these days. With property-based testing, developers can test properties of the system under test against large varieties of randomly generated inputs without writing test cases. Despite the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2017
211 pages
Copyright © 2017 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 September 2017
Published in SIGPLAN Volume 52, Issue 10
Check for updates
Author Tags
Qualifiers
- Article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 647Total Downloads
- Downloads (Last 12 months)212
- Downloads (Last 6 weeks)23
Reflects downloads up to 01 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in