我想创建这个函数，它从Set中选择一个随机元素：
randElem :: (RandomGen g) => Set a -> g -> (a, g)
可以编写简单的列表实现。例如（代码更新，验证工作）：
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的线性查找成本。有没有更快的方法来选择集合中的随机元素？理想情况下，重复随机选择应该在所有选项上产生均匀分布，这意味着它不喜欢某些元素而不是其他元素。
编辑：答案中出现了一些很棒的想法，所以我只想对我正在寻找的内容进行更多的澄清。我用套装作为this situation的解决方案问了这个问题。我更喜欢两者的答案
我也喜欢工作代码，所以如果你的答案包括一个有效的解决方案，那么期望（至少）给我+1。
这是一个想法：你可以做间隔二等分。
size s是恒定的时间。使用randomR获取您选择的集合的距离。split在原始的findMin和findMax之间有各种值，直到你得到你想要的位置的元素。如果你真的担心该组合是由实数组成并且非常紧密地聚集在一起，你可以每次重新计算findMin和findMax以保证每次都能敲掉一些元素。性能将是O（n log n），基本上不比你当前的解决方案差，但是只有相当弱的条件才能使得集合不能完全聚集在某个积累点附近，平均性能应该是〜（（logn） ^ 2），这是相当不变的。如果它是一组整数，则得到O（log n * log m），其中m是该集合的初始范围;它只是在区间二分区（或其顺序类型有累积点的其他数据类型）中可能导致真正令人讨厌的性能的实数。
PS。这样可以产生完美均匀的分布，只要观察一下即可，以确保可以将元素放在顶部和底部。
一些不优雅的，未经检查的（伪？）代码。在我当前的机器上没有编译器进行冒烟测试，可能需要使用更少的ifs。一件事：看看如何生成mid;它需要一些调整，这取决于你是否正在寻找一些适用于整数或实数的东西（区间二分本质上是拓扑的，对于具有不同拓扑的集合，它不应该完全相同）。
import Data.Set as Set
import System.Random (getStdGen, randomR, RandomGen)
getNth (s, n) = if n = 0 then (Set.findMin s) else if n + 1 = Set.size s then Set.findMax s
else if n < Set.size bott then getNth (bott, n) else if pres and Set.size bott = n then n
else if pres then getNth (top, n - Set.size bott - 1) else getNth (top, n - Set.size)
where mid = ((Set.findMax s) - (Set.findMin s)) /2 + (Set.findMin s)
(bott, pres, top) = (splitMember mid s)
randElem s g = (getNth(s, n), g')
where (n, g') = randomR (0, Set.size s - 1) g
Data.Map有一个索引函数（elemAt），所以使用这个：
import qualified Data.Map as M
import Data.Map(member, size, empty)
import System.Random
type Set a = M.Map a ()
insert :: (Ord a) => a -> Set a -> Set a
insert a = M.insert a ()
fromList :: Ord a => [a] -> Set a
fromList = M.fromList . flip zip (repeat ())
elemAt i = fst . M.elemAt i
randElem :: (RandomGen g) => Set a -> g -> (a, g)
randElem s g = (elemAt n s, g')
where (n, g') = randomR (0, size s - 1) g
并且你有一些与Data.Set（关于接口和性能）完全兼容的东西，它还有一个log（n）索引函数和你请求的randElem函数。
请注意，randElem是log（n）（它可能是这种复杂性可以获得的最快实现），并且所有其他函数都具有与Data.Set相同的复杂性。如果您需要Set API中的任何其他特定功能，请告诉我，我将添加它们。
据我所知，正确的解决方案是使用索引集 - 即IntMap。您只需存储随地图添加的元素总数。每次添加元素时，都会使用比以前更高的键添加元素。删除元素很好 - 只是不要改变总元素计数器。如果在查找键控元素时该元素不再存在，则生成一个新的随机数并重试。这一直有效，直到删除的总数占据集合中活动元素的数量。如果这是一个问题，您可以保留一组单独的已删除键，以便在插入新元素时进行绘制。
从containers-0.5.2.0开始，Data.Set模块具有elemAt函数，该函数通过排序的元素序列中的从零开始的索引检索值。所以现在编写这个函数是微不足道的
import Control.Monad.Random
import Data.Set (Set)
import qualified Data.Set as Set
randElem :: (MonadRandom m, Ord a) -> Set a -> m (a, Set a)
randElem xs = do
n <- getRandomR (0, Set.size xs - 1)
return (Set.elemAt n xs, Set.deleteAt n xs)
由于Set.elemAt和Set.deleteAt都是O（log n），其中n是集合中元素的数量，整个操作是O（log n）
如果您可以访问the internals of Data.Set，它只是一个二叉树，您可以在树上递归，在每个节点根据各自的大小选择其中一个分支。这非常简单，在内存管理和分配方面为您提供了非常好的性能，因为您没有额外的簿记功能。 OTOH，你必须调用RNG O（log n）次。
一个变体是使用Jonas的建议首先获取大小并根据该大小选择随机元素的索引，然后使用（尚未添加的elemAt）函数到Data.Set。
如果您不需要修改您的集合或需要不经常修改它，您可以使用数组作为具有O（1）访问时间的查找表。
import qualified Data.Vector
import qualified Data.Set
newtype RandSet a = RandSet (V.Vector a)
randElem :: RandSet a -> RandomGen -> (a, RandomGen)
randElem (RandSet v) g
| V.empty v = error "Cannot select from empty set"
| otherwise =
let (i,g') = randomR (0, V.length v - 1) g
in (v ! i, g')
-- Of course you have to rebuild array on insertion/deletion which is O(n)
insert :: a -> RandSet a -> RandSet a
insert x = V.fromList . Set.toList . Set.insert x . Set.fromList . V.toList`
如果你不介意完全消耗你的RandomGen，这个问题可能会有点麻烦。使用可分离的发电机，这是一个A-OK的事情。基本思想是为集合创建一个查找表：
randomElems :: Set a -> RandomGen -> [a]
randomElems set = map (table !) . randomRs bounds where
bounds = (1, size set)
table = listArray bounds (toList set)
这将具有非常好的性能：它将花费您O（n + m）时间，其中n是集合的大小，m是您评估的结果列表的元素数量。 （当然，加上在边界中随机选择m个数字所需的时间。）
实现此目的的另一种方法可能是使用Data.Sequence而不是Data.Set。这将允许您在O（1）时间内添加元素到O（log n）时间的索引元素。如果您还需要能够进行成员资格测试或删除，则必须使用更通用的fingertree包并使用类似FingerTree (Sum 1, Max a) a的内容。要插入元素，请使用Max a批注找到要插入的正确位置;这基本上需要O（log n）时间（对于某些使用模式，它可能会少一些）。要进行成员资格测试，基本上做同样的事情，所以它是O（log n）时间（同样，对于某些使用模式，这可能会少一些）。要选择一个随机元素，请使用Sum 1注释进行索引，取O（log n）时间（这将是均匀随机索引的平均情况）。