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

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.