[Haskell-cafe] Documentation of Data.Map

[Shiqi Cao]

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