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

[Henning Thielemann]

On Mon, 18 Feb 2008, Stuart Cook 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.

Some ours ago I uploaded a package which would allow this:
 http://hackage.haskell.org/cgi-bin/hackage-scripts/package/probability-0.2

You would stack a State transformer with a distribution as state and the
inner monad is a Probability.Random.T. A similar example is here:
 http://darcs.haskell.org/probability/src/Numeric/Probability/Example/Collection.hs

But maybe your concern is efficiency, and thus you need the special data
structure.