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

Hi Edward,

-----Original message----- From: Edward Kmett 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