Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell2010 |

# Normalizing applicative functors

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.

## 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 -- 1 <$>, 3 <*>

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

, keeping the code in roughly the same structure.
In the following snippet, identifiers exported by the library are highlighted.`Aps`

f

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`

-- 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 -- 1 liftA2, 1 <*>

The following example with a tree-shaped structure also reduces to the same list-shaped expression above.

traverseE :: Applicative f => (a -> f b) -> Example a -> f (Example b) traverseE go (Example a b c d) = (\((a', b'), (c', d')) -> Example a' b' c' d') <$> ((,) <$> ((,)`<$>^`

go a <*> pure b) <*> ((,)`<$>^`

traverse go c`<*>^`

traverseE go d))`&`

`lowerAps`

-- 4 <$>, 3 <*>

Such structure occurs when using an intermediate definition (which itself
uses the applicative operators) as the right operand of `(`

or
`<$>`

)`(`

.
This could also be found in a naive generic implementation of `<*>`

)`traverse`

using GHC.Generics.

## Usage

The main idea is to compose applicative actions not directly in your applicative
functor `f`

, but in a transformed one

.`Aps`

f

- Send actions from
`f`

into

using`Aps`

f`liftAps`

. `pure`

actions lift themselves already:`pure x`

can be specialized to both`f`

and`Aps f`

.- Compose actions in

using applicative combinators such as`Aps`

f`(`

,`<$>`

)`(`

, and`<*>`

)`liftA2`

. - Move back from

to`Aps`

f`f`

using`lowerAps`

.

The shorthands `(`

and `<$>^`

)`(`

can be used instead of
`<*>^`

)`(`

and `<$>`

)`(`

with a neighboring `<*>`

)`liftAps`

.

Definitions in

should not be recursive,
since this relies on inlining,
and recursive functions are not inlined by GHC.`Aps`

f

# Interface

An applicative functor transformer which accumulates `f`

-actions (things of type `f x`

)
in a normal form.

It constructs a value of type `f a`

with the following syntactic invariant.
It depends on the number of `f`

-actions `a1 ... an`

composing it,
which are delimited using `liftAps`

:

- Zero action:
`pure x`

- One action:
`f <$> a1`

- Two or more actions:
`liftA2 f a1 a2 <*> a3 <*> ... <*> an`

#### Instances

Functor (Aps f) Source # | |

Applicative f => Applicative (Aps f) Source # | |

(<$>^) :: (a -> b) -> f a -> Aps f b infixl 4 Source #

`f <$>^ u :: Aps f b`

is a delayed representation of `f <$> u :: f b`

,
so that it can be fused with other applicative operations.

`f <$>^ u`

is a shorthand for `f <$> `

.`liftAps`

u