[Haskell-cafe] Documentation of Data.Map
Shiqi Cao
caos2 at mcmaster.ca
Wed Jun 15 13:26:28 EDT 2005
Hi,
I just read the API of Data.Map and the source code of it. The
documentation of "insertWithKey" is not precise.
The following is copied from API.
*insertWithKey* :: Ord
<http://www.haskell.org/ghc/docs/6.4/html/libraries/base/Prelude.html#t%3AOrd>
k => (k -> a -> a -> a) -> k -> a -> Map
<http://www.haskell.org/ghc/docs/6.4/html/libraries/base/Data.Map.html#t%3AMap>
k a -> Map
<http://www.haskell.org/ghc/docs/6.4/html/libraries/base/Data.Map.html#t%3AMap>
k a
/O(log n)/. Insert with a combining function.
This function take a function to solve collision, which can be
considered as an operator. However the documentation does not specify
the order of arguments to the operator. Because of that we can only
supply operator which is communitive. But we all know that there must
exist an ordering of arguments. I explored the source code of it as the
following.
-- | /O(log n)/. Insert with a combining function.
insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey f kx x t
= case t of
Tip -> singleton kx x
Bin sy ky y l r
-> case compare kx ky of
LT -> balance ky y (insertWithKey f kx x l) r
GT -> balance ky y l (insertWithKey f kx x r)
EQ -> Bin sy ky (f ky x y) l r
By the last line the ordering is clear such that the inserted value goes the first.
Shiqi Cao
More information about the Haskell-Cafe
mailing list