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

[Luke Palmer]

On Feb 18, 2008 5:11 AM, Stuart Cook <scook0 at gmail.com> wrote:
> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>