-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Self-normalizing applicative expressions
--   
--   An applicative functor transformer to normalize expressions using
--   <tt>(&lt;$&gt;)</tt>, <tt>(&lt;*&gt;)</tt>, and <tt>pure</tt> into a
--   linear list of actions. See <a>ApNormalize</a> to get started.
@package ap-normalize
@version 0.1.0.1


-- | This structure is part of the definition of <a>Aps</a>.
module ApNormalize.DList

-- | Type of applicative difference lists.
--   
--   An applicative transformer which accumulates <tt>f</tt>-actions in a
--   left-nested composition using <tt>(<a>&lt;*&gt;</a>)</tt>.
--   
--   <a>ApDList</a> represents a sequence of <tt>f</tt>-actions <tt>u1 :: f
--   x1</tt>, ... <tt>un :: f xn</tt> as "term with a hole" <tt>(_
--   &lt;*&gt; u1 &lt;*&gt; ... &lt;*&gt; un) :: f r</tt>.
--   
--   That hole must have type <tt>_ :: f (x1 -&gt; ... -&gt; un -&gt;
--   r)</tt>; the variable number of arrows is hidden by existential
--   quantification and continuation passing.
--   
--   To help ensure that syntactic invariant, the <a>Functor</a> and
--   <a>Applicative</a> instances for <a>ApDList</a> have no constraints.
--   <a>liftApDList</a> is the only function whose signature requires an
--   <tt><a>Applicative</a> f</tt> constraint, wrapping each action
--   <tt>u</tt> inside one <tt>(<a>&lt;*&gt;</a>)</tt>.
newtype ApDList (f :: Type -> Type) a
ApDList :: (forall r. () => Yoneda f (a -> r) -> f r) -> ApDList (f :: Type -> Type) a

-- | A difference list with one element <tt>u</tt>, denoted <tt>_ &lt;*&gt;
--   u</tt>.
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 <a>fmap</a> which can be fused with an inner
--   <a>fmap</a> or <a>liftA2</a>.
--   
--   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 :: Type -> Type) a
Yoneda :: (forall x. () => (a -> x) -> f x) -> Yoneda (f :: Type -> Type) a
instance GHC.Internal.Base.Applicative (ApNormalize.DList.ApDList f)
instance GHC.Internal.Base.Functor (ApNormalize.DList.ApDList f)
instance GHC.Internal.Base.Functor (ApNormalize.DList.Yoneda f)


-- | The definition of <a>Aps</a>. Most of this is reexported by
--   <a>ApNormalize</a>.
module ApNormalize.Aps

-- | An applicative functor transformer which accumulates
--   <tt>f</tt>-actions (things of type <tt>f x</tt>) in a normal form.
--   
--   It constructs a value of type <tt>f a</tt> with the following
--   syntactic invariant. It depends on the number of <tt>f</tt>-actions
--   <tt>a1 ... an</tt> composing it, which are delimited using
--   <a>liftAps</a>:
--   
--   <ul>
--   <li>Zero action: <tt>pure x</tt></li>
--   <li>One action: <tt>f &lt;$&gt; a1</tt></li>
--   <li>Two or more actions: <tt>liftA2 f a1 a2 &lt;*&gt; a3 &lt;*&gt; ...
--   &lt;*&gt; an</tt></li>
--   </ul>
data Aps (f :: Type -> Type) a
[Pure] :: forall a (f :: Type -> Type). a -> Aps f a
[FmapLift] :: forall x a (f :: Type -> Type). (x -> a) -> f x -> Aps f a
[LiftA2Aps] :: forall x y z a (f :: Type -> Type). (x -> y -> z -> a) -> f x -> f y -> ApDList f z -> Aps f a

-- | <tt>f &lt;$&gt;^ u :: Aps f b</tt> is a delayed representation of
--   <tt>f &lt;$&gt; u :: f b</tt>, so that it can be fused with other
--   applicative operations.
--   
--   <tt>f &lt;$&gt;^ u</tt> is a shorthand for <tt>f &lt;$&gt;
--   <a>liftAps</a> u</tt>.
(<$>^) :: (a -> b) -> f a -> Aps f b
infixl 4 <$>^

-- | <tt>u &lt;*&gt;^ v</tt> appends an <tt>f</tt>-action <tt>v</tt> to the
--   right of an <tt>(<a>Aps</a> f)</tt>-action <tt>u</tt>.
--   
--   <tt>u &lt;*&gt;^ v</tt> is a shorthand for <tt>u &lt;*&gt;
--   <a>liftAps</a> v</tt>.
(<*>^) :: Applicative f => Aps f (a -> b) -> f a -> Aps f b
infixl 4 <*>^

-- | Lift an <tt>f</tt>-action into <tt><a>Aps</a> f</tt>.
liftAps :: f a -> Aps f a

-- | Lower an <tt>f</tt>-action from <tt><a>Aps</a> f</tt>.
lowerAps :: Applicative f => Aps f a -> f a

-- | Append an action to the left of an <a>Aps</a>.
liftA2Aps :: Applicative f => (a -> b -> c) -> f a -> Aps f b -> Aps f c

-- | Conversion from <a>Aps</a> to <a>ApDList</a>.
apsToApDList :: forall (f :: Type -> Type) a. Applicative f => Aps f a -> ApDList f a
instance GHC.Internal.Base.Applicative f => GHC.Internal.Base.Applicative (ApNormalize.Aps.Aps f)
instance GHC.Internal.Base.Functor (ApNormalize.Aps.Aps f)


-- | <h1>Normalizing applicative functors</h1>
--   
--   Normalize applicative expressions by simplifying intermediate
--   <a>pure</a> and <tt>(<a>&lt;$&gt;</a>)</tt> and reassociating
--   <tt>(<a>&lt;*&gt;</a>)</tt>.
--   
--   This works by transforming the underlying applicative functor into one
--   whose operations (<a>pure</a>, <tt>(<a>&lt;$&gt;</a>)</tt>,
--   <tt>(<a>&lt;*&gt;</a>)</tt>) reassociate themselves by inlining and
--   beta-reduction.
--   
--   It relies entirely on GHC's simplifier. No rewrite rules, no Template
--   Haskell, no plugins.
--   
--   <h2>Example</h2>
--   
--   In the following traversal, one of the actions is <tt>pure b</tt>,
--   which can be simplified in principle, but only assuming the
--   applicative functor laws. As far as GHC is concerned, <a>pure</a>,
--   <tt>(<a>&lt;$&gt;</a>)</tt>, and <tt>(<a>&lt;*&gt;</a>)</tt> are
--   completely opaque because <tt>f</tt> is abstract, so it cannot
--   simplify this expression.
--   
--   <pre>
--   data Example a = Example a Bool [a] (Example a)
--   
--   traverseE :: Applicative f =&gt; (a -&gt; f b) -&gt; Example a -&gt; f (Example b)
--   traverseE go (Example a b c d) =
--     Example
--       &lt;$&gt; go a
--       &lt;*&gt; pure b
--       &lt;*&gt; traverse go c
--       &lt;*&gt; traverseE go d
--     -- 1 &lt;$&gt;, 3 &lt;*&gt;
--   </pre>
--   
--   Using this library, we can compose actions in a specialized
--   applicative functor <tt><a>Aps</a> f</tt>, keeping the code in roughly
--   the same structure. In the following snippet, identifiers exported by
--   the library are highlighted.
--   
--   <pre>
--   traverseE :: Applicative f =&gt; (a -&gt; f b) -&gt; Example a -&gt; f (Example b)
--   traverseE go (Example a b c d) =
--     Example
--       <a>&lt;$&gt;^</a> go a
--       &lt;*&gt;  pure b
--       <a>&lt;*&gt;^</a> traverse go c
--       <a>&lt;*&gt;^</a> traverseE go d
--       <a>&amp;</a> <a>lowerAps</a>
--     -- 1 &lt;$&gt;, 3 &lt;*&gt;
--   </pre>
--   
--   GHC simplifies that traversal to the following, using only two
--   combinators in total.
--   
--   <pre>
--   traverseE :: Applicative f =&gt; (a -&gt; f b) -&gt; Example a -&gt; f (Example b)
--   traverseE go (Example a b c d) =
--     liftA2 (\a' -&gt; Example a' b)
--       (go a)
--       (traverse go c)
--       &lt;*&gt; traverseE go d
--     -- 1 liftA2, 1 &lt;*&gt;
--   </pre>
--   
--   The following example with a tree-shaped structure also reduces to the
--   same list-shaped expression above.
--   
--   <pre>
--   traverseE :: Applicative f =&gt; (a -&gt; f b) -&gt; Example a -&gt; f (Example b)
--   traverseE go (Example a b c d) =
--     (\((a', b'), (c', d')) -&gt; Example a' b' c' d')
--       &lt;$&gt; ((,) &lt;$&gt; ((,) <a>&lt;$&gt;^</a> go a
--                         &lt;*&gt;  pure b)
--                &lt;*&gt; ((,) <a>&lt;$&gt;^</a> traverse go c
--                         <a>&lt;*&gt;^</a> traverseE go d))
--       <a>&amp;</a> <a>lowerAps</a>
--     -- 4 &lt;$&gt;, 3 &lt;*&gt;
--   </pre>
--   
--   Such structure occurs when using an intermediate definition (which
--   itself uses the applicative operators) as the right operand of
--   <tt>(<a>&lt;$&gt;</a>)</tt> or <tt>(<a>&lt;*&gt;</a>)</tt>. This could
--   also be found in a naive generic implementation of <a>traverse</a>
--   using <a>GHC.Generics</a>.
--   
--   <h2>Usage</h2>
--   
--   The main idea is to compose applicative actions not directly in your
--   applicative functor <tt>f</tt>, but in a transformed one
--   <tt><a>Aps</a> f</tt>.
--   
--   <ul>
--   <li>Send actions from <tt>f</tt> into <tt><a>Aps</a> f</tt> using
--   <a>liftAps</a>.</li>
--   <li><a>pure</a> actions lift themselves already: <tt>pure x</tt> can
--   be specialized to both <tt>f</tt> and <tt>Aps f</tt>.</li>
--   <li>Compose actions in <tt><a>Aps</a> f</tt> using applicative
--   combinators such as <tt>(<a>&lt;$&gt;</a>)</tt>,
--   <tt>(<a>&lt;*&gt;</a>)</tt>, and <a>liftA2</a>.</li>
--   <li>Move back from <tt><a>Aps</a> f</tt> to <tt>f</tt> using
--   <a>lowerAps</a>.</li>
--   </ul>
--   
--   The shorthands <tt>(<a>&lt;$&gt;^</a>)</tt> and
--   <tt>(<a>&lt;*&gt;^</a>)</tt> can be used instead of
--   <tt>(<a>&lt;$&gt;</a>)</tt> and <tt>(<a>&lt;*&gt;</a>)</tt> with a
--   neighboring <a>liftAps</a>.
--   
--   Definitions in <tt><a>Aps</a> f</tt> 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
--   <tt>f</tt>-actions (things of type <tt>f x</tt>) in a normal form.
--   
--   It constructs a value of type <tt>f a</tt> with the following
--   syntactic invariant. It depends on the number of <tt>f</tt>-actions
--   <tt>a1 ... an</tt> composing it, which are delimited using
--   <a>liftAps</a>:
--   
--   <ul>
--   <li>Zero action: <tt>pure x</tt></li>
--   <li>One action: <tt>f &lt;$&gt; a1</tt></li>
--   <li>Two or more actions: <tt>liftA2 f a1 a2 &lt;*&gt; a3 &lt;*&gt; ...
--   &lt;*&gt; an</tt></li>
--   </ul>
data Aps (f :: Type -> Type) a

-- | <tt>f &lt;$&gt;^ u :: Aps f b</tt> is a delayed representation of
--   <tt>f &lt;$&gt; u :: f b</tt>, so that it can be fused with other
--   applicative operations.
--   
--   <tt>f &lt;$&gt;^ u</tt> is a shorthand for <tt>f &lt;$&gt;
--   <a>liftAps</a> u</tt>.
(<$>^) :: (a -> b) -> f a -> Aps f b
infixl 4 <$>^

-- | <tt>u &lt;*&gt;^ v</tt> appends an <tt>f</tt>-action <tt>v</tt> to the
--   right of an <tt>(<a>Aps</a> f)</tt>-action <tt>u</tt>.
--   
--   <tt>u &lt;*&gt;^ v</tt> is a shorthand for <tt>u &lt;*&gt;
--   <a>liftAps</a> v</tt>.
(<*>^) :: Applicative f => Aps f (a -> b) -> f a -> Aps f b
infixl 4 <*>^

-- | Lift an <tt>f</tt>-action into <tt><a>Aps</a> f</tt>.
liftAps :: f a -> Aps f a

-- | Lower an <tt>f</tt>-action from <tt><a>Aps</a> f</tt>.
lowerAps :: Applicative f => Aps f a -> f a

-- | <a>&amp;</a> is a reverse application operator. This provides
--   notational convenience. Its precedence is one higher than that of the
--   forward application operator <a>$</a>, which allows <a>&amp;</a> to be
--   nested in <a>$</a>.
--   
--   This is a version of <tt><a>flip</a> <a>id</a></tt>, where <a>id</a>
--   is specialized from <tt>a -&gt; a</tt> to <tt>(a -&gt; b) -&gt; (a
--   -&gt; b)</tt> which by the associativity of <tt>(-&gt;)</tt> is <tt>(a
--   -&gt; b) -&gt; a -&gt; b</tt>. flipping this yields <tt>a -&gt; (a
--   -&gt; b) -&gt; b</tt> which is the type signature of <a>&amp;</a>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; 5 &amp; (+1) &amp; show
--   "6"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sqrt $ [1 / n^2 | n &lt;- [1..1000]] &amp; sum &amp; (*6)
--   3.1406380562059946
--   </pre>
(&) :: a -> (a -> b) -> b
infixl 1 &
