Hi Edward,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.

  traverseWithKey_ f = go
    where go Tip = pure ()
          go (Bin _ k v l r) = f k v *> go l *> go r

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,

foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
foldrM f z0 xs = foldl f' return xs z0
  where f' k x z = f x z >>= k

foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m a
foldlM f z0 xs = foldr f' return xs z0
  where f' x k z = f z x >>= k

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.