ap-normalize: Self-normalizing applicative expressions

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

An applicative functor transformer to normalize expressions using (<$>), (<*>), and pure into a linear list of actions. See ApNormalize to get started.


[Skip to Readme]

Properties

Versions 0.1.0.0, 0.1.0.0, 0.1.0.1
Change log None available
Dependencies base (>=4.8 && <5) [details]
License MIT
Copyright Li-yao Xia 2020
Author Li-yao Xia
Maintainer lysxia@gmail.com
Category Control
Bug tracker https://gitlab.com/lysxia/ap-normalize/-/issues
Uploaded by lyxia at 2020-08-05T20:50:22Z

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for ap-normalize-0.1.0.0

[back to package description]

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.

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