CODEWITHSUNDEEP
haskellmonads
ThreeFx
ThreeFx

Reputation: 7360

Implement mapM without using sequence

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?

Upvotes: 4

Views: 892

Answers (4)

Random Dev
Random Dev

Reputation: 52280

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

Upvotes: 3

user3680029
user3680029

Reputation: 179

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

Upvotes: 1

dfeuer
dfeuer

Reputation: 48591

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

Upvotes: 10

Jasper
Jasper

Reputation: 76

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

Upvotes: 3

Related Questions