Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

[Milan Straka]

Hi Edward,

> -----Original message-----
> From: Edward Kmett <ekmett at gmail.com>
> Sent: 6 Aug 2013, 13:38
>
> traverse and traverse_ visit elements in the same order as foldMap and
> foldr up to the Monoid/Applicative laws permitting (finite) reassociation
> and unit mapping.
> 
> It would stand to reason that traverseWithKey, traverseWithKey_,
> foldMapWithKey and foldrWithKey should retain that relationship.
> 
> I don't particularly care about what the order is, but that said, if you
> start breaking the invariant of the current ordering, you'll silently break
> a lot of people's code while still permitting it to typecheck.
> 
> This means that the errors will be insidious and difficult to find. e.g.
> the lens-based zipper code for walking into a Map will silently break and
> I'm sure I'm not the only one who has taken advantage of the existing
> ordering on these combinators.

I am not suggesting we should change the behaviour of existing functions
and traverseWithKey_ should definitely use the same order as
traverseWithKey. Changing semantics without changing type signatures is
really suspicious and usually plainly wrong.

Nevertheless, I was wondering whether we should have a monadic fold
(foldrM and foldlM) which would process the elements in a given order
(ascending and descending, analogously to foldr and foldl). From one
point of view, we can implement foldrM and foldlM using foldr and foldl,
nevertheless using linear heap space complexity compared to constant
heap space complexity we can achieve with specialized implementations.
This is the same situation as traverseWithKey_ -- we can implement it
using traverseWithKey, but the heap space complexity increases.

Cheers,
Milan