# 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`

):

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