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
usingAps
fliftAps
. pure
actions lift themselves already:pure x
can be specialized to bothf
andAps f
.- Compose actions in
using applicative combinators such asAps
f(
,<$>
)(
, and<*>
)liftA2
. - Move back from
toAps
ff
usinglowerAps
.
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