fmap in Applicative and Monad

While reading the Applicative section of Typeclassopedia I stumbled upon the line that said:

In fact, as we will see, fmap can be implemented using the Applicative methods, so every Applicative is a functor whether we like it or not; the Functor constraint forces us to be honest.

This got me curious as to whether or not I could figure out how to do this. I then wondered if it would also be possible to do using only Monad methods. If you don't want anything spoiled, I'd suggest not reading any further and trying to figure this out yourself.

Applicative

So starting with Applicative, I wanted to see what tools were available to me. Basically, we have the following:

(<*>) :: Applicative f => f (a -> b) -> f a -> f b
pure :: Applicative f => a -> f a  

Now, if it isn't obvious, (<*>) looks awfully similar to our target fmap:

fmap :: Functor f => (a -> b) -> f a -> f b  

the main difference being Applicative's (<*>) has the function lifted into Applicative. It seems logical that we could take a function (a -> b) and use pure in order to lift it to f (a -> b) after which we can just use (<*>) like so:

afmap :: Applicative f => (a -> b) -> f a -> f b  
afmap f x = pure f <*> x  

Nice and simple. But for bonus points, I decided to see if I could write this in point-free style. Dropping the x is really simple because we can just use sectioning to rewrite our function as such:

afmap :: Applicative f => (a -> b) -> f a -> f b  
afmap f = (pure f <*>)  

Now the interesting part is to get rid of the f. We obviously won't be able to use sectioning, but if we use (<*>) in its prefix form then we'll be able to pass the pureified function first:

afmap :: Applicative f => (a -> b) -> f a -> f b  
afmap f = (<*>) (pure f)  

So here we are extremely close. This pattern might not be recognizable at first, but if we substite the values the pattern should be immediately recognizable.

g = (<*>)  
h = pure

afmap x = g (h x)  

Looking at it like this, we can see this is just function composition or (.). If we rewrite our previous code using function composition, we get:

afmap :: Applicative f => (a -> b) -> f a -> f b  
afmap f = ((<*>) . pure) f  

And finally, we can drop the f and the parenthesis:

afmap :: Applicative f => (a -> b) -> f a -> f b  
afmap = (<*>) . pure  

And there we've succeeded in writing fmap using Applicative methods.

Monad

Let's see if we can do the same thing with Monad. I found this one to be a little bit more troublesome. In Monad we have the following:

(>>=) :: Monad m => m a -> (a -> m b) -> m b
return :: Monad m => a -> m a  

At first glance, we can see that (>>=) looks a lot like fmap as well, but the arguments are flipped. So if we flip it, then we'll have something that more closely resembles fmap:

flip (>>=) :: Monad m => (a -> m b) -> m a -> m b  

Additionally, we can just use (=<<) which is the fliped version of (>>=):

(=<<) :: Monad m => (a -> m b) -> m a -> m b

Looking at the first argument we have a function (a -> m b), so how would we take a function that looks like (a -> b) and turn it into a function (a -> m b). We essentially want something like:

foo :: (a -> b) -> (a -> m b)  

or, simplified

foo :: (a -> b) -> a -> m b  

Interestingly enough, if we can evaluate the function and get a b back, we can turn it into an m b with return, this looks like function composition again! Let's take a look at the type for (.):

(.) :: (b -> c) -> (a1 -> b) -> a1 -> c

I'm using a1 here to prevent a naming conflict later. Now, if we take a look at return again:

return :: Monad m => a -> m a  

If we apply return as the first argument to (.), we can then replace every b with an a and every c with an m a. Additionally, since we've applied the argument to (.), we need to also drop the (b -> c) part. Using sectioning again, we can get:

(return .) :: (a1 -> a) -> a1 -> m a

or rewritten

(return .) :: (a -> b) -> (a -> m b)

which is exactly what we wanted. We can now pass the result of this into (=<<) and we're done:

mfmap :: Monad m => (a -> b) -> m a -> m b  
mfmap f x = (=<<) (return . f) x  

Finally, for even more bonus points, let's make this point-free as well. Dropping the x is easy once again:

mfmap :: Monad m => (a -> b) -> m a -> m b  
mfmap f = (=<<) (return . f)  

and dropping the f is as easy as before if we do some renaming to recognize the pattern:

g = (=<<)  
h = (return .)

mfmap x = g (h x)  

So once again we can just use function composition to get:

mfmap :: Monad m => (a -> b) -> m a -> m b  
mfmap f = ((=<<) . (return .)) f  

and finally, we can drop the f and the extra parenthesis:

mfmap :: Monad m => (a -> b) -> m a -> m b  
mfmap = (=<<) . (return .)  

And there we have it, we were able to write fmap using both the Applicative and Monad methods and in point-free style at that. Of course, this doesn't really serve any real-world purpose as you would simply use fmap, but it is a neat exercise to see how these typeclasses are related and similarly to become more familiar with Haskell as a whole.