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

[Brent Yorgey]

On Fri, Jul 20, 2012 at 01:24:57PM +0000, jwaldmann wrote:
> 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.

If you had access to the Set constructors, this would be very easy, as
each node caches a size.  Unfortunately there does not appear to be
any way to do this in sub-linear time via the exposed API, because
there is no way to directly access the subtrees.

I wonder about the wisdom of exporting a function like

  -- | Partition a set into two approximately equal-sized subsets.
  --   If @divide s == (s1,s2)@, then 
  --     * @s1 `intersect` s2 == empty@
  --     * @s1 `union` s2     == s@
  --     * The sizes of @s1@ and @s2@ differ by at most a constant factor
  --       (currently, 3).
  divide :: Set a -> (Set a, Set a)

which would give you enough to implement what you want, without
breaking the Set abstraction.  (However, even though technically it
doesn't break any abstraction, it still smells somewhat
"implementation-dependent"...)

-Brent