Normalize applicative expressions
by simplifying intermediate
(<$>) and reassociating
This works by transforming the underlying applicative functor into one whose
(<*>)) reassociate themselves by inlining
It relies entirely on GHC’s simplifier. No rewrite rules, no Template
Haskell, no plugins.
Only Haskell code with two common extensions:
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,
completely opaque because
f is abstract, so it cannot simplify this
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
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
The blog post Generic traversals with applicative difference lists gives an overview of the motivation and core data structure of this library.
The same idea can be applied to monoids and monads. They are all applications of Cayley’s representation theorem.
Latest version: https://gitlab.com/lysxia/ap-normalize/-/blob/main/CHANGELOG.md
- No library changes.
- Fix test suite to build with clang’s C preprocessor (default on MacOS).
- Create ap-normalize.