Christian.Maeder at dfki.de
Wed Jul 18 11:10:04 EDT 2007
Andriy Palamarchuk schrieb:
> I'm currently improving Data.Map documentation.
> Behavior of updateAt in this module differs from what I would expect.
> The documentation says:
> updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
> O(log n). Update the element at index. Calls error when an invalid index is used.
> So I expected this code:
> let m = fromList [(3,"b"),(5,"a")]
> let f k a = Just "x"
> updateAt f 1 m
> to return
> fromList [(3,"b"),(5,"x")]
> but it returns
> fromList [(5,"x")]
> deleting the key 3.
> I tested this using ghci 6.6.
> Is this a bug or I missed something here?
This is a bug, the tree is not properly reconstructed (in the LT and GT
cases). "updateAt f 0 m" works as expected, because the left tree
happens to be empty and updateAt goes into the EQ case. "deleteAt 1 m"
is also wrong.
The code looks as follows:
-- | /O(log n)/. Update the element at /index/. Calls 'error' when an
-- invalid index is used.
updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
updateAt f i Tip = error "Map.updateAt: index out of range"
updateAt f i (Bin sx kx x l r)
= case compare i sizeL of
LT -> updateAt f i l
GT -> updateAt f (i-sizeL-1) r
EQ -> case f kx x of
Just x' -> Bin sx kx x' l r
Nothing -> glue l r
sizeL = size l
-- | /O(log n)/. Delete the element at /index/.
-- Defined as (@'deleteAt' i map = 'updateAt' (\k x -> 'Nothing') i map@).
deleteAt :: Int -> Map k a -> Map k a
deleteAt i map
= updateAt (\k x -> Nothing) i map
More information about the Libraries