I also blog frequently on the Yesod Web Framework blog, as well as the FP Complete blog.

Follow up on mapM_

January 19, 2017

This is a short follow-up to my blog post about mapM_ and Maybe. Roman Cheplyaka started a discussion on that post, and ultimately we came up with the following implementation of mapM_ which works for all Foldables and avoids the non-tail-recursive case for Maybe as desired:

mapM_ :: (Applicative m, Foldable f) => (a -> m ()) -> f a -> m ()
mapM_ f a =
    go (toList a)
  where
    go [] = pure ()
    go [x] = f x -- here's the magic
    go (x:xs) = f x *> go xs

Why is this useful? If you implement mapM_ directly in terms of foldr or foldMap, there is no way to tell that you are currently looking at the last element in the structure, and therefore will always end up with the equivalent of f x *> pure () in your expanded code. By contrast, with explicit pattern matching on the list-ified version, we can easily pattern match with go [x] and avoid *> pure () bit, thereby making tail recursion possible.

Some interesting things to note:

  • Using () <$ f x instead of f x *> pure () or f x >> return () seemed to make no difference for tail recursion purposes.
  • As a result of that, we still need to have the ()-specialized type signature I describe in the previous blog post, there doesn't seem to be a way around that.
  • As you can see from the benchmark which I unceremoniously ripped off from Roman, there do not appear to be cases where this version has more memory residency than mapM_ from base. Roman had raised the concern that the intermediate list may involve extra allocations, though it appears that GHC is smart enough to avoid them.

Here are the results. Notice the significantly higher residency numbers for base:

   5000      roman          36,064 bytes
   5000    michael          36,064 bytes
   5000       base          36,064 bytes
  50000      roman          36,064 bytes
  50000    michael          36,064 bytes
  50000       base         133,200 bytes
 500000      roman          44,384 bytes
 500000    michael          44,384 bytes
 500000       base       2,354,216 bytes
5000000      roman          44,384 bytes
5000000    michael          44,384 bytes
5000000       base      38,235,176 bytes

My takeaway from all of this: it's probably too late to change the type signature of mapM_ and forM_ in base, but this alternative implementation is a good fit for mono-traversable. Perhaps there are some rewrite rules that could be applied in base to get the benefits of this implementation as well.

Completely tangential, but: as long as I'm linking to pull requests based on blog posts, I've put together a PR for classy-prelude and conduit-combinators that gets rid of generalized I/O operations, based on my readFile blog post.

Blog archive