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 theApplicative
methods, so everyApplicative
is a functor whether we like it or not; theFunctor
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 pure
ified 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 flip
ed 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.