Implement mapM without using sequence

Question

I am currently trying to solve the 20 Intermediate Haskell Excercises excercises and am stuck which trying to implement mapM (which is moppy in the excercise) without the use of sequence.

All I can produce is a [m b] by simply applying fmap but I don't know how to continue:

moppy :: [a] -> (a -> m b) -> m [b]
moppy la f = furry' f la -- how do I transform [m b] to m [b] without sequence

Can someone give me a hint in which direction to look?

Answer 1

In the modern era, as Benjamin Hodgson mentioned, we should be using Applicative for this particular purpose:

myMapM :: Applicative f
       => (a -> f b) -> [a] -> f [b]

We want myMapM f [] to be pure [] (there's no way we can get any bs!), so

myMapM f [] = pure []

Now we get to the heart of the matter, figuring out the recursive step. We want myMapM f (x : xs) to perform f x, perform myMapM f xs, and combine the results. So

myMapM f [] = pure []
myMapM f (x : xs) = (:) <$> f x <*> myMapM f xs

When doing something nice and regular with a list, we can very often get away with just foldr:

myMapM f = foldr go (pure []) where
  go x r = (:) <$> f x <*> r

Answer 2

Well I don't know how to do this without too much spoiler -- so here you go with a very basic / recursive definition:

moppy :: Monad m => [a] -> (a -> m b) -> m [b]
moppy [] _ = return []
moppy (x:xs) f = do
  y  <- f x
  ys <- moppy xs f
  return (y:ys)

It should be rather self-explanatory -- please note that you need the Monad m constraint (I think you want it anyway, as it gets rather impossible without it ;) )