[Haskell-cafe] how to select random elements of a Data.Set?

Roman Cheplyaka 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

  import Data.Map
  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).
> J.W.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

Roman I. Cheplyaka :: http://ro-che.info/

More information about the Haskell-Cafe mailing list