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