ap-normalize

Self-normalizing applicative expressions

Version on this page:0.1.0.0
LTS Haskell 22.14:0.1.0.1
Stackage Nightly 2024-03-28:0.1.0.1
Latest on Hackage:0.1.0.1

See all snapshots ap-normalize appears in

MIT licensed by Li-yao Xia
Maintained by [email protected]
This version can be pinned in stack with:ap-normalize-0.1.0.0@sha256:3475934c78f89228949ae4f9f669eddf8e09df29b12e08fbab0488511df1d4d1,1174

Module documentation for 0.1.0.0

Depends on 1 package(full list with versions):
Used by 1 package in nightly-2020-08-18(full list with versions):

Self-normalizing applicative expressions Hackage pipeline status

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