[Haskell-cafe] naming a data structure for weighted random selection without replacement

Stuart Cook scook0 at gmail.com
Mon Feb 18 00:11:44 EST 2008


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.

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.


More information about the Haskell-Cafe mailing list