6

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.

Mathias Vorreiter Pedersen
  • 780
  • 8
  • 22

2 Answers2

11

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
Cirdec
  • 24,019
  • 2
  • 50
  • 100
8

@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
Ørjan Johansen
  • 18,119
  • 3
  • 43
  • 53
  • Equivalently could you not just wrap the monad in `ContT` for just this function? – luqui Apr 05 '15 at 08:25
  • @luqui I don't think that's quite equivalent, with a left fold you would still be *building up* the entire left-nested action before `ContT` could convert it. In particular it cannot be as lazy when consuming. – Ørjan Johansen Apr 05 '15 at 14:14
  • This is a great answer, but it would be great to explain some of the ideas/details. e.g. turning the original fold into a monadic fold actually means, we chain monadic actions. This way, it becomes clear that `pure` or `return` as the start value make sense. ... even though one wouldn't expect a function as a start value. Furthermore, `f'` can be rewritten to `f' k b a2mb = \a -> f a k b >>= a2mb` to match the type signature more directly, and also make the idea of chained monadic actions more explicit. – ruben.moor Dec 21 '22 at 16:11
  • Finally, the `$` is superfluous, but yes - `foldrWithKey f' return m` has type `a -> m a`, even though we applied 3 arguments, and thus it can be applied once more. – ruben.moor Dec 21 '22 at 16:12