-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Self-normalizing applicative expressions
--
-- An applicative functor transformer to normalize expressions using
-- (<$>), (<*>), and pure into a
-- linear list of actions. See ApNormalize to get started.
@package ap-normalize
@version 0.1.0.1
-- | This structure is part of the definition of Aps.
module ApNormalize.DList
-- | Type of applicative difference lists.
--
-- An applicative transformer which accumulates f-actions in a
-- left-nested composition using (<*>).
--
-- ApDList represents a sequence of f-actions u1 :: f
-- x1, ... un :: f xn as "term with a hole" (_
-- <*> u1 <*> ... <*> un) :: f r.
--
-- That hole must have type _ :: f (x1 -> ... -> un ->
-- r); the variable number of arrows is hidden by existential
-- quantification and continuation passing.
--
-- To help ensure that syntactic invariant, the Functor and
-- Applicative instances for ApDList have no constraints.
-- liftApDList is the only function whose signature requires an
-- Applicative f constraint, wrapping each action
-- u inside one (<*>).
newtype ApDList f a
ApDList :: (forall r. Yoneda f (a -> r) -> f r) -> ApDList f a
-- | A difference list with one element u, denoted _ <*>
-- u.
liftApDList :: Applicative f => f a -> ApDList f a
-- | Complete a difference list, filling the hole with the first argument.
lowerApDList :: Yoneda f (b -> c) -> ApDList f b -> f c
-- | A delayed application of fmap which can be fused with an inner
-- fmap or liftA2.
--
-- This is the same definition as in the kan-extensions library, but we
-- redefine it to not pay for all the dependencies.
newtype Yoneda f a
Yoneda :: (forall x. (a -> x) -> f x) -> Yoneda f a
instance GHC.Base.Functor (ApNormalize.DList.ApDList f)
instance GHC.Base.Applicative (ApNormalize.DList.ApDList f)
instance GHC.Base.Functor (ApNormalize.DList.Yoneda f)
-- | The definition of Aps. Most of this is reexported by
-- ApNormalize.
module ApNormalize.Aps
-- | 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
--
data Aps f a
[Pure] :: a -> Aps f a
[FmapLift] :: (x -> a) -> f x -> Aps f a
[LiftA2Aps] :: (x -> y -> z -> a) -> f x -> f y -> ApDList f z -> Aps f a
-- | 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.
(<$>^) :: (a -> b) -> f a -> Aps f b
infixl 4 <$>^
-- | u <*>^ v appends an f-action v to the
-- right of an (Aps f)-action u.
--
-- u <*>^ v is a shorthand for u <*>
-- liftAps v.
(<*>^) :: Applicative f => Aps f (a -> b) -> f a -> Aps f b
infixl 4 <*>^
-- | Lift an f-action into Aps f.
liftAps :: f a -> Aps f a
-- | Lower an f-action from Aps f.
lowerAps :: Applicative f => Aps f a -> f a
-- | Append an action to the left of an Aps.
liftA2Aps :: Applicative f => (a -> b -> c) -> f a -> Aps f b -> Aps f c
-- | Conversion from Aps to ApDList.
apsToApDList :: Applicative f => Aps f a -> ApDList f a
instance GHC.Base.Functor (ApNormalize.Aps.Aps f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (ApNormalize.Aps.Aps f)
-- | 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 Aps f, keeping the code in roughly
-- the same structure. In the following snippet, identifiers exported by
-- the library are highlighted.
--
--
-- 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 Aps f using
-- liftAps.
-- - pure actions lift themselves already: pure x can
-- be specialized to both f and Aps f.
-- - Compose actions in Aps f using applicative
-- combinators such as (<$>),
-- (<*>), and liftA2.
-- - Move back from Aps f to f using
-- lowerAps.
--
--
-- The shorthands (<$>^) and
-- (<*>^) can be used instead of
-- (<$>) and (<*>) with a
-- neighboring liftAps.
--
-- Definitions in Aps f should not be recursive, since
-- this relies on inlining, and recursive functions are not inlined by
-- GHC.
module ApNormalize
-- | 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
--
data Aps f a
-- | 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.
(<$>^) :: (a -> b) -> f a -> Aps f b
infixl 4 <$>^
-- | u <*>^ v appends an f-action v to the
-- right of an (Aps f)-action u.
--
-- u <*>^ v is a shorthand for u <*>
-- liftAps v.
(<*>^) :: Applicative f => Aps f (a -> b) -> f a -> Aps f b
infixl 4 <*>^
-- | Lift an f-action into Aps f.
liftAps :: f a -> Aps f a
-- | Lower an f-action from Aps f.
lowerAps :: Applicative f => Aps f a -> f a
-- | & is a reverse application operator. This provides
-- notational convenience. Its precedence is one higher than that of the
-- forward application operator $, which allows & to be
-- nested in $.
--
--
-- >>> 5 & (+1) & show
-- "6"
--
(&) :: a -> (a -> b) -> b
infixl 1 &