# Self-normalizing applicative expressions

Normalize applicative expressions
by simplifying intermediate `pure`

and `(<$>)`

and reassociating `(<*>)`

.

This works by transforming the underlying applicative functor into one whose
operations (`pure`

, `(<$>)`

, `(<*>)`

) reassociate themselves by inlining
and beta-reduction.

It relies entirely on GHC's simplifier. No rewrite rules, no Template
Haskell, no plugins.
Only Haskell code with two common extensions: `GADTs`

and `RankNTypes`

.

## Example

In the following traversal, one of the actions is `pure b`

, which
can be simplified in principle, but only assuming the applicative functor
laws. As far as GHC is concerned, `pure`

, `(<$>)`

, and `(<*>)`

are
completely opaque because `f`

is abstract, so it cannot simplify this
expression.

```
data Example a = Example a Bool [a] (Example a)
traverseE :: Applicative f => (a -> f b) -> Example a -> f (Example b)
traverseE go (Example a b c d) =
Example
<$> go a
<*> pure b
<*> traverse go c
<*> traverseE go d
-- Total: 1 <$>, 3 <*>
```

Using this library, we can compose actions in a specialized applicative
functor `Aps f`

, keeping the code in roughly the same structure.

```
traverseE :: Applicative f => (a -> f b) -> Example a -> f (Example b)
traverseE go (Example a b c d) =
Example
<$>^ go a
<*> pure b
<*>^ traverse go c
<*>^ traverseE go d
& lowerAps
-- Total: 1 <$>, 3 <*>
```

GHC simplifies that traversal to the following, using only two
combinators in total.

```
traverseE :: Applicative f => (a -> f b) -> Example a -> f (Example b)
traverseE go (Example a b c d) =
liftA2 (\a' -> Example a' b)
(go a)
(traverse go c)
<*> traverseE go d
-- Total: 1 liftA2, 1 <*>
```

For more details see the `ApNormalize`

module.

## Related links

The same idea can be applied to monoids and monads.
They are all applications of Cayley's representation theorem.

`Endo`

to normalize `(<>)`

and `mempty`

, in *base*
`Codensity`

to normalize `pure`

and `(>>=)`

, in *kan-extensions*