title: Select random element from a set, faster than linear time (Haskell)
body: <p>I'd like to create this function, which selects a random element from a <a href="http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html#t:Set" rel="nofollow noreferrer">Set</a>:</p>
  
  <pre><code>randElem :: (RandomGen g) =&gt; Set a -&gt; g -&gt; (a, g)
  </code></pre>
  
  <p>Simple listy implementations can be written. For example (code updated, verified working):</p>
  
  <pre><code>import Data.Set as Set
  import System.Random (getStdGen, randomR, RandomGen)
  
  randElem :: (RandomGen g) =&gt; Set a -&gt; g -&gt; (a, g)
  randElem s g = (Set.toList s !! n, g')
      where (n, g') = randomR (0, Set.size s - 1) g
  
  -- simple test drive
  main = do g &lt;- getStdGen
            print . fst $ randElem s g
      where s = Set.fromList [1,3,5,7,9]
  </code></pre>
  
  <p>But using <code>!!</code> incurs a linear lookup cost for large (randomly selected) <code>n</code>. Is there a faster way to select a random element in a Set? Ideally, repeated random selections should produce a uniform distribution over all options, meaning it does not prefer some elements over others.</p>
  
  <hr>
  
  <p><strong>Edit</strong>: some great ideas are popping up in the answers, so I just wanted to throw a couple more clarifications on what exactly I'm looking for. I asked this question with Sets as the solution to <a href="https://stackoverflow.com/questions/7342862/growing-arrays-in-haskell">this situation</a> in mind. I'll prefer answers that both</p>
  
  <ol>
  <li>avoid using any outside-the-function bookkeeping beyond the Set's internals, and</li>
  <li>maintain good performance (better than <em>O(n)</em> on average) even though the function is only used once per unique set.</li>
  </ol>
  
  <p>I also have this love of working code, so expect (at minimum) a +1 from me if your answer includes a working solution.</p>