[Haskell-cafe] mapM_ -> Monoid.Monad.map

[Dan Doel]

On Friday 23 January 2009 3:50:18 pm Henning Thielemann wrote:
>   I always considered the monad functions with names ending on '_' a
> concession to the IO monad. Would you need them for any other monad than
> IO? For self-written monads you would certainly use a monoid instead of
> monadic action, all returning (), but IO is a monad. (You could however
> wrap (newtype Output = Output (IO ())) and define a Monoid instance on
> Output.)
>   However our recent Monoid discussion made me think about mapM_,
> sequence_, and friends. I think they could be useful for many monads if
> they would have the type:
>   mapM_ :: (Monoid b) => (a -> m b) -> [a] -> m b
>    I expect that the Monoid instance of () would yield the same efficiency
> as todays mapM_ and it is also safer since it connects the monadic result
> types of the atomic and the sequenced actions. There was a recent
> discussion on the topic:

What is your proposed definition of the new mapM_? For instance:

  mapM_ f = foldr (liftM2 mappend) (return mempty)

Has exactly the same problem as mapM for the situations you'd actually want to 
use it (roughly, it's not monadically 'tail recursive'). You could instead 
have:

  mapM_ f = foldr (>>) (return mempty)

which does have the right behavior, but it doesn't naturally have the type you 
give above, and always returns mempty, which isn't much more useful than 
always returning ().

mapM_ is also useful in ST (perhaps not surprising) and strict State. It 
should be useful in other monads in which >>= implies a strict sequencing of 
evaluation, as it's the difference between:

  nonTail (x:xs) = do a <- foo x
                      b <- nonTail xs -- overflows for long lists
                      return $ f a b

and:

  tail (x:xs) = do foo x
                   tail xs

Even if f doesn't even look at its arguments, it leads to stack overflows for 
long lists in certain monads.

You can, of course, write a 'tail recursive' mapM by using an Endo m 
accumulator (to preseve ordering), and that might work out well enough, but I 
haven't thought much about it. In any case, I have a hard time believing IO is 
the *only* monad where you might want to write a loop purely for its side 
effects, but maybe I'm off the mark.

-- Dan