Выберите случайный элемент из набора, быстрее, чем линейное время (Haskell)

Я хотел бы создать эту функцию, которая выбирает случайный элемент из набора :

randElem :: (RandomGen g) => Set a -> g -> (a, g)

Простые реализации Listy могут быть записаны. Например, (Код обновлен, Проверенная работа):

import Data.Set as Set
import System.Random (getStdGen, randomR, RandomGen)

randElem :: (RandomGen g) => Set a -> g -> (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 <- getStdGen
          print . fst $ randElem s g
    where s = Set.fromList [1,3,5,7,9]

Но с использованием ! ! возникает линейный доступ к большому (случайным образом выбрано) n . Есть ли более быстрый способ выбрать случайного элемента в наборе? В идеале, повторяющиеся случайные выборы должны создавать равномерное распределение по всем вариантам, что означает, что он не предпочитает некоторых элементов над другими.

Редактировать : некоторые великие идеи появляются в ответах, поэтому я просто хотел бросить пару Больше разъяснений на том, что именно я ищу. Я задал этот вопрос с множеством в качестве решения этой ситуации . Я предпочитаю ответы, что оба

1. избегают использовать любую внешнюю функцию. Бухгалтерия за пределами внутренних органов набора, а
2. поддерживать хорошую производительность (лучше чем o (n) в среднем), даже если Funct Ион используется только один раз в уникальный набор.

У меня также есть эта любовь к рабочему коду, так ожидать (как минимум) +1 от меня, если ваш ответ включает в себя рабочий раствор.