[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:
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.
More information about the Haskell-Cafe
mailing list