[Haskell-cafe] how to select random elements of a Data.Set?
roma at ro-che.info
Fri Jul 20 16:36:10 CEST 2012
There was recently a proposal to add indexing operators to Data.Set.
Until it is accepted, you can simulate Set with Map like this
type Set a = Map a ()
Data.Map already has indexing operations (e.g. elemAt, deleteAt).
* jwaldmann <waldmann at imn.htwk-leipzig.de> [2012-07-20 13:24:57+0000]
> Dear all,
> how would I quickly select an element of a Set (as in Data.Set)
> uniformly at random?
> Via the API, this can only be done in linear time? (via toList)
> If I could access the tree structure,
> then of course it could be logarithmic.
> But probably I'd need a weighted selection sooner or later,
> and this would require some specific code anyway. Or does it not?
> Actually I need a sequence of such selections
> (each selected element is deleted immediately).
> I don't need all elements
> (so, computing a random permuation might be too much).
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Roman I. Cheplyaka :: http://ro-che.info/
More information about the Haskell-Cafe