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?

In general if you ever want to add more "context" than `map` will allow you, consider using either a fold or explicit recursion to traverse your data structure. — badcook, Apr 20 '16 at 14:39

score 10 · Accepted Answer · answered Apr 20 '16 at 15:18

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

For true inscrutability, ``myMapM = (`foldr` pure []) . (((<*>) . fmap (:)) .)`` — dfeuer, Apr 20 '16 at 18:14
i.e. `liftA2 (:) . f` in the `foldr`, to get a one-liner, and to avoid the scare brackets. :) — Will Ness, May 02 '19 at 06:13

score 3 · Answer 2 · edited May 02 '19 at 06:28

3

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 ;) )

edited May 02 '19 at 06:28

Will Ness

70,110
9
98
181

answered Apr 20 '16 at 11:26

Random Dev

51,810
9
92
119

2

You only need `Applicative m` to write `mapM` (aka `traverse`). `traverse f (x:xs) = (:) <$> f x <*> traverse f xs` – Benjamin Hodgson Apr 20 '16 at 11:56
@BenjaminHodgson told you it's *basic* - IMO it's a bit problematic to tell someone about `Traversable` if they struggle with monads (and I think most can handle `do` notations as they look familiar-imperative) - but why don't you add this as a nice answer? – Random Dev Apr 20 '16 at 12:29
we could have Monadic do... Applicative do... Functorial do! or in the other direction, [LiftF... LiftA2... liftBind](https://stackoverflow.com/a/53829742/849891). and yes, I think `do` notation could be the gateway drug to monads, and should even be presented much earlier than `>>=` or even the name "monad" is mentioned. Come to think of it, teaching Haskell should start with `main = do { putStrLn "Hello, World!"; return () }`! – Will Ness May 02 '19 at 06:49

score 2 · Answer 3 · answered Apr 20 '16 at 14:41

Maybe it helps when you start with implementing mapM with just >>= and return. You would end up with something similar to:

mapM' :: Monad m => (a -> m b) -> [a] -> m [b]
mapM' _ []     = return []
mapM' f (x:xs) =        f x           >>=
                 \y  -> mapM' f xs    >>=
                 \ys -> return (y:ys)

This kind of gives you the answer as the previous poster mentioned. All you need to do is change the order of arguments:

moppy :: (Misty m) => [a] -> (a -> m b) -> m [b]      
moppy []     _ = unicorn []
moppy (x:xs) f = banana (\y -> banana (\ys -> unicorn (y:ys)) (moppy xs f)) (f x)

Or:

moppy :: (Misty m) => [a] -> (a -> m b) -> m [b]      
moppy []     _ = unicorn []
moppy (x:xs) f = (\y  -> (\ys -> unicorn (y:ys)) `banana` moppy xs f) `banana` f x

Or:

moppy :: (Misty m) => [a] -> (a -> m b) -> m [b]      
moppy []     _ = unicorn []
moppy (x:xs) f = let g y = let h ys = unicorn (y : ys)
                            in h `banana` moppy xs f
                  in g `banana` f x

score 1 · Answer 4 · edited May 02 '19 at 06:21

1

Take this implementation:

moppy :: Monad m => (a -> m b) -> [a] -> m [b]
moppy f xs = foldr g n xs 
  where
    n = return []
    g x mys = do {
      y  <- f x ;
      ys <- mys ;
      return (y:ys) }

(mys :: m [b] because foldr g n (x:xs) = g x (foldr g n xs).)

(adapted from C9 Lectures: Ralf Lämmel - Going Bananas [8:06 min - youtube).

edited May 02 '19 at 06:21

Will Ness

70,110
9
98
181

answered May 01 '19 at 20:16

user3680029

179
8

Implement mapM without using sequence

4 Answers4