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

[Christian Maeder]

Am 20.07.2012 15:24, schrieb jwaldmann:
> Dear all,
>
> how would I quickly select an element of a Set (as in Data.Set)
> uniformly at random?

If you use a "Map a ()" (or Map a a) you can use Map.elemAt.

The initial conversion is still linear, though.

-- | convert a set into an identity map
setToMap :: Ord a => Set.Set a -> Map.Map a a
setToMap = Map.fromDistinctAscList . List.map (\ a -> (a, a)) . Set.toList

HTH C.

>
> 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.
>