On Feb 18, 2008 5:11 AM, Stuart Cook
A while ago I wrote a little data structure that allows weighted random selection-without-replacement from a collection of values in O(log n) time.[1] I'm now in the process of packaging it up for Hackage, but I'm looking for good names for both the type and its operations.
I'm pretty sure it should have Random in the name whatever it is called. Luke
The name I have at the moment is "Pool", which I'm reasonably happy with, but I wanted to see if I could find anything better. Asking on #haskell got me a few responses:
* Hat (cute, but conflicts with the program tracer) * Bag (already way too overloaded) * Bucket (not as suggestive as Pool)
I have three main operations:
* "pull" selects a random element, returning it and the remainder, but fails if the pool is empty * "pullN" selects /n/ distinct elements, returning them and the remainder, but fails if the pool has too few elements * "takeN" selects up to /n/ distinct elements, returning them and the remainder, but returns no more elements than could be found in the pool (analogous to Data.List.take)
Any suggestions?
Stuart
[1] Actually I delegated most of the work to the data-structure-in-a-can that is Data.FingerTree, but that's another story. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe