foldlWithKey in monad

Question

I'm looking for a function that like foldlWithKey, but encapsulated in a monad.

I would expect it to have type

Monad m => (a -> k -> b -> m a) -> a -> Map k b -> m a

but Hoogle isn't giving me anything with that type.

Answer 1

foldlWithKey is already very close to what you want. If you specialize a to m a you will have something that operates on values encapsulated in a monad.

foldlWithKey :: (  a -> k -> b ->   a) ->   a -> Map k b ->   a
foldlWithKey :: (m a -> k -> b -> m a) -> m a -> Map k b -> m a
             {-  ^- you don't want these -^   -}

We can get rid of the two m as you don't want with >>= and return.

foldlWithKeyM :: Monad m => (a -> k -> b -> m a) -> a -> Map k b -> m a
foldlWithKeyM f acc = foldlWithKey f' (return acc) 
    where
        f' ma k b = ma >>= \a -> f a k b

Answer 2

@Cirdec's solution certainly works, but it has a possible problem: It nests >>=s deeply leftwards. For many (but not all!) monads, this can give stack blowup similar to when using non-strict foldl. So I'll present a different solution, which nests >>=s rightwards instead. For monads such as IO this should allow the action to be constructed and consumed lazily from the map as it is executed.

This solution is probably a bit trickier, as it uses a right fold to build up the monadic function that will eventually consume the starting value. At least I had some trouble getting the types right.

Except for the key handling, this is essentially the same method as used by Data.Foldable.foldlM.

-- Pragma needed only to give f' a type signature for sanity.  Getting it 
-- right almost took a piece of mine until I remembered typed holes.
{-# LANGUAGE ScopedTypeVariables #-}

import Data.Map

foldlWithKeyM
  :: forall m a k b. Monad m => (a -> k -> b -> m a) -> a -> Map k b -> m a
foldlWithKeyM f start m = foldrWithKey f' return m $ start
  where
    f' :: k -> b -> (a -> m a) -> (a -> m a)
    f' k b a2mb a = f a k b >>= a2mb