插入Data.Set并检查元素是否同时存在

Question

是否有一种有效的方法可以Data.Set在一段时间内插入一个值,同时检查该值是否已经是该集合的成员？

如果没有,是否有任何特殊原因使用containers库中当前的集合实现无法编写这样的函数？

Answer 1

你可以做到这一点O(log n),采取的事实,优势的复杂性size是O(1),和前后只比较:

-- | Inserts a value into the Set.  If the value was not already in the set,
-- | then True is returned, otherwise False
insertIfMissing :: Ord a => a -> Set a -> (Set a, Bool)
insertIfMissing a s = (newSet, missing)
    where
        newSet = Set.insert a s
        oldSize = Set.size s
        newSize = Set.size newSet
        missing = oldSize < newSize

如果你对它是否已经存在不感兴趣,那么missing由于懒惰,这不应该计算部分.