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

Henning Thielemann lemming at henning-thielemann.de
Mon Feb 18 05:53:24 EST 2008

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:

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:

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

More information about the Haskell-Cafe mailing list