# Incrementally solving the Applicative instance for Compose

February 04, 2019 - Ben Tefay

Here at Stacktrace, our team have been working our way through the incredible (and incredibly challenging) Haskell data61 course. Last week we started working on the `Applicative` instance for `Compose`, and boy, it is much harder to implement than you might expect.

Lets have a look:

``````newtype Compose f g a = Compose (f (g a))

instance (Applicative f, Applicative g) => Applicative (Compose f g a) where
pure :: a -> Compose f g a
(<*>) :: Compose f g (a -> b) -> Compose f g a -> Compose f g b``````

There isn’t much going on, right? Just some `Compose`, `f`, `g`, `a` and `b`.

Well, I was in agony for what felt like a brain-melting hour before my colleague put me out of my misery and solved the hardest part for me. Just another day in the life of learning Haskell.

In fairness, `pure` is easy enough.

``````instance (Applicative f, Applicative g) => Applicative (Compose f g a) where
pure :: a -> Compose f g a``````

We just need to put an `a` in a `g`, and then put that `g a` in an `f`. Given `g` and `f` are `Applicatives`, we can call `pure` to create one of each `Applicative` and then wrap the result in `Compose`:

``pure a = Compose \$ pure \$ pure a``

Or, if we’re feeling a bit point free:

``pure = Compose . pure . pure``

In contrast `<*>` (“apply”, or more whimsically, “spaceship”) is hard.

Lets look at that signature again:

``````instance (Applicative f, Applicative g) => Applicative (Compose f g a) where
(<*>) :: Compose f g (a -> b) -> Compose f g a -> Compose f g b``````

It doesn’t look that hard, right? The problem is this: how on earth do you reach through `f` and `g`, to get hold of `a -> b` and `a`, so that you can actually apply them to each other and end up with `f (g b)`.

For the life of me, I couldn’t figure out how to solve this incrementally. That left me trying to solve it all at once, in my head. I failed.

To practice being more piecemeal with Haskell, let’s try to walk through this in a way that my past self would have appreciated.

To start, lets write the easy stuff. Since `Compose` is a `newtype` wrapper, we need to unwrap the contents of our two `Compose` arguments, and then put the result back in `Compose` at the end:

``````instance (Applicative f, Applicative g) => Applicative (Compose f g a) where
(<*>) :: Compose f g (a -> b) -> Compose f g a -> Compose f g b
Compose fga2b <*> Compose fga = Compose \$ _fgb``````

with the types:

``````fga2b :: f (g (a -> b))
fga :: f (g a)
_fgb :: f (g b)``````

The good news is that we’re now just dealing with `f`, `g`, `a` and `b`. The bad news is that it’s not obvious what to do next.

Lets try to break the problem down. We need to figure out what `_fgb` should be. Given `f` and `g` are `Applicative`s, we have four choices to start us off (ignoring `pure`, since the last thing we need is more nested `Applicatives`):

1. `_fgb = _ <*> fga2b`
2. `_fgb = _ <*> fga`
3. `_fgb = _ <\$> fga2b`
4. `_fgb = _ <\$> fga`

It can’t be `<\$>` (“fmap”), as we’ll end up inside `f` twice, once for `fga` and once for `fga2b`. So it must be `<*>`:

``````_fgb :: f (g b)
_fgb = _ <*> _``````

Whatever `_fgb` is, it needs to have a type of `f (g b)`. Given we’re calling `<*>`, where `<*> :: f (a -> b) -> f a -> f b`, we probably need a non-function on the right. That means we have to start with option (3): `_fgb = ? <*> fga`.

Now we’re getting somewhere:

``````instance (Applicative f, Applicative g) => Applicative (Compose f g a) where
(<*>) :: Compose f g (a -> b) -> Compose f g a -> Compose f g b
Compose fga2b <*> Compose fga = Compose \$ _fga2gb <*> fga``````

with the types:

``````fga2b :: f (g (a -> b))
fga :: f (g a)
_fga2gb :: f (g a -> g b)``````

We’ve already used `fga`, so that leaves us with `fga2b`. Can we transform `fga2b :: f (g (a -> b))` into `f (g a -> g b)`?

Lets try to do it in a separate function called `lessScary`:

``````Compose fga2b <*> Compose fga = Compose \$ lessScary fga2b <*> fga
where
lessScary :: f (g (a -> b)) -> f (g a -> g b)
lessScary fga2b = _somethingGoesHere``````

This seems a little more manageable. We need to transform the contents of `f` from `g (a -> b)` into `g a -> g b`. That feels like a job for `<\$>`!

``````(Compose fga2b) <*> (Compose fga) = Compose \$ lessScary fga2b <*> fga
where
lessScary :: f (g (a -> b)) -> f (g a -> g b)
lessScary fga2b = _somethingElseGoesHere <\$> fga2b``````

with the types:

``_somethingElseGoesHere :: g (a -> b) -> (g a -> g b)``

Yes yes yes! Lets break that `_somethingElseGoesHere` out into another function:

``````Compose fga2b <*> Compose fga = Compose \$ lessScary fga2b <*> fga
where
lessScary :: f (g (a -> b)) -> f (g a -> g b)
lessScary fga2b = whatThe <\$> fga2b
whatThe :: g (a -> b) -> g a -> g b
whatThe ga2b = _oneMoreThingGoesHere``````

Note that I’ve dropped the brackets around `(g a -> g b)` in `g (a -> b) -> (g a -> g b)`, since that’s actually the same as `g (a -> b) -> g a -> g b`.

You know what `g (a -> b) -> g a -> g b` looks like? Yup! It looks like `<*>` for `g`:

``````Compose fga2b <*> Compose fga = Compose \$ lessScary fga2b <*> fga
where
lessScary :: f (g (a -> b)) -> f (g a -> g b)
lessScary fga2b = whatThe <\$> fga2b
whatThe :: g (a -> b) -> g a -> g b
whatThe ga2b = (<*>) ga2b``````

That’s it! We did it.

We can take things further though, and condense a bunch of this code.

First, lets drop `ga2b` from `(<*>)` in `whatThe`, since it’s the first parameter to both:

``````Compose fga2b <*> Compose fga = Compose \$ lessScary fga2b <*> fga
where
lessScary :: f (g (a -> b)) -> f (g a -> g b)
lessScary fga2b = whatThe <\$> fga2b
whatThe :: g (a -> b) -> g a -> g b
whatThe = (<*>)``````

Now, lets inline `whatThe`:

``````Compose fga2b <*> Compose fga = Compose \$ lessScary fga2b <*> fga
where
lessScary :: f (g (a -> b)) -> f (g a -> g b)
lessScary fga2b = (<*>) <\$> fga2b``````

`lessScary` can be inlined too:

``Compose fga2b <*> Compose fga = Compose \$ (<*>) <\$> fga2b <*> fga``

And there we have it. The `Applicative` instance for `Compose`. In incremental steps.