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/Collect... But maybe your concern is efficiency, and thus you need the special data structure.