Czy istnieje skuteczny sposób wstawienia wartości do Data.Set przy jednoczesnym sprawdzeniu, czy ta wartość była już elementem zestawu?Wstaw do Data.Set i sprawdź, czy element istnieje w tym samym czasie.
Jeśli nie ma, czy istnieje jakiś szczególny powód, dla którego taka funkcja byłaby niemożliwa do napisania przy aktualnej implementacji zestawów w bibliotece containers?
Można to zrobić z O(log n) złożoności, wykorzystując fakt, że size jest O(1), i po prostu porównać przed i po:
-- | 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
A jeśli nie jesteś zainteresowany, czy to był już obecny, to nie powinno obliczyć części missing dzięki lenistwu.
Och, to niezła sztuczka! Tylko drobna uwaga: myślę, że złożoność '(Set.insert elem set, Set.member elem set)' jest również 'O (log n)', więc argument złożoności nie jest tutaj istotny, chodzi tylko o stałe czynniki . – bennofs
@bennofs Złożoność jest taka sama, ale to się powtórzy. Zasadniczo kończy się różnica między 'O (log n) + O (1) + O (1)' i 'O (log n) + O (log n)'. Użycie 'Set.member' będzie prawdopodobnie zauważalnie wolniejsze w przypadku dużych zestawów. – bheklilr
Taką funkcję można faktycznie zapisać, zmieniając nieznacznie funkcję Set.insert. Postanowiłem zwrócić Maybe (Set a), więc funkcja tworzy tylko nowy Set, jeśli element nie istnieje. Równie dobrze byłoby napisać funkcję o numerze (Bool, Set a) jako typ zwracany.
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
Czy chcesz wstawić element wtedy i tylko wtedy, gdy nie jest on jeszcze w zestawie, ale nie powtórzy pracy z przechodzeniem przez strukturę w celu wstawienia, jeśli nie jest? – bheklilr
@bheklilr Tak, to inny sposób na powiedzenie tego. Wszystko, co chcę zrobić, to '(Set.member elem set, Set.insert elem set)', tylko bardziej wydajnie (nie powtarzając pracy). Na przykład w C++ możesz porównać zwracaną wartość 'insert' z' .end() ', aby sprawdzić, czy element był już członkiem zestawu, bez konieczności osobnego połączenia w celu sprawdzenia członkostwa. – bennofs
A więc potrzebujesz funkcji 'insertIfMissing :: Ord a => a -> Set a -> (Set a, Bool)' która wskazuje, czy wstawiona wartość została faktycznie wstawiona? – bheklilr