# Incrementally solving the Applicative instance for Compose

by Ben Tefay, Senior Software Engineer

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`

):

`_fgb = _ <*> fga2b`

`_fgb = _ <*> fga`

`_fgb = _ <$> fga2b`

`_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.