有沒有一種有效的方法將值插入到Data.Set
中,同時檢查該值是否已經是該組的成員?插入Data.Set並檢查元素是否同時存在
如果沒有,是否有任何特殊的原因,這樣的函數將不可能用containers
庫中的集合的當前實現編寫?
有沒有一種有效的方法將值插入到Data.Set
中,同時檢查該值是否已經是該組的成員?插入Data.Set並檢查元素是否同時存在
如果沒有,是否有任何特殊的原因,這樣的函數將不可能用containers
庫中的集合的當前實現編寫?
您可以通過採取的事實size
是O(1)
優勢與O(log n)
複雜做到這一點,只是比較之前和之後:
-- | 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
部分。
實際上可以通過稍微更改Set.insert
函數來編寫這樣的函數。我決定返回一個Maybe (Set a)
,所以如果元素不存在,函數只會創建一個新的Set
。用(Bool, Set a)
作爲返回類型編寫函數也是可能的。
insertMember :: Ord a => a -> Set a -> Maybe (Set a)
insertMember = go
where
go :: Ord a => a -> Set a -> Maybe (Set a)
STRICT_1_OF_2(go)
go x Tip = Just $ singleton x
go x (Bin sz y l r) = case compare x y of
LT -> do
l' <- go x l
return $ balanceL y l' r
GT -> do
r' <- go x r
return $ balanceR y l
EQ -> Nothing
想要插入一個元素嗎?當且僅當它不在集合中,但不重複遍歷結構插入它的工作,如果它不是? – bheklilr 2014-09-13 20:11:58
@bheklilr是的,這是另一種說法。我想要做的就是'(Set.member elem set,Set.insert elem set)',更高效(不重複工作)。例如,在C++中,可以將'insert'的返回值與'.end()'進行比較,以檢查元素是否已經是該集合的成員,而不需要單獨的調用來檢查成員資格。 – bennofs 2014-09-13 20:15:08
所以你想要一個函數'insertIfMissing :: Ord a => a - >設置一個 - >(Set a,Bool)'來表明插入的值是否被實際插入? – bheklilr 2014-09-13 20:20:11