Proposal: add traverseWithKey to Data.Map

[Thomas Schilling]

On 14 March 2012 23:28, Max Bolingbroke <batterseapower at hotmail.com> wrote:
> Hi Haskellers,
>
> I propose to add a new function, traverseWithKey, to Data.Map:

+1

A few minor comments below.

> """
> -- | /O(n)/.
> -- @'traverseWithKey' f s == 'fmap' 'fromList' ('traverse' (\(k, v) ->
> fmap ((,) k) (f k v)) ('toList' s))@

Since we're assuming that the users already knows Applicative, I
believe the following formulation would be easier to read:

    fromList <$> traverse (\(k, v) -> (,) k <$> f k v) (toList m)

I agree with the use of '==' rather than '=' since the above
definition has an Ord constraint on the key, but this function does
not.  You could get that by using fromDistinctAscList but that would
defeat the purpose of giving an easy to understand definition.

> -- That is, behaves exactly like a regular 'traverse' except that the traversing
> -- function also has access to the key associated with a value.
> --
> -- > traverseWithKey (\k v -> if k + v < 10 then Just (v + 1) else
> Nothing) (fromList [(1, 2), (5, 4)]) == Just (fromList [(1, 3), (5,
> 5)])
> -- > traverseWithKey (\k v -> if k + v < 10 then Just (v + 1) else
> Nothing) (fromList [(5, 5)]) == Nothing
> traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)
> """

I think this example could be a bit confusing because both key and
value have the same type.  I suggest the following example:

  traverseWithKey
    (\k v -> if odd k then Just (succ v) else Nothing)
    (fromList [(1, 'a'), (3, 'e')])
   == Just (fromList [(1,'b'),(3,'f')])

>
> This is a rather useful function, and if we define it in SATed style
> and with an INLINE pragma (as in my attached patch), GHC can generate
> really good code for it at use sites.

I think we're moving away from INLINE in favour of INLIN[E]ABLE.  In
this case it seems fine since it's just building a closure +
tailcalling which probably would get optimised away.  Still, would
using INLINEABLE have a drawback in this case?