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


-- | Tools for functor combinator-based program design
--   
--   Tools for working with <i>functor combinators</i>: types that take
--   functors (or other indexed types) and returns a new functor that
--   "enhances" or "mixes" them in some way. In the process, you can design
--   featureful programs by composing smaller "primitives" using basic
--   unversal combinators.
--   
--   The main entry point is <a>Data.Functor.Combinators</a>, but more
--   fine-grained functionality and extra combinators (some of them
--   re-implementations for compatibility) are available in other modules
--   as well.
--   
--   This library does not define new functor combinators for the most
--   part, but rather re-exports them from different parts of the Haskell
--   ecosystem and provides a uniform interface.
--   
--   See the README for a quick overview, and also
--   <a>https://blog.jle.im/entry/functor-combinatorpedia.html</a> for an
--   in-depth dive into the motivation behind functor combinator-driven
--   development, examples of the functor combinators in this library, and
--   details about how to use these abstractions!
@package functor-combinators
@version 0.1.1.0


-- | This module provides functor combinators that are wrappers over lists
--   or maybes of <tt>f a</tt>s, especially for their <a>Interpret</a>
--   instances.
--   
--   Each one transforms a functor into some product of itself. For
--   example, <tt><a>NonEmptyF</a> f</tt> represents <tt>f <a>:*:</a>
--   f</tt>, or <tt>f :*: f :*: f</tt>, or <tt>f :*: f :*: f :*: f</tt>,
--   etc.
module Control.Applicative.ListF

-- | A list of <tt>f a</tt>s. Can be used to describe a product of many
--   different values of type <tt>f a</tt>.
--   
--   This is the Free <a>Plus</a>.
newtype ListF f a
ListF :: [f a] -> ListF f a
[runListF] :: ListF f a -> [f a]

-- | Map a function over the inside of a <a>ListF</a>.
mapListF :: ([f a] -> [g b]) -> ListF f a -> ListF g b

-- | A non-empty list of <tt>f a</tt>s. Can be used to describe a product
--   between many different possible values of type <tt>f a</tt>.
--   
--   Essentially:
--   
--   <pre>
--   <a>NonEmptyF</a> f
--       ~ f                          -- one f
--     <a>:+:</a> (f <a>:*:</a> f)              -- two f's
--     :+: (f :*: f :*: f)            -- three f's
--     :+: (f :*: f :*: f :*: f)      -- four f's
--     :+: ...                        -- etc.
--   </pre>
--   
--   This is the Free <a>Plus</a>.
newtype NonEmptyF f a
NonEmptyF :: NonEmpty (f a) -> NonEmptyF f a
[runNonEmptyF] :: NonEmptyF f a -> NonEmpty (f a)

-- | Map a function over the inside of a <a>NonEmptyF</a>.
mapNonEmptyF :: (NonEmpty (f a) -> NonEmpty (g b)) -> NonEmptyF f a -> NonEmptyF g b

-- | Convert a <a>NonEmptyF</a> into a <a>ListF</a> with at least one item.
toListF :: NonEmptyF f ~> ListF f

-- | Convert a <a>ListF</a> either a <a>NonEmptyF</a>, or a <a>Proxy</a> in
--   the case that the list was empty.
fromListF :: ListF f ~> (Proxy :+: NonEmptyF f)

-- | A maybe <tt>f a</tt>.
--   
--   Can be useful for describing a "an <tt>f a</tt> that may or may not be
--   there".
--   
--   This is the free structure for a "fail"-like typeclass that would only
--   have <tt>zero :: f a</tt>.
newtype MaybeF f a
MaybeF :: Maybe (f a) -> MaybeF f a
[runMaybeF] :: MaybeF f a -> Maybe (f a)

-- | Map a function over the inside of a <a>MaybeF</a>.
mapMaybeF :: (Maybe (f a) -> Maybe (g b)) -> MaybeF f a -> MaybeF g b

-- | Convert a <a>ListF</a> into a <a>MaybeF</a> containing the first <tt>f
--   a</tt> in the list, if it exists.
listToMaybeF :: ListF f ~> MaybeF f

-- | Convert a <a>MaybeF</a> into a <a>ListF</a> with zero or one items.
maybeToListF :: MaybeF f ~> ListF f

-- | A map of <tt>f a</tt>s, indexed by keys of type <tt>k</tt>. It can be
--   useful for represeting a product of many different values of type
--   <tt>f a</tt>, each "at" a different <tt>k</tt> location.
--   
--   Can be considered a combination of <a>EnvT</a> and <a>ListF</a>, in a
--   way --- a <tt><a>MapF</a> k f a</tt> is like a <tt><a>ListF</a>
--   (<a>EnvT</a> k f) a</tt> with unique (and ordered) keys.
--   
--   One use case might be to extend a schema with many "options", indexed
--   by some string.
--   
--   For example, if you had a command line argument parser for a single
--   command
--   
--   <pre>
--   data Command a
--   </pre>
--   
--   Then you can represent a command line argument parser for
--   <i>multiple</i> named commands with
--   
--   <pre>
--   type Commands = <a>MapF</a> <a>String</a> Command
--   </pre>
--   
--   See <a>NEMapF</a> for a non-empty variant, if you want to enforce that
--   your bag has at least one <tt>f a</tt>.
newtype MapF k f a
MapF :: Map k (f a) -> MapF k f a
[runMapF] :: MapF k f a -> Map k (f a)

-- | A non-empty map of <tt>f a</tt>s, indexed by keys of type <tt>k</tt>.
--   It can be useful for represeting a product of many different values of
--   type <tt>f a</tt>, each "at" a different <tt>k</tt> location, where
--   you need to have at least one <tt>f a</tt> at all times.
--   
--   Can be considered a combination of <a>EnvT</a> and <a>NonEmptyF</a>,
--   in a way --- an <tt><a>NEMapF</a> k f a</tt> is like a
--   <tt><a>NonEmptyF</a> (<a>EnvT</a> k f) a</tt> with unique (and
--   ordered) keys.
--   
--   See <a>MapF</a> for some use cases.
newtype NEMapF k f a
NEMapF :: NEMap k (f a) -> NEMapF k f a
[runNEMapF] :: NEMapF k f a -> NEMap k (f a)
instance (GHC.Classes.Ord k, Data.Functor.Classes.Ord1 f) => Data.Functor.Classes.Ord1 (Control.Applicative.ListF.NEMapF k f)
instance (GHC.Classes.Ord k, GHC.Read.Read k, Data.Functor.Classes.Read1 f) => Data.Functor.Classes.Read1 (Control.Applicative.ListF.NEMapF k f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Applicative.ListF.NEMapF k f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Applicative.ListF.NEMapF k f)
instance (GHC.Classes.Ord k, Data.Functor.Alt.Alt f) => GHC.Base.Semigroup (Control.Applicative.ListF.NEMapF k f a)
instance (GHC.Base.Functor f, GHC.Classes.Ord k) => Data.Functor.Alt.Alt (Control.Applicative.ListF.NEMapF k f)
instance (GHC.Base.Monoid k, Data.Pointed.Pointed f) => Data.Pointed.Pointed (Control.Applicative.ListF.NEMapF k f)
instance (GHC.Classes.Eq k, Data.Functor.Classes.Eq1 f) => Data.Functor.Classes.Eq1 (Control.Applicative.ListF.NEMapF k f)
instance (GHC.Show.Show k, Data.Functor.Classes.Show1 f) => Data.Functor.Classes.Show1 (Control.Applicative.ListF.NEMapF k f)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Data.Data k, Data.Data.Data (f a), GHC.Classes.Ord k) => Data.Data.Data (Control.Applicative.ListF.NEMapF k f a)
instance GHC.Generics.Generic (Control.Applicative.ListF.NEMapF k f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Applicative.ListF.NEMapF k f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Applicative.ListF.NEMapF k f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Applicative.ListF.NEMapF k f)
instance (GHC.Classes.Ord k, GHC.Classes.Ord (f a)) => GHC.Classes.Ord (Control.Applicative.ListF.NEMapF k f a)
instance (GHC.Classes.Eq k, GHC.Classes.Eq (f a)) => GHC.Classes.Eq (Control.Applicative.ListF.NEMapF k f a)
instance (GHC.Classes.Ord k, GHC.Read.Read k, GHC.Read.Read (f a)) => GHC.Read.Read (Control.Applicative.ListF.NEMapF k f a)
instance (GHC.Show.Show k, GHC.Show.Show (f a)) => GHC.Show.Show (Control.Applicative.ListF.NEMapF k f a)
instance (GHC.Classes.Ord k, Data.Functor.Classes.Ord1 f) => Data.Functor.Classes.Ord1 (Control.Applicative.ListF.MapF k f)
instance (GHC.Classes.Ord k, GHC.Read.Read k, Data.Functor.Classes.Read1 f) => Data.Functor.Classes.Read1 (Control.Applicative.ListF.MapF k f)
instance (GHC.Classes.Ord k, Data.Functor.Alt.Alt f) => GHC.Base.Semigroup (Control.Applicative.ListF.MapF k f a)
instance (GHC.Classes.Ord k, Data.Functor.Alt.Alt f) => GHC.Base.Monoid (Control.Applicative.ListF.MapF k f a)
instance (GHC.Base.Functor f, GHC.Classes.Ord k) => Data.Functor.Alt.Alt (Control.Applicative.ListF.MapF k f)
instance (GHC.Base.Functor f, GHC.Classes.Ord k) => Data.Functor.Plus.Plus (Control.Applicative.ListF.MapF k f)
instance (GHC.Base.Monoid k, Data.Pointed.Pointed f) => Data.Pointed.Pointed (Control.Applicative.ListF.MapF k f)
instance (GHC.Classes.Eq k, Data.Functor.Classes.Eq1 f) => Data.Functor.Classes.Eq1 (Control.Applicative.ListF.MapF k f)
instance (GHC.Show.Show k, Data.Functor.Classes.Show1 f) => Data.Functor.Classes.Show1 (Control.Applicative.ListF.MapF k f)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Data.Data k, Data.Data.Data (f a), GHC.Classes.Ord k) => Data.Data.Data (Control.Applicative.ListF.MapF k f a)
instance GHC.Generics.Generic (Control.Applicative.ListF.MapF k f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Applicative.ListF.MapF k f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Applicative.ListF.MapF k f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Applicative.ListF.MapF k f)
instance (GHC.Classes.Ord k, GHC.Classes.Ord (f a)) => GHC.Classes.Ord (Control.Applicative.ListF.MapF k f a)
instance (GHC.Classes.Eq k, GHC.Classes.Eq (f a)) => GHC.Classes.Eq (Control.Applicative.ListF.MapF k f a)
instance (GHC.Classes.Ord k, GHC.Read.Read k, GHC.Read.Read (f a)) => GHC.Read.Read (Control.Applicative.ListF.MapF k f a)
instance (GHC.Show.Show k, GHC.Show.Show (f a)) => GHC.Show.Show (Control.Applicative.ListF.MapF k f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Applicative.ListF.MaybeF f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Control.Applicative.ListF.MaybeF f)
instance GHC.Base.Functor f => Data.Functor.Alt.Alt (Control.Applicative.ListF.MaybeF f)
instance GHC.Base.Functor f => Data.Functor.Plus.Plus (Control.Applicative.ListF.MaybeF f)
instance GHC.Base.Applicative f => GHC.Base.Alternative (Control.Applicative.ListF.MaybeF f)
instance GHC.Base.Semigroup (Control.Applicative.ListF.MaybeF f a)
instance GHC.Base.Monoid (Control.Applicative.ListF.MaybeF f a)
instance Data.Pointed.Pointed f => Data.Pointed.Pointed (Control.Applicative.ListF.MaybeF f)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Applicative.ListF.MaybeF f)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Applicative.ListF.MaybeF f)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Applicative.ListF.MaybeF f)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Data.Data (f a)) => Data.Data.Data (Control.Applicative.ListF.MaybeF f a)
instance GHC.Generics.Generic (Control.Applicative.ListF.MaybeF f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Applicative.ListF.MaybeF f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Applicative.ListF.MaybeF f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Applicative.ListF.MaybeF f)
instance GHC.Classes.Ord (f a) => GHC.Classes.Ord (Control.Applicative.ListF.MaybeF f a)
instance GHC.Classes.Eq (f a) => GHC.Classes.Eq (Control.Applicative.ListF.MaybeF f a)
instance GHC.Read.Read (f a) => GHC.Read.Read (Control.Applicative.ListF.MaybeF f a)
instance GHC.Show.Show (f a) => GHC.Show.Show (Control.Applicative.ListF.MaybeF f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Applicative.ListF.NonEmptyF f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Control.Applicative.ListF.NonEmptyF f)
instance GHC.Base.Functor f => Data.Functor.Alt.Alt (Control.Applicative.ListF.NonEmptyF f)
instance GHC.Base.Semigroup (Control.Applicative.ListF.NonEmptyF f a)
instance Data.Pointed.Pointed f => Data.Pointed.Pointed (Control.Applicative.ListF.NonEmptyF f)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Applicative.ListF.NonEmptyF f)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Applicative.ListF.NonEmptyF f)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Applicative.ListF.NonEmptyF f)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Data.Data (f a)) => Data.Data.Data (Control.Applicative.ListF.NonEmptyF f a)
instance GHC.Generics.Generic (Control.Applicative.ListF.NonEmptyF f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Applicative.ListF.NonEmptyF f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Applicative.ListF.NonEmptyF f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Applicative.ListF.NonEmptyF f)
instance GHC.Classes.Ord (f a) => GHC.Classes.Ord (Control.Applicative.ListF.NonEmptyF f a)
instance GHC.Classes.Eq (f a) => GHC.Classes.Eq (Control.Applicative.ListF.NonEmptyF f a)
instance GHC.Read.Read (f a) => GHC.Read.Read (Control.Applicative.ListF.NonEmptyF f a)
instance GHC.Show.Show (f a) => GHC.Show.Show (Control.Applicative.ListF.NonEmptyF f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Applicative.ListF.ListF f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Apply (Control.Applicative.ListF.ListF f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Control.Applicative.ListF.ListF f)
instance GHC.Base.Functor f => Data.Functor.Alt.Alt (Control.Applicative.ListF.ListF f)
instance GHC.Base.Functor f => Data.Functor.Plus.Plus (Control.Applicative.ListF.ListF f)
instance GHC.Base.Applicative f => GHC.Base.Alternative (Control.Applicative.ListF.ListF f)
instance GHC.Base.Semigroup (Control.Applicative.ListF.ListF f a)
instance GHC.Base.Monoid (Control.Applicative.ListF.ListF f a)
instance Data.Pointed.Pointed f => Data.Pointed.Pointed (Control.Applicative.ListF.ListF f)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Applicative.ListF.ListF f)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Applicative.ListF.ListF f)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Applicative.ListF.ListF f)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Data.Data (f a)) => Data.Data.Data (Control.Applicative.ListF.ListF f a)
instance GHC.Generics.Generic (Control.Applicative.ListF.ListF f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Applicative.ListF.ListF f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Applicative.ListF.ListF f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Applicative.ListF.ListF f)
instance GHC.Classes.Ord (f a) => GHC.Classes.Ord (Control.Applicative.ListF.ListF f a)
instance GHC.Classes.Eq (f a) => GHC.Classes.Eq (Control.Applicative.ListF.ListF f a)
instance GHC.Read.Read (f a) => GHC.Read.Read (Control.Applicative.ListF.ListF f a)
instance GHC.Show.Show (f a) => GHC.Show.Show (Control.Applicative.ListF.ListF f a)


-- | The church-encoded <a>Freer</a> Monad. Basically provides the free
--   monad in a way that is compatible with <a>HFunctor</a> and
--   <a>Interpret</a>. We also have the "semigroup" version <a>Free1</a>,
--   which is the free <a>Bind</a>.
--   
--   The module also provides a version of <a>:.:</a> (or <a>Compose</a>),
--   <a>Comp</a>, in a way that is compatible with <a>HBifunctor</a> and
--   the related typeclasses.
module Control.Monad.Freer.Church

-- | A <tt><a>Free</a> f</tt> is <tt>f</tt> enhanced with "sequential
--   binding" capabilities. It allows you to sequence multiple <tt>f</tt>s
--   one after the other, and also to determine "what <tt>f</tt> to
--   sequence" based on the result of the computation so far.
--   
--   Essentially, you can think of this as "giving <tt>f</tt> a
--   <a>Monad</a> instance", with all that that entails (<a>return</a>,
--   <a>&gt;&gt;=</a>, etc.).
--   
--   Lift <tt>f</tt> into it with <tt><a>inject</a> :: f a -&gt; Free f
--   a</tt>. When you finally want to "use" it, you can interpret it into
--   any monadic context:
--   
--   <pre>
--   <a>interpret</a>
--       :: <a>Monad</a> g
--       =&gt; (forall x. f x -&gt; g x)
--       -&gt; <a>Free</a> f a
--       -&gt; g a
--   </pre>
--   
--   Structurally, this is equivalent to many "nested" f's. A value of type
--   <tt><a>Free</a> f a</tt> is either:
--   
--   <ul>
--   <li><pre>a</pre></li>
--   <li><pre>f a</pre></li>
--   <li><pre>f (f a)</pre></li>
--   <li><pre>f (f (f a))</pre></li>
--   <li>.. etc.</li>
--   </ul>
--   
--   Under the hood, this is the Church-encoded Freer monad. It's
--   <a>Free</a>, or <a>F</a>, but in a way that is compatible with
--   <a>HFunctor</a> and <a>Interpret</a>.
newtype Free f a
Free :: (forall r. (a -> r) -> (forall s. f s -> (s -> r) -> r) -> r) -> Free f a
[runFree] :: Free f a -> forall r. (a -> r) -> (forall s. f s -> (s -> r) -> r) -> r

-- | Convert a <tt><a>Free</a> f</tt> into any instance of
--   <tt><a>MonadFree</a> f</tt>.
reFree :: (MonadFree f m, Functor f) => Free f a -> m a

-- | Lift an <tt>f</tt> into <tt><a>Free</a> f</tt>, so you can use it as a
--   <a>Monad</a>.
--   
--   This is <a>inject</a>.
liftFree :: f ~> Free f

-- | Interpret a <tt><a>Free</a> f</tt> into a context <tt>g</tt>, provided
--   that <tt>g</tt> has a <a>Monad</a> instance.
--   
--   This is <a>interpret</a>.
interpretFree :: Monad g => (f ~> g) -> Free f ~> g

-- | Extract the <tt>f</tt>s back "out" of a <tt><a>Free</a> f</tt>,
--   utilizing its <a>Monad</a> instance.
--   
--   This is <a>retract</a>.
retractFree :: Monad f => Free f ~> f

-- | Swap out the underlying functor over a <a>Free</a>. This preserves all
--   of the structure of the <a>Free</a>.
hoistFree :: (f ~> g) -> Free f ~> Free g

-- | Recursively fold down a <a>Free</a> by handling the <a>pure</a> case
--   and the nested/wrapped case.
--   
--   This is a catamorphism.
--   
--   This requires <tt><a>Functor</a> f</tt>; see <a>foldFree'</a> and
--   <a>foldFreeC</a> for a version that doesn't require <tt><a>Functor</a>
--   f</tt>.
foldFree :: Functor f => (a -> r) -> (f r -> r) -> Free f a -> r

-- | A version of <a>foldFree</a> that doesn't require <tt><a>Functor</a>
--   f</tt>, by taking a RankN folding function. This is essentially a
--   flipped <a>runFree</a>.
foldFree' :: (a -> r) -> (forall s. f s -> (s -> r) -> r) -> Free f a -> r

-- | A version of <a>foldFree</a> that doesn't require <tt><a>Functor</a>
--   f</tt>, by folding over a <a>Coyoneda</a> instead.
foldFreeC :: (a -> r) -> (Coyoneda f r -> r) -> Free f a -> r

-- | The Free <a>Bind</a>. Imbues any functor <tt>f</tt> with a <a>Bind</a>
--   instance.
--   
--   Conceptually, this is "<a>Free</a> without pure". That is, while
--   normally <tt><a>Free</a> f a</tt> is an <tt>a</tt>, a <tt>f a</tt>, a
--   <tt>f (f a)</tt>, etc., a <tt><a>Free1</a> f a</tt> is an <tt>f
--   a</tt>, <tt>f (f a)</tt>, <tt>f (f (f a))</tt>, etc. It's a
--   <a>Free</a> with "at least one layer of <tt>f</tt>", excluding the
--   <tt>a</tt> case.
--   
--   It can be useful as the semigroup formed by <a>:.:</a> (functor
--   composition): Sometimes we want an <tt>f :.: f</tt>, or an <tt>f :.: f
--   :.: f</tt>, or an <tt>f :.: f :.: f :.: f</tt>...just as long as we
--   have at least one <tt>f</tt>.
newtype Free1 f a
Free1 :: (forall r. (forall s. f s -> (s -> a) -> r) -> (forall s. f s -> (s -> r) -> r) -> r) -> Free1 f a
[runFree1] :: Free1 f a -> forall r. (forall s. f s -> (s -> a) -> r) -> (forall s. f s -> (s -> r) -> r) -> r

-- | Convert a <tt><a>Free1</a> f</tt> into any instance of
--   <tt><a>MonadFree</a> f</tt>.
reFree1 :: (MonadFree f m, Functor f) => Free1 f a -> m a

-- | <tt><a>Free1</a> f</tt> is a special subset of <tt><a>Free</a> f</tt>
--   that consists of at least one nested <tt>f</tt>. This converts it back
--   into the "bigger" type.
--   
--   See <a>free1Comp</a> for a version that preserves the "one nested
--   layer" property.
toFree :: Free1 f ~> Free f

-- | Inject an <tt>f</tt> into a <tt><a>Free1</a> f</tt>
liftFree1 :: f ~> Free1 f

-- | Interpret the <tt><a>Free1</a> f</tt> in some context <tt>g</tt>,
--   provided that <tt>g</tt> has a <a>Bind</a> instance. Since we always
--   have at least one <tt>f</tt>, we will always have at least one
--   <tt>g</tt>, so we do not need a full <a>Monad</a> constraint.
interpretFree1 :: Bind g => (f ~> g) -> Free1 f ~> g

-- | Retract the <tt>f</tt> out of a <tt><a>Free1</a> f</tt>, as long as
--   the <tt>f</tt> implements <a>Bind</a>. Since we always have at least
--   one <tt>f</tt>, we do not need a full <a>Monad</a> constraint.
retractFree1 :: Bind f => Free1 f ~> f

-- | Map the underlying functor under a <a>Free1</a>.
hoistFree1 :: (f ~> g) -> Free1 f ~> Free1 g

-- | Because a <tt><a>Free1</a> f</tt> is just a <tt><a>Free</a> f</tt>
--   with at least one nested layer of <tt>f</tt>, this function converts
--   it back into the one-nested-<tt>f</tt> format.
free1Comp :: Free1 f ~> Comp f (Free f)

-- | A <tt><a>Free1</a> f</tt> is either a single un-nested <tt>f</tt>, or
--   a <tt>f</tt> nested with another <tt><a>Free1</a> f</tt>. This decides
--   which is the case.
matchFree1 :: forall f. Functor f => Free1 f ~> (f :+: Comp f (Free1 f))

-- | Recursively fold down a <a>Free1</a> by handling the single <tt>f</tt>
--   case and the nested/wrapped case.
--   
--   This is a catamorphism.
--   
--   This requires <tt><a>Functor</a> f</tt>; see <a>foldFree'</a> and
--   <a>foldFreeC</a> for a version that doesn't require <tt><a>Functor</a>
--   f</tt>.
foldFree1 :: Functor f => (f a -> r) -> (f r -> r) -> Free1 f a -> r

-- | A version of <a>foldFree1</a> that doesn't require <tt><a>Functor</a>
--   f</tt>, by taking a RankN folding function. This is essentially a
--   flipped <a>runFree</a>.
foldFree1' :: (forall s. f s -> (s -> a) -> r) -> (forall s. f s -> (s -> r) -> r) -> Free1 f a -> r

-- | A version of <a>foldFree1</a> that doesn't require <tt><a>Functor</a>
--   f</tt>, by folding over a <a>Coyoneda</a> instead.
foldFree1C :: (Coyoneda f a -> r) -> (Coyoneda f r -> r) -> Free1 f a -> r

-- | Functor composition. <tt><a>Comp</a> f g a</tt> is equivalent to <tt>f
--   (g a)</tt>, and the <a>Comp</a> pattern synonym is a way of getting
--   the <tt>f (g a)</tt> in a <tt><a>Comp</a> f g a</tt>.
--   
--   For example, <tt><a>Maybe</a> (<a>IO</a> <a>Bool</a>)</tt> is
--   <tt><a>Comp</a> <a>Maybe</a> <a>IO</a> <a>Bool</a></tt>.
--   
--   This is mostly useful for its typeclass instances: in particular,
--   <a>Functor</a>, <a>Applicative</a>, <a>HBifunctor</a>, and
--   <a>Monoidal</a>.
--   
--   This is essentially a version of <a>:.:</a> and <a>Compose</a> that
--   allows for an <a>HBifunctor</a> instance.
--   
--   It is slightly less performant. Using <tt><a>comp</a> .
--   <a>unComp</a></tt> every once in a while will concretize a <a>Comp</a>
--   value (if you have <tt><a>Functor</a> f</tt>) and remove some
--   indirection if you have a lot of chained operations.
--   
--   The "free monoid" over <a>Comp</a> is <a>Free</a>, and the "free
--   semigroup" over <a>Comp</a> is <a>Free1</a>.
data Comp f g a
(:>>=) :: f x -> (x -> g a) -> Comp f g a

-- | "Smart constructor" for <a>Comp</a> that doesn't require
--   <tt><a>Functor</a> f</tt>.
comp :: f (g a) -> Comp f g a
instance GHC.Base.Functor g => GHC.Base.Functor (Control.Monad.Freer.Church.Comp f g)
instance (GHC.Base.Applicative f, GHC.Base.Applicative g) => GHC.Base.Applicative (Control.Monad.Freer.Church.Comp f g)
instance (Data.Foldable.Foldable f, Data.Foldable.Foldable g) => Data.Foldable.Foldable (Control.Monad.Freer.Church.Comp f g)
instance (Data.Traversable.Traversable f, Data.Traversable.Traversable g) => Data.Traversable.Traversable (Control.Monad.Freer.Church.Comp f g)
instance (GHC.Base.Alternative f, GHC.Base.Alternative g) => GHC.Base.Alternative (Control.Monad.Freer.Church.Comp f g)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 g) => Data.Functor.Classes.Show1 (Control.Monad.Freer.Church.Comp f g)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 g, GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Freer.Church.Comp f g a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 g) => Data.Functor.Classes.Read1 (Control.Monad.Freer.Church.Comp f g)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 g, GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Freer.Church.Comp f g a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 g) => Data.Functor.Classes.Eq1 (Control.Monad.Freer.Church.Comp f g)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 g) => Data.Functor.Classes.Ord1 (Control.Monad.Freer.Church.Comp f g)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 g, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Freer.Church.Comp f g a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 g, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Freer.Church.Comp f g a)
instance GHC.Base.Functor (Control.Monad.Freer.Church.Free1 f)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Freer.Church.Free1 f)
instance Data.Functor.Bind.Class.Bind (Control.Monad.Freer.Church.Free1 f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Freer.Church.Free1 f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Freer.Church.Free1 f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Monad.Freer.Church.Free1 f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Freer.Church.Free1 f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f) => Data.Functor.Classes.Eq1 (Control.Monad.Freer.Church.Free1 f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f) => Data.Functor.Classes.Ord1 (Control.Monad.Freer.Church.Free1 f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Freer.Church.Free1 f a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Freer.Church.Free1 f a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f) => Data.Functor.Classes.Show1 (Control.Monad.Freer.Church.Free1 f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f, GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Freer.Church.Free1 f a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f) => Data.Functor.Classes.Read1 (Control.Monad.Freer.Church.Free1 f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f, GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Freer.Church.Free1 f a)
instance GHC.Base.Functor (Control.Monad.Freer.Church.Free f)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Freer.Church.Free f)
instance GHC.Base.Applicative (Control.Monad.Freer.Church.Free f)
instance Data.Pointed.Pointed (Control.Monad.Freer.Church.Free f)
instance Data.Functor.Bind.Class.Bind (Control.Monad.Freer.Church.Free f)
instance GHC.Base.Monad (Control.Monad.Freer.Church.Free f)
instance Control.Monad.Free.Class.MonadFree f (Control.Monad.Freer.Church.Free f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Freer.Church.Free f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Freer.Church.Free f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f) => Data.Functor.Classes.Eq1 (Control.Monad.Freer.Church.Free f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f) => Data.Functor.Classes.Ord1 (Control.Monad.Freer.Church.Free f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Freer.Church.Free f a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Freer.Church.Free f a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f) => Data.Functor.Classes.Show1 (Control.Monad.Freer.Church.Free f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Show1 f, GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Freer.Church.Free f a)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f) => Data.Functor.Classes.Read1 (Control.Monad.Freer.Church.Free f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 f, GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Freer.Church.Free f a)


-- | Types describing isomorphisms between two functors, and functions to
--   manipulate them.
module Control.Natural.IsoF

-- | A natural transformation from <tt>f</tt> to <tt>g</tt>.
type (~>) (f :: k -> Type) (g :: k -> Type) = forall (x :: k). () => f x -> g x
infixr 0 ~>

-- | The type of an isomorphism between two functors. <tt>f
--   <a>&lt;~&gt;</a> g</tt> means that <tt>f</tt> and <tt>g</tt> are
--   isomorphic to each other.
--   
--   We can effectively <i>use</i> an <tt>f &lt;~&gt; g</tt> with:
--   
--   <pre>
--   <a>viewF</a>   :: (f &lt;~&gt; g) -&gt; f a -&gt; g a
--   <a>reviewF</a> :: (f &lt;~&gt; g) -&gt; g a -&gt; a a
--   </pre>
--   
--   Use <a>viewF</a> to extract the "<tt>f</tt> to <tt>g</tt>" function,
--   and <a>reviewF</a> to extract the "<tt>g</tt> to <tt>f</tt>" function.
--   Reviewing and viewing the same value (or vice versa) leaves the value
--   unchanged.
--   
--   One nice thing is that we can compose isomorphisms using <a>.</a> from
--   <a>Prelude</a>:
--   
--   <pre>
--   (<a>.</a>) :: f &lt;~&gt; g
--       -&gt; g &lt;~&gt; h
--       -&gt; f &lt;~&gt; h
--   </pre>
--   
--   Another nice thing about this representation is that we have the
--   "identity" isomorphism by using <a>id</a> from <a>Prelude</a>.
--   
--   <pre>
--   <a>id</a> :: f <a>&lt;~&gt;</a> g
--   </pre>
--   
--   As a convention, most isomorphisms have form "X-ing", where the
--   forwards function is "ing". For example, we have:
--   
--   <pre>
--   <a>splittingSF</a> :: <a>Monoidal</a> t =&gt; <a>SF</a> t a <a>&lt;~&gt;</a> t f (<a>MF</a> t f)
--   <a>splitSF</a>     :: Monoidal t =&gt; SF t a  <a>~&gt;</a> t f (MF t f)
--   </pre>
type f <~> g = forall p a. Profunctor p => p (g a) (g a) -> p (f a) (f a)
infixr 0 <~>

-- | Create an <tt>f <a>&lt;~&gt;</a> g</tt> by providing both legs of the
--   isomorphism (the <tt>f a -&gt; g a</tt> and the <tt>g a -&gt; f
--   a</tt>.
isoF :: (f ~> g) -> (g ~> f) -> f <~> g

-- | Use a <a>&lt;~&gt;</a> by retrieving the "forward" function:
--   
--   <pre>
--   <a>viewF</a>   :: (f <a>~</a> g) -&gt; f a -&gt; g a
--   </pre>
viewF :: (f <~> g) -> f ~> g

-- | Use a <a>&lt;~&gt;</a> by retrieving the "backwards" function:
--   
--   <pre>
--   <a>viewF</a>   :: (f <a>~</a> g) -&gt; f a -&gt; g a
--   </pre>
reviewF :: (f <~> g) -> g ~> f

-- | Lift a function <tt>g a ~&gt; g a</tt> to be a function <tt>f a -&gt;
--   f a</tt>, given an isomorphism between the two.
--   
--   One neat thing is that <tt><a>overF</a> i id == id</tt>.
overF :: (f <~> g) -> (g ~> g) -> f ~> f

-- | Reverse an isomorphism.
--   
--   <pre>
--   <a>viewF</a>   (<a>fromF</a> i) == <a>reviewF</a> i
--   <a>reviewF</a> (<a>fromF</a> i) == <a>viewF</a> i
--   </pre>
fromF :: (f <~> g) -> g <~> f

-- | Profunctor that allows us to implement <a>fromF</a>.
data Exchange a b s t
Exchange :: (s -> a) -> (b -> t) -> Exchange a b s t
instance GHC.Base.Functor (Control.Natural.IsoF.Exchange a b s)
instance Data.Profunctor.Unsafe.Profunctor (Control.Natural.IsoF.Exchange a b)


-- | This module provides functor combinators that are the fixed points of
--   applications of <a>:+:</a> and <a>These1</a>. They are useful for
--   their <a>Interpret</a> instances, along with their relationship to the
--   <a>Monoidal</a> instances of <a>:+:</a> and <a>These1</a>.
module Control.Applicative.Step

-- | An <tt>f a</tt>, along with a <a>Natural</a> index.
--   
--   <pre>
--   <a>Step</a> f a ~ (<a>Natural</a>, f a)
--   Step f   ~ ((,) Natural) <a>:.:</a> f       -- functor composition
--   </pre>
--   
--   It is the fixed point of infinite applications of <a>:+:</a> (functor
--   sums).
--   
--   Intuitively, in an infinite <tt>f :+: f :+: f :+: f ...</tt>, you have
--   exactly one <tt>f</tt> <i>somewhere</i>. A <tt><a>Step</a> f a</tt>
--   has that <tt>f</tt>, with a <a>Natural</a> giving you "where" the
--   <tt>f</tt> is in the long chain.
--   
--   Can be useful for using with the <a>Monoidal</a> instance of
--   <a>:+:</a>.
--   
--   <a>interpret</a>ing it requires no constraint on the target context.
--   
--   Note that this type and its instances equivalent to <tt><a>EnvT</a>
--   (<a>Sum</a> <a>Natural</a>)</tt>.
data Step f a
Step :: Natural -> f a -> Step f a
[stepPos] :: Step f a -> Natural
[stepVal] :: Step f a -> f a

-- | A non-empty map of <a>Natural</a> to <tt>f a</tt>. Basically, contains
--   multiple <tt>f a</tt>s, each at a given <a>Natural</a> index.
--   
--   <pre>
--   Steps f a ~ <a>Map</a> <a>Natural</a> (f a)
--   Steps f   ~ <a>Map</a> <a>Natural</a> <a>:.:</a> f       -- functor composition
--   </pre>
--   
--   It is the fixed point of applications of <a>TheseT</a>.
--   
--   You can think of this as an infinite sparse array of <tt>f a</tt>s.
--   
--   Intuitively, in an infinite <tt>f `TheseT` f `TheseT` f `TheseT` f
--   ...</tt>, each of those infinite positions may have an <tt>f</tt> in
--   them. However, because of the at-least-one nature of <a>TheseT</a>, we
--   know we have at least one f at one position <i>somewhere</i>.
--   
--   A <tt><a>Steps</a> f a</tt> has potentially many <tt>f</tt>s, each
--   stored at a different <a>Natural</a> position, with the guaruntee that
--   at least one <tt>f</tt> exists.
--   
--   Can be useful for using with the <a>Monoidal</a> instance of
--   <a>TheseT</a>.
--   
--   <a>interpret</a>ing it requires at least an <a>Alt</a> instance in the
--   target context, since we have to handle potentially more than one
--   <tt>f</tt>.
--   
--   This type is essentailly the same as <tt><a>NEMapF</a> (<a>Sum</a>
--   <a>Natural</a>)</tt> (except with a different <a>Semigroup</a>
--   instance).
newtype Steps f a
Steps :: NEMap Natural (f a) -> Steps f a
[getSteps] :: Steps f a -> NEMap Natural (f a)

-- | An <tt>f a</tt>, along with a <a>Bool</a> flag
--   
--   <pre>
--   <a>Flagged</a> f a ~ (<a>Bool</a>, f a)
--   Flagged f   ~ ((,) Bool) <a>:.:</a> f       -- functor composition
--   </pre>
--   
--   Creation with <a>inject</a> or <a>pure</a> uses <a>False</a> as the
--   boolean.
--   
--   You can think of it as an <tt>f a</tt> that is "flagged" with a
--   boolean value, and that value can indicuate whether or not it is
--   "pure" (made with <a>inject</a> or <a>pure</a>) as <a>False</a>, or
--   "impure" (made from some other source) as <a>True</a>. However,
--   <a>False</a> may be always created directly, of course, using the
--   constructor.
--   
--   You can think of it like a <a>Step</a> that is either 0 or 1, as well.
--   
--   <a>interpret</a>ing it requires no constraint on the target context.
--   
--   This type is equivalent (along with its instances) to:
--   
--   <ul>
--   <li><pre><a>HLift</a> <a>IdentityT</a></pre></li>
--   <li><pre><a>EnvT</a> <a>Any</a></pre></li>
--   </ul>
data Flagged f a
Flagged :: Bool -> f a -> Flagged f a
[flaggedFlag] :: Flagged f a -> Bool
[flaggedVal] :: Flagged f a -> f a

-- | Unshift an item into a <a>Step</a>. Because a <tt><a>Step</a> f</tt>
--   is <tt>f :+: f :+: f :+: f :+: ...</tt> forever, this basically conses
--   an additional possibility of <tt>f</tt> to the beginning of it all.
--   
--   You can think of it as reassociating
--   
--   <pre>
--   f :+: ( f :+: f :+: f :+: ...)
--   </pre>
--   
--   into
--   
--   <pre>
--   f :+: f :+: f :+: f :+: ...
--   </pre>
--   
--   <pre>
--   <a>stepUp</a> (<a>L1</a> "hello")
--   -- <a>Step</a> 0 "hello"
--   stepUp (<a>R1</a> (Step 1 "hello"))
--   -- Step 2 "hello"
--   </pre>
--   
--   Forms an isomorphism with <a>stepDown</a> (see <a>stepping</a>).
stepUp :: (f :+: Step f) ~> Step f

-- | Pop off the first item in a <a>Step</a>. Because a <tt><a>Step</a>
--   f</tt> is <tt>f :+: f :+: f :+: ...</tt> forever, this matches on the
--   first branch.
--   
--   You can think of it as reassociating
--   
--   <pre>
--   f :+: f :+: f :+: f :+: ...
--   </pre>
--   
--   into
--   
--   <pre>
--   f :+: ( f :+: f :+: f :+: ...)
--   </pre>
--   
--   <pre>
--   <a>stepDown</a> (<a>Step</a> 2 "hello")
--   -- <a>R1</a> (Step 1 "hello")
--   stepDown (Step 0 "hello")
--   -- <a>L1</a> "hello"
--   </pre>
--   
--   Forms an isomorphism with <a>stepUp</a> (see <a>stepping</a>).
stepDown :: Step f ~> (f :+: Step f)

-- | "Uncons and cons" an <tt>f</tt> branch before a <a>Step</a>. This is
--   basically a witness that <a>stepDown</a> and <a>stepUp</a> form an
--   isomorphism.
stepping :: Step f <~> (f :+: Step f)

-- | Unshift an item into a <a>Steps</a>. Because a <tt><a>Steps</a> f</tt>
--   is <tt>f <a>These1</a> f <a>These1</a> f <a>These1</a> f <a>These1</a>
--   ...</tt> forever, this basically conses an additional possibility of
--   <tt>f</tt> to the beginning of it all.
--   
--   You can think of it as reassociating
--   
--   <pre>
--   f <a>These1</a> ( f <a>These1</a> f <a>These1</a> f <a>These1</a> ...)
--   </pre>
--   
--   into
--   
--   <pre>
--   f <a>These1</a> f <a>These1</a> f <a>These1</a> f <a>These1</a> ...
--   </pre>
--   
--   If you give:
--   
--   <ul>
--   <li><a>This1</a>, then it returns a singleton <a>Steps</a> with one
--   item at index 0</li>
--   <li><a>That1</a>, then it shifts every item in the given <a>Steps</a>
--   up one index.</li>
--   <li><a>These1</a>, then it shifts every item in the given <a>Steps</a>
--   up one index, and adds the given item (the <tt>f</tt>) at index
--   zero.</li>
--   </ul>
--   
--   Forms an isomorphism with <a>stepDown</a> (see <a>stepping</a>).
stepsUp :: These1 f (Steps f) ~> Steps f

-- | Pop off the first item in a <a>Steps</a>. Because a <tt><a>Steps</a>
--   f</tt> is <tt>f <a>These1</a> f <a>These1</a> f <a>These1</a> ...</tt>
--   forever, this matches on the first branch.
--   
--   You can think of it as reassociating
--   
--   <pre>
--   f <a>These1</a> f <a>These1</a> f <a>These1</a> f <a>These1</a> ...
--   </pre>
--   
--   into
--   
--   <pre>
--   f <a>These1</a> ( f <a>These1</a> f <a>These1</a> f <a>These1</a> ...)
--   </pre>
--   
--   It returns:
--   
--   <ul>
--   <li><a>This1</a> if the first item is the <i>only</i> item in the
--   <a>Steps</a></li>
--   <li><a>That1</a> if the first item in the <a>Steps</a> is empty, but
--   there are more items left. The extra items are all shfited down.</li>
--   <li><a>These1</a> if the first item in the <a>Steps</a> exists, and
--   there are also more items left. The extra items are all shifted
--   down.</li>
--   </ul>
--   
--   Forms an isomorphism with <a>stepsUp</a> (see <a>steppings</a>).
stepsDown :: Steps f ~> These1 f (Steps f)

-- | "Uncons and cons" an <tt>f</tt> branch before a <a>Steps</a>. This is
--   basically a witness that <a>stepsDown</a> and <a>stepsUp</a> form an
--   isomorphism.
steppings :: Steps f <~> These1 f (Steps f)

-- | We have a natural transformation between <a>V1</a> and any other
--   functor <tt>f</tt> with no constraints.
absurd1 :: V1 a -> f a

-- | <tt><a>Void2</a> a b</tt> is uninhabited for all <tt>a</tt> and
--   <tt>b</tt>.
data Void2 a b

-- | If you treat a <tt><a>Void2</a> f a</tt> as a functor combinator, then
--   <a>absurd2</a> lets you convert from a <tt><a>Void2</a> f a</tt> into
--   a <tt>t f a</tt> for any functor combinator <tt>t</tt>.
absurd2 :: Void2 f a -> t f a

-- | <tt><a>Void3</a> a b</tt> is uninhabited for all <tt>a</tt> and
--   <tt>b</tt>.
data Void3 a b c

-- | If you treat a <tt><a>Void3</a> f a</tt> as a binary functor
--   combinator, then <a>absurd3</a> lets you convert from a
--   <tt><a>Void3</a> f a</tt> into a <tt>t f a</tt> for any functor
--   combinator <tt>t</tt>.
absurd3 :: Void3 f g a -> t f g a
instance forall k1 k2 (a :: k2) (b :: k1). Data.Functor.Classes.Ord1 (Control.Applicative.Step.Void3 a b)
instance forall k1 k2 k3 (a :: k3) (b :: k2) (c :: k1). GHC.Base.Semigroup (Control.Applicative.Step.Void3 a b c)
instance forall k1 k2 (a :: k2) (b :: k1). Data.Functor.Alt.Alt (Control.Applicative.Step.Void3 a b)
instance forall k1 k2 (a :: k2) (b :: k1). Data.Functor.Bind.Class.Bind (Control.Applicative.Step.Void3 a b)
instance forall k1 k2 (a :: k2) (b :: k1). Data.Functor.Bind.Class.Apply (Control.Applicative.Step.Void3 a b)
instance forall k1 k2 (a :: k2) (b :: k1). Data.Functor.Classes.Eq1 (Control.Applicative.Step.Void3 a b)
instance forall k1 k2 (a :: k2) (b :: k1). Data.Functor.Classes.Read1 (Control.Applicative.Step.Void3 a b)
instance forall k1 k2 (a :: k2) (b :: k1). Data.Functor.Classes.Show1 (Control.Applicative.Step.Void3 a b)
instance forall k1 (a :: k1) k2 (b :: k2) k3 (c :: k3). (Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable b, Data.Typeable.Internal.Typeable c, Data.Typeable.Internal.Typeable k1, Data.Typeable.Internal.Typeable k2, Data.Typeable.Internal.Typeable k3) => Data.Data.Data (Control.Applicative.Step.Void3 a b c)
instance forall k1 (a :: k1) k2 (b :: k2) k3 (c :: k3). GHC.Generics.Generic (Control.Applicative.Step.Void3 a b c)
instance forall k1 (a :: k1) k2 (b :: k2). Data.Traversable.Traversable (Control.Applicative.Step.Void3 a b)
instance forall k1 (a :: k1) k2 (b :: k2). Data.Foldable.Foldable (Control.Applicative.Step.Void3 a b)
instance forall k1 (a :: k1) k2 (b :: k2). GHC.Base.Functor (Control.Applicative.Step.Void3 a b)
instance forall k1 (a :: k1) k2 (b :: k2) k3 (c :: k3). GHC.Classes.Ord (Control.Applicative.Step.Void3 a b c)
instance forall k1 (a :: k1) k2 (b :: k2) k3 (c :: k3). GHC.Classes.Eq (Control.Applicative.Step.Void3 a b c)
instance forall k1 (a :: k1) k2 (b :: k2) k3 (c :: k3). GHC.Read.Read (Control.Applicative.Step.Void3 a b c)
instance forall k1 (a :: k1) k2 (b :: k2) k3 (c :: k3). GHC.Show.Show (Control.Applicative.Step.Void3 a b c)
instance forall k (a :: k). Data.Functor.Classes.Ord1 (Control.Applicative.Step.Void2 a)
instance forall k1 k2 (a :: k2) (b :: k1). GHC.Base.Semigroup (Control.Applicative.Step.Void2 a b)
instance forall k (a :: k). Data.Functor.Alt.Alt (Control.Applicative.Step.Void2 a)
instance forall k (a :: k). Data.Functor.Bind.Class.Bind (Control.Applicative.Step.Void2 a)
instance forall k (a :: k). Data.Functor.Bind.Class.Apply (Control.Applicative.Step.Void2 a)
instance forall k (a :: k). Data.Functor.Classes.Eq1 (Control.Applicative.Step.Void2 a)
instance forall k (a :: k). Data.Functor.Classes.Read1 (Control.Applicative.Step.Void2 a)
instance forall k (a :: k). Data.Functor.Classes.Show1 (Control.Applicative.Step.Void2 a)
instance forall k1 (a :: k1) k2 (b :: k2). (Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable b, Data.Typeable.Internal.Typeable k1, Data.Typeable.Internal.Typeable k2) => Data.Data.Data (Control.Applicative.Step.Void2 a b)
instance forall k1 (a :: k1) k2 (b :: k2). GHC.Generics.Generic (Control.Applicative.Step.Void2 a b)
instance forall k (a :: k). Data.Traversable.Traversable (Control.Applicative.Step.Void2 a)
instance forall k (a :: k). Data.Foldable.Foldable (Control.Applicative.Step.Void2 a)
instance forall k (a :: k). GHC.Base.Functor (Control.Applicative.Step.Void2 a)
instance forall k1 (a :: k1) k2 (b :: k2). GHC.Classes.Ord (Control.Applicative.Step.Void2 a b)
instance forall k1 (a :: k1) k2 (b :: k2). GHC.Classes.Eq (Control.Applicative.Step.Void2 a b)
instance forall k1 (a :: k1) k2 (b :: k2). GHC.Read.Read (Control.Applicative.Step.Void2 a b)
instance forall k1 (a :: k1) k2 (b :: k2). GHC.Show.Show (Control.Applicative.Step.Void2 a b)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Applicative.Step.Flagged f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Control.Applicative.Step.Flagged f)
instance Data.Pointed.Pointed f => Data.Pointed.Pointed (Control.Applicative.Step.Flagged f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Applicative.Step.Flagged f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Applicative.Step.Flagged f)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Applicative.Step.Flagged f)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Applicative.Step.Flagged f)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Applicative.Step.Flagged f)
instance forall k (f :: k -> *) (a :: k). (Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable k, Data.Data.Data (f a)) => Data.Data.Data (Control.Applicative.Step.Flagged f a)
instance forall k (f :: k -> *) (a :: k). GHC.Generics.Generic (Control.Applicative.Step.Flagged f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Applicative.Step.Flagged f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Applicative.Step.Flagged f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Applicative.Step.Flagged f)
instance forall k (f :: k -> *) (a :: k). GHC.Classes.Ord (f a) => GHC.Classes.Ord (Control.Applicative.Step.Flagged f a)
instance forall k (f :: k -> *) (a :: k). GHC.Classes.Eq (f a) => GHC.Classes.Eq (Control.Applicative.Step.Flagged f a)
instance forall k (f :: k -> *) (a :: k). GHC.Read.Read (f a) => GHC.Read.Read (Control.Applicative.Step.Flagged f a)
instance forall k (f :: k -> *) (a :: k). GHC.Show.Show (f a) => GHC.Show.Show (Control.Applicative.Step.Flagged f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Applicative.Step.Steps f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Applicative.Step.Steps f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Applicative.Step.Steps f)
instance forall k (f :: k -> *) (a :: k). GHC.Base.Semigroup (Control.Applicative.Step.Steps f a)
instance GHC.Base.Functor f => Data.Functor.Alt.Alt (Control.Applicative.Step.Steps f)
instance Data.Pointed.Pointed f => Data.Pointed.Pointed (Control.Applicative.Step.Steps f)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Applicative.Step.Steps f)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Applicative.Step.Steps f)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Applicative.Step.Steps f)
instance forall k (f :: k -> *) (a :: k). (Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable k, Data.Data.Data (f a)) => Data.Data.Data (Control.Applicative.Step.Steps f a)
instance forall k (f :: k -> *) (a :: k). GHC.Generics.Generic (Control.Applicative.Step.Steps f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Applicative.Step.Steps f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Applicative.Step.Steps f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Applicative.Step.Steps f)
instance forall k (f :: k -> *) (a :: k). GHC.Classes.Ord (f a) => GHC.Classes.Ord (Control.Applicative.Step.Steps f a)
instance forall k (f :: k -> *) (a :: k). GHC.Classes.Eq (f a) => GHC.Classes.Eq (Control.Applicative.Step.Steps f a)
instance forall k (f :: k -> *) (a :: k). GHC.Read.Read (f a) => GHC.Read.Read (Control.Applicative.Step.Steps f a)
instance forall k (f :: k -> *) (a :: k). GHC.Show.Show (f a) => GHC.Show.Show (Control.Applicative.Step.Steps f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Applicative.Step.Step f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Control.Applicative.Step.Step f)
instance Data.Pointed.Pointed f => Data.Pointed.Pointed (Control.Applicative.Step.Step f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Applicative.Step.Step f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Applicative.Step.Step f)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Applicative.Step.Step f)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Applicative.Step.Step f)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Applicative.Step.Step f)
instance forall k (f :: k -> *) (a :: k). (Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable k, Data.Data.Data (f a)) => Data.Data.Data (Control.Applicative.Step.Step f a)
instance forall k (f :: k -> *) (a :: k). GHC.Generics.Generic (Control.Applicative.Step.Step f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Applicative.Step.Step f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Applicative.Step.Step f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Applicative.Step.Step f)
instance forall k (f :: k -> *) (a :: k). GHC.Classes.Ord (f a) => GHC.Classes.Ord (Control.Applicative.Step.Step f a)
instance forall k (f :: k -> *) (a :: k). GHC.Classes.Eq (f a) => GHC.Classes.Eq (Control.Applicative.Step.Step f a)
instance forall k (f :: k -> *) (a :: k). GHC.Read.Read (f a) => GHC.Read.Read (Control.Applicative.Step.Step f a)
instance forall k (f :: k -> *) (a :: k). GHC.Show.Show (f a) => GHC.Show.Show (Control.Applicative.Step.Step f a)


-- | Working with non-standard typeclasses like <a>Plus</a>, <a>Apply</a>,
--   <a>Bind</a>, and <a>Pointed</a> will sometimes cause problems when
--   using with libraries that do not provide instances, even though their
--   types already are instances of <a>Alternative</a> or
--   <a>Applicative</a> or <a>Monad</a>.
--   
--   This module provides unsafe methods to "promote" <a>Applicative</a>
--   instances to <a>Apply</a>, <a>Alternative</a> to <a>Plus</a>, etc.
--   
--   They are unsafe in the sense that if those types <i>already</i> have
--   those instances, this will cause overlapping instances errors or
--   problems with coherence. Because of this, you should always use these
--   with <i>specific</i> <tt>f</tt>s, and never in a polymorphic way over
--   <tt>f</tt>.
module Data.Functor.Combinator.Unsafe

-- | For any <tt><a>Alternative</a> f</tt>, produce a value that would
--   require <tt><a>Plus</a> f</tt>.
--   
--   Always use with concrete and specific <tt>f</tt> only, and never use
--   with any <tt>f</tt> that already has a <a>Plus</a> instance.
--   
--   See documentation for <a>upgradeC</a> for example usages.
--   
--   The <a>Proxy</a> argument allows you to specify which specific
--   <tt>f</tt> you want to enhance. You can pass in something like
--   <tt><a>Proxy</a> @MyFunctor</tt>.
unsafePlus :: forall f proxy r. Alternative f => proxy f -> (Plus f => r) -> r

-- | For any <tt><a>Applicative</a> f</tt>, produce a value that would
--   require <tt><a>Apply</a> f</tt>.
--   
--   Always use with concrete and specific <tt>f</tt> only, and never use
--   with any <tt>f</tt> that already has a <a>Apply</a> instance.
--   
--   See documentation for <a>upgradeC</a> for example usages.
--   
--   The <a>Proxy</a> argument allows you to specify which specific
--   <tt>f</tt> you want to enhance. You can pass in something like
--   <tt><a>Proxy</a> @MyFunctor</tt>.
unsafeApply :: forall f proxy r. Applicative f => proxy f -> (Apply f => r) -> r

-- | For any <tt><a>Monad</a> f</tt>, produce a value that would require
--   <tt><a>Bind</a> f</tt>.
--   
--   Always use with concrete and specific <tt>f</tt> only, and never use
--   with any <tt>f</tt> that already has a <a>Bind</a> instance.
--   
--   See documentation for <a>upgradeC</a> for example usages.
--   
--   The <a>Proxy</a> argument allows you to specify which specific
--   <tt>f</tt> you want to enhance. You can pass in something like
--   <tt><a>Proxy</a> @MyFunctor</tt>.
unsafeBind :: forall f proxy r. Monad f => proxy f -> (Bind f => r) -> r

-- | For any <tt><a>Applicative</a> f</tt>, produce a value that would
--   require <tt><a>Pointed</a> f</tt>.
--   
--   Always use with concrete and specific <tt>f</tt> only, and never use
--   with any <tt>f</tt> that already has a <a>Pointed</a> instance.
--   
--   See documentation for <a>upgradeC</a> for example usages.
--   
--   The <a>Proxy</a> argument allows you to specify which specific
--   <tt>f</tt> you want to enhance. You can pass in something like
--   <tt><a>Proxy</a> @MyFunctor</tt>.
unsafePointed :: forall f proxy r. Applicative f => proxy f -> (Pointed f => r) -> r
instance GHC.Base.Applicative f => Data.Pointed.Pointed (Data.Functor.Combinator.Unsafe.PointMe f)


-- | This module provides abstractions for working with unary functor
--   combinators.
--   
--   Principally, it defines the <a>HFunctor</a> itself, as well as some
--   classes that expose extra functionality that some <a>HFunctor</a>s
--   have (<a>Inject</a> and <a>HBind</a>).
--   
--   See <a>Data.HFunctor.Interpret</a> for tools to use <a>HFunctor</a>s
--   as functor combinators that can represent interpretable schemas, and
--   <a>Data.HBifunctor</a> for an abstraction over <i>binary</i> functor
--   combinators.
module Data.HFunctor

-- | An <a>HFunctor</a> can be thought of a unary "functor transformer" ---
--   a basic functor combinator. It takes a functor as input and returns a
--   functor as output.
--   
--   It "enhances" a functor with extra structure (sort of like how a monad
--   transformer enhances a <a>Monad</a> with extra structure).
--   
--   As a uniform inteface, we can "swap the underlying functor" (also
--   sometimes called "hoisting"). This is what <a>hmap</a> does: it lets
--   us swap out the <tt>f</tt> in a <tt>t f</tt> for a <tt>t g</tt>.
--   
--   For example, the free monad <a>Free</a> takes a <a>Functor</a> and
--   returns a new <a>Functor</a>. In the process, it provides a monadic
--   structure over <tt>f</tt>. <a>hmap</a> lets us turn a <tt><a>Free</a>
--   f</tt> into a <tt><a>Free</a> g</tt>: a monad built over <tt>f</tt>
--   can be turned into a monad built over <tt>g</tt>.
--   
--   For the ability to move in and out of the enhanced functor, see
--   <a>Inject</a> and <a>Interpret</a>.
--   
--   This class is similar to <a>MFunctor</a> from
--   <a>Control.Monad.Morph</a>, but instances must work without a
--   <a>Monad</a> constraint.
class HFunctor t

-- | If we can turn an <tt>f</tt> into a <tt>g</tt>, then we can turn a
--   <tt>t f</tt> into a <tt>t g</tt>.
--   
--   It must be the case that
--   
--   <pre>
--   <a>hmap</a> <a>id</a> == id
--   </pre>
--   
--   Essentially, <tt>t f</tt> adds some "extra structure" to <tt>f</tt>.
--   <a>hmap</a> must swap out the functor, <i>without affecting the added
--   structure</i>.
--   
--   For example, <tt><a>ListF</a> f a</tt> is essentially a list of <tt>f
--   a</tt>s. If we <a>hmap</a> to swap out the <tt>f a</tt>s for <tt>g
--   a</tt>s, then we must ensure that the "added structure" (here, the
--   number of items in the list, and the ordering of those items) remains
--   the same. So, <a>hmap</a> must preserve the number of items in the
--   list, and must maintain the ordering.
--   
--   The law <tt><a>hmap</a> <a>id</a> == id</tt> is a way of formalizing
--   this property.
hmap :: HFunctor t => (f ~> g) -> t f ~> t g

-- | Lift an isomorphism over an <a>HFunctor</a>.
--   
--   Essentailly, if <tt>f</tt> and <tt>g</tt> are isomorphic, then so are
--   <tt>t f</tt> and <tt>t g</tt>.
overHFunctor :: HFunctor t => (f <~> g) -> t f <~> t g

-- | A typeclass for <a>HFunctor</a>s where you can "inject" an <tt>f
--   a</tt> into a <tt>t f a</tt>:
--   
--   <pre>
--   <a>inject</a> :: f a -&gt; t f a
--   </pre>
--   
--   If you think of <tt>t f a</tt> as an "enhanced <tt>f</tt>", then
--   <a>inject</a> allows you to use an <tt>f</tt> as its enhanced form.
--   
--   With the exception of directly pattern matching on the result,
--   <a>inject</a> itself is not too useful in the general case without
--   <a>Interpret</a> to allow us to interpret or retrieve back the
--   <tt>f</tt>.
class HFunctor t => Inject t

-- | Lift from <tt>f</tt> into the enhanced <tt>t f</tt> structure.
--   Analogous to <a>lift</a> from <a>MonadTrans</a>.
--   
--   Note that this lets us "lift" a <tt>f a</tt>; if you want to lift an
--   <tt>a</tt> with <tt>a -&gt; t f a</tt>, check if <tt>t f</tt> is an
--   instance of <a>Applicative</a> or <a>Pointed</a>.
inject :: Inject t => f ~> t f

-- | <a>HBind</a> is effectively a "higher-order <a>Monad</a>", in the
--   sense that <a>HFunctor</a> is a "higher-order <a>Functor</a>".
--   
--   It can be considered a typeclass for <a>HFunctor</a>s that you can
--   bind continuations to, nautral<i>universal over all
--   <tt>f</tt></i>functors. They work "for all functors" you lift, without
--   requiring any constraints.
--   
--   It is very similar to <a>Interpret</a>, except <a>Interpret</a> has
--   the ability to constrain the contexts to some typeclass.
--   
--   The main law is that binding <a>inject</a> should leave things
--   unchanged:
--   
--   <pre>
--   <a>hbind</a> <a>inject</a> == <a>id</a>
--   </pre>
--   
--   But <a>hbind</a> should also be associatiatve, in a way that makes
--   
--   <pre>
--   <a>hjoin</a> . hjoin
--      = hjoin . <a>hmap</a> hjoin
--   </pre>
--   
--   That is, squishing a <tt>t (t (t f)) a</tt> into a <tt>t f a</tt> can
--   be done "inside" first, then "outside", or "outside" first, then
--   "inside".
--   
--   Note that these laws are different from the <a>Interpret</a> laws, so
--   we often have instances where <a>hbind</a> and <a>interpret</a>
--   (though they both may typecheck) produce different behavior.
--   
--   This class is similar to <a>MMonad</a> from
--   <a>Control.Monad.Morph</a>, but instances must work without a
--   <a>Monad</a> constraint.
class Inject t => HBind t

-- | Bind a continuation to a <tt>t f</tt> into some context <tt>g</tt>.
hbind :: HBind t => (f ~> t g) -> t f ~> t g

-- | Collapse a nested <tt>t (t f)</tt> into a single <tt>t f</tt>.
hjoin :: HBind t => t (t f) ~> t f

-- | The functor combinator that forgets all structure in the input.
--   Ignores the input structure and stores no information.
--   
--   Acts like the "zero" with respect to functor combinator composition.
--   
--   <pre>
--   <a>ComposeT</a> ProxyF f      ~ ProxyF
--   <a>ComposeT</a> f      ProxyF ~ ProxyF
--   </pre>
--   
--   It can be <a>inject</a>ed into (losing all information), but it is
--   impossible to ever <a>retract</a> or <a>interpret</a> it.
--   
--   This is essentially <tt><a>ConstF</a> ()</tt>.
data ProxyF f a
ProxyF :: ProxyF f a

-- | Functor combinator that forgets all structure on the input, and
--   instead stores a value of type <tt>e</tt>.
--   
--   Like <a>ProxyF</a>, acts like a "zero" with functor combinator
--   composition.
--   
--   It can be <a>inject</a>ed into (losing all information), but it is
--   impossible to ever <a>retract</a> or <a>interpret</a> it.
data ConstF e f a
ConstF :: e -> ConstF e f a
[getConstF] :: ConstF e f a -> e

-- | An "<a>HFunctor</a> combinator" that enhances an <a>HFunctor</a> with
--   the ability to hold a single <tt>f a</tt>. This is the higher-order
--   analogue of <a>Lift</a>.
--   
--   You can think of it as a free <a>Inject</a> for any <tt>f</tt>.
--   
--   Note that <tt><a>HLift</a> <a>IdentityT</a></tt> is equivalent to
--   <tt><a>EnvT</a> <a>Any</a></tt>.
data HLift t f a
HPure :: f a -> HLift t f a
HOther :: t f a -> HLift t f a

-- | A higher-level <a>retract</a> to get a <tt>t f a</tt> back out of an
--   <tt><a>HLift</a> t f a</tt>, provided <tt>t</tt> is an instance of
--   <a>Inject</a>.
--   
--   This witnesses the fact that <a>HLift</a> is the "Free <a>Inject</a>".
retractHLift :: Inject t => HLift t f a -> t f a

-- | An "<a>HFunctor</a> combinator" that turns an <a>HFunctor</a> into
--   potentially infinite nestings of that <a>HFunctor</a>.
--   
--   An <tt><a>HFree</a> t f a</tt> is either <tt>f a</tt>, <tt>t f a</tt>,
--   <tt>t (t f) a</tt>, <tt>t (t (t f)) a</tt>, etc.
--   
--   This effectively turns <tt>t</tt> into a tree with <tt>t</tt>
--   branches.
--   
--   One particularly useful usage is with <a>MapF</a>. For example if you
--   had a data type representing a command line command parser:
--   
--   <pre>
--   data Command a
--   </pre>
--   
--   You could represent "many possible named commands" using
--   
--   <pre>
--   type Commands = <a>MapF</a> <a>String</a> Command
--   </pre>
--   
--   And you can represent multiple <i>nested</i> named commands using:
--   
--   <pre>
--   type NestedCommands = <a>HFree</a> (<a>MapF</a> <a>String</a>)
--   </pre>
--   
--   This has an <a>Interpret</a> instance, but it can be more useful to
--   use via direct pattern matching, or through
--   
--   <pre>
--   <a>foldHFree</a>
--       :: <a>HBifunctor</a> t
--       =&gt; f <a>~&gt;</a> g
--       -&gt; t g ~&gt; g
--       -&gt; HFree t f ~&gt; g
--   </pre>
--   
--   which requires no extra constriant on <tt>g</tt>, and lets you
--   consider each branch separately.
--   
--   This can be considered the higher-oder analogue of <a>Free</a>; it is
--   the free <a>HBind</a> for any <tt><a>HFunctor</a> t</tt>.
--   
--   Note that <tt><a>HFree</a> <a>IdentityT</a></tt> is equivalent to
--   <a>Step</a>.
data HFree t f a
HReturn :: f a -> HFree t f a
HJoin :: t (HFree t f) a -> HFree t f a

-- | Recursively fold down an <a>HFree</a> into a single <tt>g</tt> result,
--   by handling each branch. Can be more useful than <a>interpret</a>
--   because it allows you to treat each branch separately, and also does
--   not require any constraint on <tt>g</tt>.
--   
--   This is the catamorphism on <a>HFree</a>.
foldHFree :: forall t f g. HFunctor t => (f ~> g) -> (t g ~> g) -> HFree t f ~> g

-- | A higher-level <a>retract</a> to get a <tt>t f a</tt> back out of an
--   <tt><a>HFree</a> t f a</tt>, provided <tt>t</tt> is an instance of
--   <a>Bind</a>.
--   
--   This witnesses the fact that <a>HFree</a> is the "Free <a>Bind</a>".
retractHFree :: HBind t => HFree t f a -> t f a
instance (GHC.Base.Functor f, GHC.Base.Functor (t f)) => GHC.Base.Functor (Data.HFunctor.HLift t f)
instance forall k (f :: k -> *) (a :: k) (t :: (k -> *) -> k -> *). (GHC.Show.Show (f a), GHC.Show.Show (t f a)) => GHC.Show.Show (Data.HFunctor.HLift t f a)
instance forall k (f :: k -> *) (a :: k) (t :: (k -> *) -> k -> *). (GHC.Read.Read (f a), GHC.Read.Read (t f a)) => GHC.Read.Read (Data.HFunctor.HLift t f a)
instance forall k (f :: k -> *) (a :: k) (t :: (k -> *) -> k -> *). (GHC.Classes.Eq (f a), GHC.Classes.Eq (t f a)) => GHC.Classes.Eq (Data.HFunctor.HLift t f a)
instance forall k (f :: k -> *) (a :: k) (t :: (k -> *) -> k -> *). (GHC.Classes.Ord (f a), GHC.Classes.Ord (t f a)) => GHC.Classes.Ord (Data.HFunctor.HLift t f a)
instance (GHC.Base.Functor f, GHC.Base.Functor (t (Data.HFunctor.HFree t f))) => GHC.Base.Functor (Data.HFunctor.HFree t f)
instance Data.HFunctor.HBind Data.Functor.Coyoneda.Coyoneda
instance Data.HFunctor.HBind Control.Applicative.Free.Ap
instance Data.HFunctor.HBind Control.Applicative.ListF.ListF
instance Data.HFunctor.HBind Control.Applicative.ListF.NonEmptyF
instance Data.HFunctor.HBind Control.Applicative.ListF.MaybeF
instance Data.HFunctor.HBind Control.Applicative.Step.Step
instance Data.HFunctor.HBind Control.Applicative.Step.Flagged
instance Data.Functor.Alt.Alt f => Data.HFunctor.HBind (Data.Functor.These.These1 f)
instance Data.Functor.Plus.Plus f => Data.HFunctor.HBind ((GHC.Generics.:*:) f)
instance Data.Functor.Plus.Plus f => Data.HFunctor.HBind (Data.Functor.Product.Product f)
instance forall k (f :: k -> *). Data.HFunctor.HBind ((GHC.Generics.:+:) f)
instance forall k (f :: k -> *). Data.HFunctor.HBind (Data.Functor.Sum.Sum f)
instance Data.HFunctor.HBind (GHC.Generics.M1 i c)
instance Data.HFunctor.HBind Control.Alternative.Free.Alt
instance Data.HFunctor.HBind Control.Monad.Freer.Church.Free
instance Data.HFunctor.HBind Control.Monad.Freer.Church.Free1
instance Data.HFunctor.HBind Control.Applicative.Free.Final.Ap
instance Data.HFunctor.HBind Control.Applicative.Free.Fast.Ap
instance Data.HFunctor.HBind Control.Monad.Trans.Identity.IdentityT
instance Data.HFunctor.HBind Control.Applicative.Lift.Lift
instance Data.HFunctor.HBind Data.Functor.Bind.Class.MaybeApply
instance Data.HFunctor.HBind Control.Applicative.Backwards.Backwards
instance Data.HFunctor.HBind Data.Functor.Bind.Class.WrappedApplicative
instance Data.HFunctor.HBind Data.Functor.Reverse.Reverse
instance Data.HFunctor.HBind Data.HFunctor.ProxyF
instance GHC.Base.Monoid e => Data.HFunctor.HBind (Control.Comonad.Trans.Env.EnvT e)
instance forall k (t :: (k -> *) -> k -> *). (Data.HFunctor.HBind t, Data.HFunctor.Inject t) => Data.HFunctor.HBind (Data.HFunctor.HLift t)
instance forall k (t :: (k -> *) -> k -> *). Data.HFunctor.Internal.HFunctor t => Data.HFunctor.HBind (Data.HFunctor.HFree t)
instance Data.HFunctor.Inject Data.Functor.Coyoneda.Coyoneda
instance Data.HFunctor.Inject Control.Applicative.Free.Ap
instance Data.HFunctor.Inject Control.Applicative.ListF.ListF
instance Data.HFunctor.Inject Control.Applicative.ListF.NonEmptyF
instance Data.HFunctor.Inject Control.Applicative.ListF.MaybeF
instance GHC.Base.Monoid k => Data.HFunctor.Inject (Control.Applicative.ListF.NEMapF k)
instance GHC.Base.Monoid k => Data.HFunctor.Inject (Control.Applicative.ListF.MapF k)
instance Data.HFunctor.Inject Control.Applicative.Step.Step
instance Data.HFunctor.Inject Control.Applicative.Step.Steps
instance Data.HFunctor.Inject Control.Applicative.Step.Flagged
instance Data.HFunctor.Inject (Data.Functor.These.These1 f)
instance GHC.Base.Applicative f => Data.HFunctor.Inject (Control.Monad.Freer.Church.Comp f)
instance GHC.Base.Applicative f => Data.HFunctor.Inject ((GHC.Generics.:.:) f)
instance Data.Functor.Plus.Plus f => Data.HFunctor.Inject ((GHC.Generics.:*:) f)
instance Data.Functor.Plus.Plus f => Data.HFunctor.Inject (Data.Functor.Product.Product f)
instance forall k (f :: k -> *). Data.HFunctor.Inject ((GHC.Generics.:+:) f)
instance forall k (f :: k -> *). Data.HFunctor.Inject (Data.Functor.Sum.Sum f)
instance Data.HFunctor.Inject (GHC.Generics.M1 i c)
instance Data.HFunctor.Inject Control.Alternative.Free.Alt
instance Data.HFunctor.Inject Control.Monad.Freer.Church.Free
instance Data.HFunctor.Inject Control.Monad.Freer.Church.Free1
instance Data.HFunctor.Inject Control.Applicative.Free.Final.Ap
instance Data.HFunctor.Inject Control.Applicative.Free.Fast.Ap
instance Data.HFunctor.Inject Control.Monad.Trans.Identity.IdentityT
instance Data.HFunctor.Inject Control.Applicative.Lift.Lift
instance Data.HFunctor.Inject Data.Functor.Bind.Class.MaybeApply
instance Data.HFunctor.Inject Control.Applicative.Backwards.Backwards
instance Data.HFunctor.Inject Data.Functor.Bind.Class.WrappedApplicative
instance Data.HFunctor.Inject (Control.Monad.Trans.Reader.ReaderT r)
instance GHC.Base.Monoid e => Data.HFunctor.Inject (Control.Comonad.Trans.Env.EnvT e)
instance Data.HFunctor.Inject Data.Functor.Reverse.Reverse
instance Data.HFunctor.Inject Data.HFunctor.ProxyF
instance GHC.Base.Monoid e => Data.HFunctor.Inject (Data.HFunctor.ConstF e)
instance (Data.HFunctor.Inject s, Data.HFunctor.Inject t) => Data.HFunctor.Inject (Control.Monad.Trans.Compose.ComposeT s t)
instance forall k (t :: (k -> *) -> k -> *). Data.HFunctor.Internal.HFunctor t => Data.HFunctor.Inject (Data.HFunctor.HLift t)
instance forall k (t :: (k -> *) -> k -> *). Data.HFunctor.Internal.HFunctor t => Data.HFunctor.Inject (Data.HFunctor.HFree t)
instance (Data.Functor.Classes.Show1 (t (Data.HFunctor.HFree t f)), Data.Functor.Classes.Show1 f) => Data.Functor.Classes.Show1 (Data.HFunctor.HFree t f)
instance (Data.Functor.Classes.Show1 (t (Data.HFunctor.HFree t f)), Data.Functor.Classes.Show1 f, GHC.Show.Show a) => GHC.Show.Show (Data.HFunctor.HFree t f a)
instance forall k (t :: (k -> *) -> k -> *). Data.HFunctor.Internal.HFunctor t => Data.HFunctor.Internal.HFunctor (Data.HFunctor.HFree t)
instance (Data.Functor.Classes.Show1 (t f), Data.Functor.Classes.Show1 f) => Data.Functor.Classes.Show1 (Data.HFunctor.HLift t f)
instance (Data.Functor.Classes.Eq1 (t f), Data.Functor.Classes.Eq1 f) => Data.Functor.Classes.Eq1 (Data.HFunctor.HLift t f)
instance (Data.Functor.Classes.Ord1 (t f), Data.Functor.Classes.Ord1 f) => Data.Functor.Classes.Ord1 (Data.HFunctor.HLift t f)
instance forall k (t :: (k -> *) -> k -> *). Data.HFunctor.Internal.HFunctor t => Data.HFunctor.Internal.HFunctor (Data.HFunctor.HLift t)
instance forall k e (f :: k). GHC.Classes.Ord e => Data.Functor.Classes.Ord1 (Data.HFunctor.ConstF e f)
instance Data.HFunctor.Internal.HFunctor (Data.HFunctor.ConstF e)
instance forall k e (f :: k). GHC.Classes.Eq e => Data.Functor.Classes.Eq1 (Data.HFunctor.ConstF e f)
instance forall k e (f :: k). GHC.Read.Read e => Data.Functor.Classes.Read1 (Data.HFunctor.ConstF e f)
instance forall k e (f :: k). GHC.Show.Show e => Data.Functor.Classes.Show1 (Data.HFunctor.ConstF e f)
instance forall e k1 (f :: k1) k2 (a :: k2). (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable k1, Data.Typeable.Internal.Typeable k2, Data.Data.Data e) => Data.Data.Data (Data.HFunctor.ConstF e f a)
instance forall e k1 (f :: k1) k2 (a :: k2). GHC.Generics.Generic (Data.HFunctor.ConstF e f a)
instance forall e k (f :: k). Data.Traversable.Traversable (Data.HFunctor.ConstF e f)
instance forall e k (f :: k). Data.Foldable.Foldable (Data.HFunctor.ConstF e f)
instance forall e k (f :: k). GHC.Base.Functor (Data.HFunctor.ConstF e f)
instance forall e k1 (f :: k1) k2 (a :: k2). GHC.Classes.Ord e => GHC.Classes.Ord (Data.HFunctor.ConstF e f a)
instance forall e k1 (f :: k1) k2 (a :: k2). GHC.Classes.Eq e => GHC.Classes.Eq (Data.HFunctor.ConstF e f a)
instance forall e k1 (f :: k1) k2 (a :: k2). GHC.Read.Read e => GHC.Read.Read (Data.HFunctor.ConstF e f a)
instance forall e k1 (f :: k1) k2 (a :: k2). GHC.Show.Show e => GHC.Show.Show (Data.HFunctor.ConstF e f a)
instance forall k (f :: k). Data.Functor.Classes.Ord1 (Data.HFunctor.ProxyF f)
instance Data.HFunctor.Internal.HFunctor Data.HFunctor.ProxyF
instance forall k (f :: k). Data.Functor.Classes.Eq1 (Data.HFunctor.ProxyF f)
instance forall k (f :: k). Data.Functor.Classes.Read1 (Data.HFunctor.ProxyF f)
instance forall k (f :: k). Data.Functor.Classes.Show1 (Data.HFunctor.ProxyF f)
instance forall k1 (f :: k1) k2 (a :: k2). (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable k1, Data.Typeable.Internal.Typeable k2) => Data.Data.Data (Data.HFunctor.ProxyF f a)
instance forall k1 (f :: k1) k2 (a :: k2). GHC.Generics.Generic (Data.HFunctor.ProxyF f a)
instance forall k (f :: k). Data.Traversable.Traversable (Data.HFunctor.ProxyF f)
instance forall k (f :: k). Data.Foldable.Foldable (Data.HFunctor.ProxyF f)
instance forall k (f :: k). GHC.Base.Functor (Data.HFunctor.ProxyF f)
instance forall k1 (f :: k1) k2 (a :: k2). GHC.Classes.Ord (Data.HFunctor.ProxyF f a)
instance forall k1 (f :: k1) k2 (a :: k2). GHC.Classes.Eq (Data.HFunctor.ProxyF f a)
instance forall k1 (f :: k1) k2 (a :: k2). GHC.Read.Read (Data.HFunctor.ProxyF f a)
instance forall k1 (f :: k1) k2 (a :: k2). GHC.Show.Show (Data.HFunctor.ProxyF f a)


-- | This module provides tools for working with unary functor combinators
--   that represent interpretable schemas.
--   
--   These are types <tt>t</tt> that take a functor <tt>f</tt> and return a
--   new functor <tt>t f</tt>, enhancing <tt>f</tt> with new structure and
--   abilities.
--   
--   For these, we have:
--   
--   <pre>
--   <a>inject</a> :: f a -&gt; t f a
--   </pre>
--   
--   which lets you "lift" an <tt>f a</tt> into its transformed version,
--   and also:
--   
--   <pre>
--   <a>interpret</a>
--       :: C t g
--       =&gt; (forall x. f a -&gt; g a)
--       -&gt; t f a
--       -&gt; g a
--   </pre>
--   
--   that lets you "interpret" a <tt>t f a</tt> into a context <tt>g
--   a</tt>, essentially "running" the computaiton that it encodes. The
--   context is required to have a typeclass constraints that reflects what
--   is "required" to be able to run a functor combinator.
--   
--   Every single instance provides different tools. Check out the instance
--   list for a nice list of useful combinators, or also the README for a
--   high-level rundown.
--   
--   See <a>Data.Functor.Tensor</a> for binary functor combinators that mix
--   together two or more different functors.
module Data.HFunctor.Interpret

-- | An <a>Interpret</a> lets us move in and out of the "enhanced"
--   <a>Functor</a>.
--   
--   For example, <tt><a>Free</a> f</tt> is <tt>f</tt> enhanced with
--   monadic structure. We get:
--   
--   <pre>
--   <a>inject</a>    :: f a -&gt; <a>Free</a> f a
--   <a>interpret</a> :: <a>Monad</a> m =&gt; (forall x. f x -&gt; m x) -&gt; <a>Free</a> f a -&gt; m a
--   </pre>
--   
--   <a>inject</a> will let us use our <tt>f</tt> inside the enhanced
--   <tt><a>Free</a> f</tt>. <a>interpret</a> will let us "extract" the
--   <tt>f</tt> from a <tt><a>Free</a> f</tt> if we can give an
--   <i>interpreting function</i> that interprets <tt>f</tt> into some
--   target <a>Monad</a>.
--   
--   The type family <a>C</a> tells us the typeclass constraint of the
--   "target" functor. For <a>Free</a>, it is <a>Monad</a>, but for other
--   <a>Interpret</a> instances, we might have other constraints.
--   
--   We enforce that:
--   
--   <pre>
--   <a>interpret</a> id . <a>inject</a> == id
--   -- or
--   <a>retract</a> . <a>inject</a> == id
--   </pre>
--   
--   That is, if we lift a value into our structure, then immediately
--   interpret it out as itself, it should lave the value unchanged.
class Inject t => Interpret t where {
    
    -- | The constraint on the target context of <a>interpret</a>. It's
    --   basically the constraint that allows you to "exit" or "run" an
    --   <a>Interpret</a>.
    type family C t :: (Type -> Type) -> Constraint;
}

-- | Remove the <tt>f</tt> out of the enhanced <tt>t f</tt> structure,
--   provided that <tt>f</tt> satisfies the necessary constraints. If it
--   doesn't, it needs to be properly <a>interpret</a>ed out.
retract :: (Interpret t, C t f) => t f ~> f

-- | Given an "interpeting function" from <tt>f</tt> to <tt>g</tt>,
--   interpret the <tt>f</tt> out of the <tt>t f</tt> into a final context
--   <tt>g</tt>.
interpret :: (Interpret t, C t g) => (f ~> g) -> t f ~> g

-- | A convenient flipped version of <a>interpret</a>.
forI :: (Interpret t, C t g) => t f a -> (f ~> g) -> g a

-- | Useful wrapper over <a>interpret</a> to allow you to directly extract
--   a value <tt>b</tt> out of the <tt>t f a</tt>, if you can convert <tt>f
--   x</tt> into <tt>b</tt>.
--   
--   Note that depending on the constraints on the interpretation of
--   <tt>t</tt>, you may have extra constraints on <tt>b</tt>.
--   
--   <ul>
--   <li>If <tt><a>C</a> t</tt> is <a>Unconstrained</a>, there are no
--   constraints on <tt>b</tt></li>
--   <li>If <tt><a>C</a> t</tt> is <a>Apply</a>, <tt>b</tt> needs to be an
--   instance of <a>Semigroup</a></li>
--   <li>If <tt><a>C</a> t</tt> is <a>Applicative</a>, <tt>b</tt> needs to
--   be an instance of <a>Monoid</a></li>
--   </ul>
--   
--   For some constraints (like <a>Monad</a>), this will not be usable.
--   
--   <pre>
--   -- get the length of the <tt>Map String</tt> in the <a>Step</a>.
--   <a>collectI</a> length
--        :: Step (Map String) Bool
--        -&gt; Int
--   </pre>
getI :: (Interpret t, C t (Const b)) => (forall x. f x -> b) -> t f a -> b

-- | Useful wrapper over <a>getI</a> to allow you to collect a <tt>b</tt>
--   from all instances of <tt>f</tt> inside a <tt>t f a</tt>.
--   
--   This will work if <tt><a>C</a> t</tt> is <a>Unconstrained</a>,
--   <a>Apply</a>, or <a>Applicative</a>.
--   
--   <pre>
--   -- get the lengths of all <tt>Map String</tt>s in the <a>Ap</a>.
--   <a>collectI</a> length
--        :: Ap (Map String) Bool
--        -&gt; [Int]
--   </pre>
collectI :: (Interpret t, C t (Const [b])) => (forall x. f x -> b) -> t f a -> [b]

-- | A constraint on <tt>a</tt> for both <tt>c a</tt> and <tt>d a</tt>.
--   Requiring <tt><a>AndC</a> <a>Show</a> <a>Eq</a> a</tt> is the same as
--   requiring <tt>(<a>Show</a> a, <a>Eq</a> a)</tt>.
class (c a, d a) => AndC c d a
instance forall k (c :: k -> GHC.Types.Constraint) (a :: k) (d :: k -> GHC.Types.Constraint). (c a, d a) => Data.HFunctor.Interpret.AndC c d a
instance (Data.HFunctor.Interpret.Interpret s, Data.HFunctor.Interpret.Interpret t) => Data.HFunctor.Interpret.Interpret (Control.Monad.Trans.Compose.ComposeT s t)
instance Data.HFunctor.Interpret.Interpret Data.Functor.Coyoneda.Coyoneda
instance Data.HFunctor.Interpret.Interpret Control.Applicative.Free.Ap
instance Data.HFunctor.Interpret.Interpret Control.Applicative.ListF.ListF
instance Data.HFunctor.Interpret.Interpret Control.Applicative.ListF.NonEmptyF
instance Data.HFunctor.Interpret.Interpret Control.Applicative.ListF.MaybeF
instance GHC.Base.Monoid k => Data.HFunctor.Interpret.Interpret (Control.Applicative.ListF.MapF k)
instance GHC.Base.Monoid k => Data.HFunctor.Interpret.Interpret (Control.Applicative.ListF.NEMapF k)
instance Data.HFunctor.Interpret.Interpret Control.Applicative.Step.Step
instance Data.HFunctor.Interpret.Interpret Control.Applicative.Step.Steps
instance Data.HFunctor.Interpret.Interpret Control.Applicative.Step.Flagged
instance Data.HFunctor.Interpret.Interpret (Data.Functor.These.These1 f)
instance Data.HFunctor.Interpret.Interpret Control.Alternative.Free.Alt
instance Data.Functor.Plus.Plus f => Data.HFunctor.Interpret.Interpret ((GHC.Generics.:*:) f)
instance Data.Functor.Plus.Plus f => Data.HFunctor.Interpret.Interpret (Data.Functor.Product.Product f)
instance Data.HFunctor.Interpret.Interpret ((GHC.Generics.:+:) f)
instance Data.HFunctor.Interpret.Interpret (Data.Functor.Sum.Sum f)
instance Data.HFunctor.Interpret.Interpret (GHC.Generics.M1 i c)
instance Data.HFunctor.Interpret.Interpret Control.Monad.Freer.Church.Free
instance Data.HFunctor.Interpret.Interpret Control.Monad.Freer.Church.Free1
instance Data.HFunctor.Interpret.Interpret Control.Applicative.Free.Final.Ap
instance Data.HFunctor.Interpret.Interpret Control.Applicative.Free.Fast.Ap
instance Data.HFunctor.Interpret.Interpret Control.Monad.Trans.Identity.IdentityT
instance Data.HFunctor.Interpret.Interpret Control.Applicative.Lift.Lift
instance Data.HFunctor.Interpret.Interpret Data.Functor.Bind.Class.MaybeApply
instance Data.HFunctor.Interpret.Interpret Control.Applicative.Backwards.Backwards
instance Data.HFunctor.Interpret.Interpret Data.Functor.Bind.Class.WrappedApplicative
instance Data.HFunctor.Interpret.Interpret (Control.Monad.Trans.Reader.ReaderT r)
instance GHC.Base.Monoid e => Data.HFunctor.Interpret.Interpret (Control.Comonad.Trans.Env.EnvT e)
instance Data.HFunctor.Interpret.Interpret Data.Functor.Reverse.Reverse
instance Data.HFunctor.Interpret.Interpret Data.HFunctor.ProxyF
instance GHC.Base.Monoid e => Data.HFunctor.Interpret.Interpret (Data.HFunctor.ConstF e)
instance Data.HFunctor.Interpret.Interpret t => Data.HFunctor.Interpret.Interpret (Data.HFunctor.HLift t)
instance Data.HFunctor.Interpret.Interpret t => Data.HFunctor.Interpret.Interpret (Data.HFunctor.HFree t)


-- | This module provides an abstraction for "two-argument functor
--   combinators", <a>HBifunctor</a>, as well as some useful combinators.
module Data.HBifunctor

-- | A <a>HBifunctor</a> is like an <a>HFunctor</a>, but it enhances
--   <i>two</i> different functors instead of just one.
--   
--   Usually, it enhaces them "together" in some sort of combining way.
--   
--   This typeclass provides a uniform instance for "swapping out" or
--   "hoisting" the enhanced functors. We can hoist the first one with
--   <a>hleft</a>, the second one with <a>hright</a>, or both at the same
--   time with <a>hbimap</a>.
--   
--   For example, the <tt>f :*: g</tt> type gives us "both <tt>f</tt> and
--   <tt>g</tt>":
--   
--   <pre>
--   data (f <a>:*:</a> g) a = f a :*: g a
--   </pre>
--   
--   It combines both <tt>f</tt> and <tt>g</tt> into a unified structure
--   --- here, it does it by providing both <tt>f</tt> and <tt>g</tt>.
--   
--   The single law is:
--   
--   <pre>
--   <a>hbimap</a> <a>id</a> id == id
--   </pre>
--   
--   This ensures that <a>hleft</a>, <a>hright</a>, and <a>hbimap</a> do
--   not affect the structure that <tt>t</tt> adds on top of the underlying
--   functors.
class HBifunctor t

-- | Swap out the first transformed functor.
hleft :: HBifunctor t => (f ~> j) -> t f g ~> t j g

-- | Swap out the second transformed functor.
hright :: HBifunctor t => (g ~> k) -> t f g ~> t f k

-- | Swap out both transformed functors at the same time.
hbimap :: HBifunctor t => (f ~> j) -> (g ~> k) -> t f g ~> t j k

-- | Useful newtype to allow us to derive an <a>HFunctor</a> instance from
--   any instance of <a>HBifunctor</a>, using -XDerivingVia.
--   
--   For example, because we have <tt>instance <a>HBifunctor</a>
--   <a>Day</a></tt>, we can write:
--   
--   <pre>
--   deriving via (<a>WrappedHBifunctor</a> <a>Day</a> f) instance <a>HFunctor</a> (<a>Day</a> f)
--   </pre>
--   
--   to give us an automatic <a>HFunctor</a> instance and save us some
--   work.
newtype WrappedHBifunctor t (f :: k -> Type) (g :: k -> Type) a
WrapHBifunctor :: t f g a -> WrappedHBifunctor t a
[unwrapHBifunctor] :: WrappedHBifunctor t a -> t f g a

-- | Lift two isomorphisms on each side of a bifunctor to become an
--   isomorphism between the two bifunctor applications.
--   
--   Basically, if <tt>f</tt> and <tt>f'</tt> are isomorphic, and
--   <tt>g</tt> and <tt>g'</tt> are isomorphic, then <tt>t f g</tt> is
--   isomorphic to <tt>t f' g'</tt>.
overHBifunctor :: HBifunctor t => (f <~> f') -> (g <~> g') -> t f g <~> t f' g'

-- | An <a>HBifunctor</a> that ignores its second input. Like a <a>:+:</a>
--   with no <a>R1</a>/right branch.
--   
--   This is <a>Joker</a> from <a>Data.Bifunctors.Joker</a>, but given a
--   more sensible name for its purpose.
newtype LeftF f g a
LeftF :: f a -> LeftF f g a
[runLeftF] :: LeftF f g a -> f a

-- | An <a>HBifunctor</a> that ignores its first input. Like a <a>:+:</a>
--   with no <a>L1</a>/left branch.
--   
--   In its polykinded form (on <tt>f</tt>), it is essentially a
--   higher-order version of <a>Tagged</a>.
newtype RightF f g a
RightF :: g a -> RightF f g a
[runRightF] :: RightF f g a -> g a
instance forall k (f :: k -> *). Data.HFunctor.Internal.HFunctor (Data.HBifunctor.RightF f)
instance forall k (g :: * -> *) (f :: k). Data.Functor.Classes.Ord1 g => Data.Functor.Classes.Ord1 (Data.HBifunctor.RightF f g)
instance Data.HFunctor.Internal.HBifunctor Data.HBifunctor.RightF
instance forall k1 k2 (f :: k2). Data.HFunctor.Internal.HFunctor (Data.HBifunctor.RightF f)
instance forall k1 k2 (f :: k2). Data.HFunctor.Inject (Data.HBifunctor.RightF f)
instance forall k1 k2 (f :: k2). Data.HFunctor.HBind (Data.HBifunctor.RightF f)
instance forall k (f :: k). Data.HFunctor.Interpret.Interpret (Data.HBifunctor.RightF f)
instance forall k (g :: * -> *) (f :: k). Data.Functor.Classes.Eq1 g => Data.Functor.Classes.Eq1 (Data.HBifunctor.RightF f g)
instance forall k (g :: * -> *) (f :: k). Data.Functor.Classes.Read1 g => Data.Functor.Classes.Read1 (Data.HBifunctor.RightF f g)
instance forall k (g :: * -> *) (f :: k). Data.Functor.Classes.Show1 g => Data.Functor.Classes.Show1 (Data.HBifunctor.RightF f g)
instance forall k1 (f :: k1) k2 (g :: k2 -> *) (a :: k2). (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable g, Data.Typeable.Internal.Typeable k1, Data.Typeable.Internal.Typeable k2, Data.Data.Data (g a)) => Data.Data.Data (Data.HBifunctor.RightF f g a)
instance forall k1 (f :: k1) k2 (g :: k2 -> *) (a :: k2). GHC.Generics.Generic (Data.HBifunctor.RightF f g a)
instance forall k (f :: k) (g :: * -> *). Data.Traversable.Traversable g => Data.Traversable.Traversable (Data.HBifunctor.RightF f g)
instance forall k (f :: k) (g :: * -> *). Data.Foldable.Foldable g => Data.Foldable.Foldable (Data.HBifunctor.RightF f g)
instance forall k (f :: k) (g :: * -> *). GHC.Base.Functor g => GHC.Base.Functor (Data.HBifunctor.RightF f g)
instance forall k1 (f :: k1) k2 (g :: k2 -> *) (a :: k2). GHC.Classes.Ord (g a) => GHC.Classes.Ord (Data.HBifunctor.RightF f g a)
instance forall k1 (f :: k1) k2 (g :: k2 -> *) (a :: k2). GHC.Classes.Eq (g a) => GHC.Classes.Eq (Data.HBifunctor.RightF f g a)
instance forall k1 (f :: k1) k2 (g :: k2 -> *) (a :: k2). GHC.Read.Read (g a) => GHC.Read.Read (Data.HBifunctor.RightF f g a)
instance forall k1 (f :: k1) k2 (g :: k2 -> *) (a :: k2). GHC.Show.Show (g a) => GHC.Show.Show (Data.HBifunctor.RightF f g a)
instance forall k (f :: k -> *). Data.HFunctor.Internal.HFunctor (Data.HBifunctor.LeftF f)
instance Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Data.HBifunctor.LeftF f)
instance GHC.Base.Applicative f => Data.Biapplicative.Biapplicative (Data.HBifunctor.LeftF f)
instance Data.HFunctor.Internal.HBifunctor Data.HBifunctor.LeftF
instance Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Data.HBifunctor.LeftF f)
instance GHC.Base.Functor f => Data.Bifunctor.Bifunctor (Data.HBifunctor.LeftF f)
instance forall k (f :: * -> *) (g :: k). Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Data.HBifunctor.LeftF f g)
instance forall k (f :: * -> *) (g :: k). Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Data.HBifunctor.LeftF f g)
instance forall k (f :: * -> *) (g :: k). Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Data.HBifunctor.LeftF f g)
instance forall k (f :: * -> *) (g :: k). Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Data.HBifunctor.LeftF f g)
instance forall k1 (f :: k1 -> *) k2 (g :: k2) (a :: k1). (Data.Typeable.Internal.Typeable g, Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable k2, Data.Typeable.Internal.Typeable k1, Data.Data.Data (f a)) => Data.Data.Data (Data.HBifunctor.LeftF f g a)
instance forall k1 (f :: k1 -> *) k2 (g :: k2) (a :: k1). GHC.Generics.Generic (Data.HBifunctor.LeftF f g a)
instance forall (f :: * -> *) k (g :: k). Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.HBifunctor.LeftF f g)
instance forall (f :: * -> *) k (g :: k). Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.HBifunctor.LeftF f g)
instance forall (f :: * -> *) k (g :: k). GHC.Base.Functor f => GHC.Base.Functor (Data.HBifunctor.LeftF f g)
instance forall k1 (f :: k1 -> *) k2 (g :: k2) (a :: k1). GHC.Classes.Ord (f a) => GHC.Classes.Ord (Data.HBifunctor.LeftF f g a)
instance forall k1 (f :: k1 -> *) k2 (g :: k2) (a :: k1). GHC.Classes.Eq (f a) => GHC.Classes.Eq (Data.HBifunctor.LeftF f g a)
instance forall k1 (f :: k1 -> *) k2 (g :: k2) (a :: k1). GHC.Read.Read (f a) => GHC.Read.Read (Data.HBifunctor.LeftF f g a)
instance forall k1 (f :: k1 -> *) k2 (g :: k2) (a :: k1). GHC.Show.Show (f a) => GHC.Show.Show (Data.HBifunctor.LeftF f g a)


-- | The free <a>Apply</a>. Provides <a>Ap1</a> and various utility
--   methods. See <a>Ap1</a> for more details.
--   
--   Ideally <a>Ap1</a> would be in the <i>free</i> package. However, it is
--   defined here for now.
module Data.Functor.Apply.Free

-- | One or more <tt>f</tt>s convolved with itself.
--   
--   Essentially:
--   
--   <pre>
--   <a>Ap1</a> f
--       ~ f                            -- one f
--     <a>:+:</a> (f `<tt>Day'</tt> f)          -- two f's
--     :+: (f `Day` f `Day` f)           -- three f's
--     :+: (f `Day` f `Day` f `Day` f)  -- four f's
--     :+: ...                          -- etc.
--   </pre>
--   
--   Useful if you want to promote an <tt>f</tt> to a situation with "at
--   least one <tt>f</tt> sequenced with itself".
--   
--   Mostly useful for its <a>HFunctor</a> and <a>Interpret</a> instance,
--   along with its relationship with <a>Ap</a> and <a>Day</a>.
--   
--   This is the free <a>Apply</a> --- Basically a "non-empty" <a>Ap</a>.
--   
--   The construction here is based on <a>Ap</a>, similar to now
--   <a>NonEmpty</a> is built on list.
data Ap1 :: (Type -> Type) -> Type -> Type
[Ap1] :: f a -> Ap f (a -> b) -> Ap1 f b

-- | An <a>Ap1</a> is a "non-empty" <a>Ap</a>; this function "forgets" the
--   non-empty property and turns it back into a normal <a>Ap</a>.
toAp :: Ap1 f ~> Ap f

-- | Convert an <a>Ap</a> into an <a>Ap1</a> if possible. If the <a>Ap</a>
--   was "empty", return the <a>Pure</a> value instead.
fromAp :: Ap f ~> (Identity :+: Ap1 f)

-- | Embed an <tt>f</tt> into <a>Ap1</a>.
liftAp1 :: f ~> Ap1 f

-- | Extract the <tt>f</tt> out of the <a>Ap1</a>.
--   
--   <pre>
--   <a>retractAp1</a> . <a>liftAp1</a> == id
--   </pre>
retractAp1 :: Apply f => Ap1 f ~> f

-- | Interpret an <tt><a>Ap</a> f</tt> into some <a>Apply</a> context
--   <tt>g</tt>.
runAp1 :: Apply g => (f ~> g) -> Ap1 f ~> g
instance GHC.Base.Functor (Data.Functor.Apply.Free.Ap1 f)
instance Data.Functor.Bind.Class.Apply (Data.Functor.Apply.Free.Ap1 f)
instance Data.HFunctor.Internal.HFunctor Data.Functor.Apply.Free.Ap1
instance Data.HFunctor.Inject Data.Functor.Apply.Free.Ap1
instance Data.HFunctor.HBind Data.Functor.Apply.Free.Ap1
instance Data.HFunctor.Interpret.Interpret Data.Functor.Apply.Free.Ap1


-- | Provides <a>Final</a>, which can be considered the "free
--   <a>Interpret</a> over a constraint": generate a handy <a>Interpret</a>
--   instance for any constraint <tt>c</tt>.
module Data.HFunctor.Final

-- | A simple way to inject/reject into any eventual typeclass.
--   
--   In a way, this is the "ultimate" multi-purpose <a>Interpret</a>
--   instance. You can use this to inject an <tt>f</tt> into a free
--   structure of any typeclass. If you want <tt>f</tt> to have a
--   <a>Monad</a> instance, for example, just use
--   
--   <pre>
--   <a>inject</a> :: f a -&gt; <a>Final</a> <a>Monad</a> f a
--   </pre>
--   
--   When you want to eventually interpret out the data, use:
--   
--   <pre>
--   <a>interpret</a> :: (f <a>~&gt;</a> g) -&gt; <a>Final</a> c f a -&gt; g a
--   </pre>
--   
--   Essentially, <tt><a>Final</a> c</tt> is the "free c". <tt><a>Final</a>
--   <a>Monad</a></tt> is the free <a>Monad</a>, etc.
--   
--   <a>Final</a> can theoretically replace <a>Ap</a>, <a>Ap1</a>,
--   <a>ListF</a>, <a>NonEmptyF</a>, <a>MaybeF</a>, <a>Free</a>,
--   <a>Identity</a>, <a>Coyoneda</a>, and other instances of
--   <a>FreeOf</a>, if you don't care about being able to pattern match on
--   explicit structure.
--   
--   However, it cannot replace <a>Interpret</a> instances that are not
--   free structures, like <a>Step</a>, <a>Steps</a>, <a>Backwards</a>,
--   etc.
--   
--   Note that this doesn't have instances for <i>all</i> the typeclasses
--   you could lift things into; you probably have to define your own if
--   you want to use <tt><a>Final</a> c</tt> as an <i>instance</i> of
--   <tt>c</tt> (using <a>liftFinal0</a>, <a>liftFinal1</a>,
--   <a>liftFinal2</a> for help).
newtype Final c f a
Final :: (forall g. c g => (forall x. f x -> g x) -> g a) -> Final c f a
[runFinal] :: Final c f a -> forall g. c g => (forall x. f x -> g x) -> g a

-- | <a>Concretize</a> a <a>Final</a>.
fromFinal :: (Interpret t, c (t f)) => Final c f ~> t f

-- | <a>Finalize</a> an <a>Interpret</a> instance.
--   
--   <pre>
--   toFinal :: <a>Coyoneda</a> f <a>~&gt;</a> <a>Final</a> <a>Functor</a> f
--   toFinal :: <a>Ap</a> f <a>~&gt;</a> <a>Final</a> <a>Applicative</a> f
--   toFinal :: <a>Alt</a> f <a>~&gt;</a> <a>Final</a> <a>Alternative</a> f
--   toFinal :: <a>Free</a> f <a>~&gt;</a> <a>Final</a> <a>Monad</a> f
--   toFinal :: <a>Lift</a> f <a>~&gt;</a> <a>Final</a> <a>Pointed</a> f
--   toFinal :: <a>ListF</a> f <a>~&gt;</a> <a>Final</a> <a>Plus</a> f
--   </pre>
--   
--   Note that the instance of <tt>c</tt> for <tt><a>Final</a> c</tt> must
--   be defined.
--   
--   This operation can potentially <i>forget</i> structure in <tt>t</tt>.
--   For example, we have:
--   
--   <pre>
--   <a>toFinal</a> :: <a>Steps</a> f ~&gt; <a>Final</a> <a>Alt</a> f
--   </pre>
--   
--   In this process, we lose the "positional" structure of <a>Steps</a>.
--   
--   In the case where <a>toFinal</a> doesn't lose any information, this
--   will form an isomorphism with <a>fromFinal</a>, and <tt>t</tt> is
--   known as the "Free <tt>c</tt>". For such a situation, <tt>t</tt> will
--   have a <a>FreeOf</a> instance.
toFinal :: (Interpret t, C t (Final c f)) => t f ~> Final c f

-- | A typeclass associating a free structure with the typeclass it is free
--   on.
--   
--   This essentially lists instances of <a>Interpret</a> where a "trip"
--   through <a>Final</a> will leave it unchanged.
--   
--   <pre>
--   <a>fromFree</a> . <a>toFree</a> == id
--   <a>toFree</a> . <a>fromFree</a> == id
--   </pre>
--   
--   This can be useful because <a>Final</a> doesn't have a concrete
--   structure that you can pattern match on and inspect, but <tt>t</tt>
--   might. This lets you work on a concrete structure if you desire.
class Interpret t => FreeOf c t | t -> c
fromFree :: FreeOf c t => t f ~> Final c f
toFree :: (FreeOf c t, Functor f) => Final c f ~> t f
fromFree :: (FreeOf c t, C t (Final c f)) => t f ~> Final c f
toFree :: (FreeOf c t, c (t f)) => Final c f ~> t f

-- | The isomorphism between a free structure and its encoding as
--   <a>Final</a>.
finalizing :: (FreeOf c t, Functor f) => t f <~> Final c f

-- | Re-interpret the context under a <a>Final</a>.
hoistFinalC :: (forall g x. (c g => g x) -> d g => g x) -> Final c f a -> Final d f a

-- | Lift an action into a <a>Final</a>.
liftFinal0 :: (forall g. c g => g a) -> Final c f a

-- | Map the action in a <a>Final</a>.
liftFinal1 :: (forall g. c g => g a -> g b) -> Final c f a -> Final c f b

-- | Merge two <a>Final</a> actions.
liftFinal2 :: (forall g. c g => g a -> g b -> g d) -> Final c f a -> Final c f b -> Final c f d
instance Data.HFunctor.Final.FreeOf GHC.Base.Functor Data.Functor.Coyoneda.Coyoneda
instance Data.HFunctor.Final.FreeOf GHC.Base.Applicative Control.Applicative.Free.Ap
instance Data.HFunctor.Final.FreeOf Data.Functor.Bind.Class.Apply Data.Functor.Apply.Free.Ap1
instance Data.HFunctor.Final.FreeOf GHC.Base.Applicative Control.Applicative.Free.Fast.Ap
instance Data.HFunctor.Final.FreeOf GHC.Base.Alternative Control.Alternative.Free.Alt
instance Data.HFunctor.Final.FreeOf GHC.Base.Monad Control.Monad.Freer.Church.Free
instance Data.HFunctor.Final.FreeOf Data.Functor.Bind.Class.Bind Control.Monad.Freer.Church.Free1
instance Data.HFunctor.Final.FreeOf Data.Pointed.Pointed Control.Applicative.Lift.Lift
instance Data.HFunctor.Final.FreeOf Data.Pointed.Pointed Data.Functor.Bind.Class.MaybeApply
instance Data.HFunctor.Final.FreeOf Data.Functor.Alt.Alt Control.Applicative.ListF.NonEmptyF
instance Data.HFunctor.Final.FreeOf Data.Functor.Plus.Plus Control.Applicative.ListF.ListF
instance Data.HFunctor.Final.FreeOf Data.Constraint.Trivial.Unconstrained Control.Monad.Trans.Identity.IdentityT
instance GHC.Base.Functor (Data.HFunctor.Final.Final GHC.Base.Functor f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final Data.Functor.Bind.Class.Apply f)
instance Data.Functor.Bind.Class.Apply (Data.HFunctor.Final.Final Data.Functor.Bind.Class.Apply f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final Data.Functor.Bind.Class.Bind f)
instance Data.Functor.Bind.Class.Apply (Data.HFunctor.Final.Final Data.Functor.Bind.Class.Bind f)
instance Data.Functor.Bind.Class.Bind (Data.HFunctor.Final.Final Data.Functor.Bind.Class.Bind f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final GHC.Base.Applicative f)
instance Data.Functor.Bind.Class.Apply (Data.HFunctor.Final.Final GHC.Base.Applicative f)
instance GHC.Base.Applicative (Data.HFunctor.Final.Final GHC.Base.Applicative f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final GHC.Base.Alternative f)
instance Data.Functor.Bind.Class.Apply (Data.HFunctor.Final.Final GHC.Base.Alternative f)
instance GHC.Base.Applicative (Data.HFunctor.Final.Final GHC.Base.Alternative f)
instance GHC.Base.Alternative (Data.HFunctor.Final.Final GHC.Base.Alternative f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final GHC.Base.Monad f)
instance Data.Functor.Bind.Class.Apply (Data.HFunctor.Final.Final GHC.Base.Monad f)
instance GHC.Base.Applicative (Data.HFunctor.Final.Final GHC.Base.Monad f)
instance GHC.Base.Monad (Data.HFunctor.Final.Final GHC.Base.Monad f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final GHC.Base.MonadPlus f)
instance GHC.Base.Applicative (Data.HFunctor.Final.Final GHC.Base.MonadPlus f)
instance GHC.Base.Monad (Data.HFunctor.Final.Final GHC.Base.MonadPlus f)
instance GHC.Base.Alternative (Data.HFunctor.Final.Final GHC.Base.MonadPlus f)
instance GHC.Base.MonadPlus (Data.HFunctor.Final.Final GHC.Base.MonadPlus f)
instance Data.Pointed.Pointed (Data.HFunctor.Final.Final Data.Pointed.Pointed f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final (Control.Monad.Reader.Class.MonadReader r) f)
instance GHC.Base.Applicative (Data.HFunctor.Final.Final (Control.Monad.Reader.Class.MonadReader r) f)
instance Data.Functor.Bind.Class.Apply (Data.HFunctor.Final.Final (Control.Monad.Reader.Class.MonadReader r) f)
instance GHC.Base.Monad (Data.HFunctor.Final.Final (Control.Monad.Reader.Class.MonadReader r) f)
instance Control.Monad.Reader.Class.MonadReader r (Data.HFunctor.Final.Final (Control.Monad.Reader.Class.MonadReader r) f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final Data.Functor.Alt.Alt f)
instance Data.Functor.Alt.Alt (Data.HFunctor.Final.Final Data.Functor.Alt.Alt f)
instance GHC.Base.Functor (Data.HFunctor.Final.Final Data.Functor.Plus.Plus f)
instance Data.Functor.Alt.Alt (Data.HFunctor.Final.Final Data.Functor.Plus.Plus f)
instance Data.Functor.Plus.Plus (Data.HFunctor.Final.Final Data.Functor.Plus.Plus f)
instance Data.HFunctor.Internal.HFunctor (Data.HFunctor.Final.Final c)
instance Data.HFunctor.Inject (Data.HFunctor.Final.Final c)
instance Data.HFunctor.Interpret.Interpret (Data.HFunctor.Final.Final c)


-- | This module provides tools for working with binary functor combinators
--   that represent interpretable schemas.
--   
--   These are types <tt><a>HBifunctor</a> t</tt> that take two functors
--   <tt>f</tt> and <tt>g</tt> and returns a new functor <tt>t f g</tt>,
--   that "mixes together" <tt>f</tt> and <tt>g</tt> in some way.
--   
--   The high-level usage of this is
--   
--   <pre>
--   <a>biretract</a> :: t f f ~&gt; f
--   </pre>
--   
--   which lets you fully "mix" together the two input functors.
--   
--   This class also associates each <a>HBifunctor</a> with its "semigroup
--   functor combinator", so we can "squish together" repeated applications
--   of <tt>t</tt>.
--   
--   That is, an <tt><a>SF</a> t f a</tt> is either:
--   
--   <ul>
--   <li><pre>f a</pre></li>
--   <li><pre>t f f a</pre></li>
--   <li><pre>t f (t f f) a</pre></li>
--   <li><pre>t f (t f (t f f)) a</pre></li>
--   <li>.. etc.</li>
--   </ul>
--   
--   which means we can have "list-like" schemas that represent multiple
--   copies of <tt>f</tt>.
--   
--   See <a>Data.HBifunctor.Tensor</a> for a version that also provides an
--   analogy to <a>inject</a>, and a more flexible "squished" combinator
--   <a>MF</a> that has an "empty" element.
module Data.HBifunctor.Associative

-- | An <a>HBifunctor</a> where it doesn't matter which binds first is
--   <a>Associative</a>. Knowing this gives us a lot of power to rearrange
--   the internals of our <a>HFunctor</a> at will.
--   
--   For example, for the functor product:
--   
--   <pre>
--   data (f <a>:*:</a> g) a = f a :*: g a
--   </pre>
--   
--   We know that <tt>f :*: (g :*: h)</tt> is the same as <tt>(f :*: g) :*:
--   h</tt>.
class HBifunctor t => Associative t

-- | The isomorphism between <tt>t f (t g h) a</tt> and <tt>t (t f g) h
--   a</tt>. To use this isomorphism, see <a>assoc</a> and <a>disassoc</a>.
associating :: (Associative t, Functor f, Functor g, Functor h) => t f (t g h) <~> t (t f g) h

-- | Reassociate an application of <tt>t</tt>.
assoc :: (Associative t, Functor f, Functor g, Functor h) => t f (t g h) ~> t (t f g) h

-- | Reassociate an application of <tt>t</tt>.
disassoc :: (Associative t, Functor f, Functor g, Functor h) => t (t f g) h ~> t f (t g h)

-- | For some <tt>t</tt>s, you can represent the act of applying a functor
--   <tt>f</tt> to <tt>t</tt> many times, as a single type. That is, there
--   is some type <tt><a>SF</a> t f</tt> that is equivalent to one of:
--   
--   <ul>
--   <li><tt>f a</tt> -- 1 time</li>
--   <li><tt>t f f a</tt> -- 2 times</li>
--   <li><tt>t f (t f f) a</tt> -- 3 times</li>
--   <li><tt>t f (t f (t f f)) a</tt> -- 4 times</li>
--   <li><tt>t f (t f (t f (t f f))) a</tt> -- 5 times</li>
--   <li>.. etc</li>
--   </ul>
--   
--   This typeclass associates each <tt>t</tt> with its "induced
--   semigroupoidal functor combinator" <tt><a>SF</a> t</tt>.
--   
--   This is useful because sometimes you might want to describe a type
--   that can be <tt>t f f</tt>, <tt>t f (t f f)</tt>, <tt>t f (t f (t f
--   f))</tt>, etc.; "f applied to itself", with at least one <tt>f</tt>.
--   This typeclass lets you use a type like <a>NonEmptyF</a> in terms of
--   repeated applications of <a>:*:</a>, or <a>Ap1</a> in terms of
--   repeated applications of <a>Day</a>, or <a>Free1</a> in terms of
--   repeated applications of <a>Comp</a>, etc.
--   
--   For example, <tt>f <a>:*:</a> f</tt> can be interpreted as "a free
--   selection of two <tt>f</tt>s", allowing you to specify "I have to
--   <tt>f</tt>s that I can use". If you want to specify "I want 1, 2, or
--   many different <tt>f</tt>s that I can use", you can use
--   <tt><a>NonEmptyF</a> f</tt>.
--   
--   At the high level, the main way to <i>use</i> a <a>Semigroupoidal</a>
--   is with <a>biretract</a> and <a>binterpret</a>:
--   
--   <pre>
--   <a>biretract</a> :: t f f <a>~&gt;</a> f
--   <a>binterpret</a> :: (f ~&gt; h) -&gt; (g ~&gt; h) -&gt; t f g ~&gt; h
--   </pre>
--   
--   which are like the <a>HBifunctor</a> versions of <a>retract</a> and
--   <a>interpret</a>: they fully "mix" together the two inputs of
--   <tt>t</tt>.
--   
--   Also useful is:
--   
--   <pre>
--   <a>toSF</a> :: t f f a -&gt; SF t f a
--   </pre>
--   
--   Which converts a <tt>t</tt> into its aggregate type <a>SF</a>.
--   
--   In reality, most <a>Semigroupoidal</a> instances are also
--   <a>Monoidal</a> instances, so you can think of the separation as
--   mostly to help organize functionality. However, there are two
--   non-monoidal semigroupoidal instances of note: <a>LeftF</a> and
--   <a>RightF</a>, which are higher order analogues of the <a>First</a>
--   and <a>Last</a> semigroups, roughly.
class (Associative t, Interpret (SF t)) => Semigroupoidal t where {
    
    -- | The "semigroup functor combinator" generated by <tt>t</tt>.
    --   
    --   A value of type <tt>SF t f a</tt> is <i>equivalent</i> to one of:
    --   
    --   <ul>
    --   <li><pre>f a</pre></li>
    --   <li><pre>t f f a</pre></li>
    --   <li><pre>t f (t f f) a</pre></li>
    --   <li><pre>t f (t f (t f f)) a</pre></li>
    --   <li><pre>t f (t f (t f (t f f))) a</pre></li>
    --   <li>.. etc</li>
    --   </ul>
    --   
    --   For example, for <a>:*:</a>, we have <a>NonEmptyF</a>. This is
    --   because:
    --   
    --   <pre>
    --   x             ~ <a>NonEmptyF</a> (x <a>:|</a> [])      ~ <a>inject</a> x
    --   x <a>:*:</a> y       ~ NonEmptyF (x :| [y])     ~ <a>toSF</a> (x :*: y)
    --   x :*: y :*: z ~ NonEmptyF (x :| [y,z])
    --   -- etc.
    --   </pre>
    --   
    --   You can create an "singleton" one with <a>inject</a>, or else one from
    --   a single <tt>t f f</tt> with <a>toSF</a>.
    type family SF t :: (Type -> Type) -> Type -> Type;
}

-- | If a <tt><a>SF</a> t f</tt> represents multiple applications of <tt>t
--   f</tt> to itself, then we can also "append" two <tt><a>SF</a> t
--   f</tt>s applied to themselves into one giant <tt><a>SF</a> t f</tt>
--   containing all of the <tt>t f</tt>s.
appendSF :: Semigroupoidal t => t (SF t f) (SF t f) ~> SF t f
matchSF :: (Semigroupoidal t, Functor f) => SF t f ~> (f :+: t f (SF t f))

-- | Prepend an application of <tt>t f</tt> to the front of a <tt><a>SF</a>
--   t f</tt>.
consSF :: Semigroupoidal t => t f (SF t f) ~> SF t f

-- | Embed a direct application of <tt>f</tt> to itself into a
--   <tt><a>SF</a> t f</tt>.
toSF :: Semigroupoidal t => t f f ~> SF t f

-- | The <a>HBifunctor</a> analogy of <a>retract</a>. It retracts
--   <i>both</i> <tt>f</tt>s into a single <tt>f</tt>, effectively fully
--   mixing them together.
biretract :: (Semigroupoidal t, CS t f) => t f f ~> f

-- | The <a>HBifunctor</a> analogy of <a>interpret</a>. It takes two
--   interpreting functions, and mixes them together into a target functor
--   <tt>h</tt>.
binterpret :: (Semigroupoidal t, CS t h) => (f ~> h) -> (g ~> h) -> t f g ~> h

-- | Convenient alias for the constraint required for <a>biretract</a>,
--   <a>binterpret</a>, etc.
--   
--   It's usually a constraint on the target/result context of
--   interpretation that allows you to "exit" or "run" a
--   <tt><a>Semigroupoidal</a> t</tt>.
type CS t = C (SF t)

-- | An <tt><a>SF</a> t f</tt> represents the successive application of
--   <tt>t</tt> to <tt>f</tt>, over and over again. So, that means that an
--   <tt><a>SF</a> t f</tt> must either be a single <tt>f</tt>, or an <tt>t
--   f (SF t f)</tt>.
--   
--   <a>matchingSF</a> states that these two are isomorphic. Use
--   <a>matchSF</a> and <tt><a>inject</a> <a>!*!</a> <a>consSF</a></tt> to
--   convert between one and the other.
matchingSF :: (Semigroupoidal t, Functor f) => SF t f <~> (f :+: t f (SF t f))

-- | Useful wrapper over <a>binterpret</a> to allow you to directly extract
--   a value <tt>b</tt> out of the <tt>t f a</tt>, if you can convert <tt>f
--   x</tt> into <tt>b</tt>.
--   
--   Note that depending on the constraints on the interpretation of
--   <tt>t</tt>, you may have extra constraints on <tt>b</tt>.
--   
--   <ul>
--   <li>If <tt><a>C</a> (<a>SF</a> t)</tt> is <a>Unconstrained</a>, there
--   are no constraints on <tt>b</tt></li>
--   <li>If <tt><a>C</a> (<a>SF</a> t)</tt> is <a>Apply</a>, <tt>b</tt>
--   needs to be an instance of <a>Semigroup</a></li>
--   <li>If <tt><a>C</a> (<a>SF</a> t)</tt> is <a>Applicative</a>,
--   <tt>b</tt> needs to be an instance of <a>Monoid</a></li>
--   </ul>
--   
--   For some constraints (like <a>Monad</a>), this will not be usable.
--   
--   <pre>
--   -- Return the length of either the list, or the Map, depending on which
--   --   one s in the <a>+</a>
--   <a>biget</a> <a>length</a> length
--       :: ([] :+: <a>Map</a> <a>Int</a>) <a>Char</a>
--       -&gt; Int
--   
--   -- Return the length of both the list and the map, added together
--   <a>biget</a> (<a>Sum</a> . length) (Sum . length)
--       :: <a>Day</a> [] (Map Int) Char
--       -&gt; Sum Int
--   </pre>
biget :: (Semigroupoidal t, CS t (Const b)) => (forall x. f x -> b) -> (forall x. g x -> b) -> t f g a -> b

-- | Useful wrapper over <a>biget</a> to allow you to collect a <tt>b</tt>
--   from all instances of <tt>f</tt> and <tt>g</tt> inside a <tt>t f g
--   a</tt>.
--   
--   This will work if <tt><a>C</a> t</tt> is <a>Unconstrained</a>,
--   <a>Apply</a>, or <a>Applicative</a>.
bicollect :: (Semigroupoidal t, CS t (Const [b])) => (forall x. f x -> b) -> (forall x. g x -> b) -> t f g a -> [b]

-- | Infix alias for <a>binterpret</a>
(!*!) :: (Semigroupoidal t, CS t h) => (f ~> h) -> (g ~> h) -> t f g ~> h
infixr 5 !*!

-- | Infix alias for <a>biget</a>
--   
--   <pre>
--   -- Return the length of either the list, or the Map, depending on which
--   --   one s in the <a>+</a>
--   <a>length</a> <a>!$!</a> length
--       :: ([] :+: <a>Map</a> <a>Int</a>) <a>Char</a>
--       -&gt; Int
--   
--   -- Return the length of both the list and the map, added together
--   <a>Sum</a> . length !$! Sum . length
--       :: <a>Day</a> [] (Map Int) Char
--       -&gt; Sum Int
--   </pre>
(!$!) :: (Semigroupoidal t, CS t (Const b)) => (forall x. f x -> b) -> (forall x. g x -> b) -> t f g a -> b
infixr 5 !$!
instance Data.HBifunctor.Associative.Semigroupoidal (GHC.Generics.:*:)
instance Data.HBifunctor.Associative.Semigroupoidal Data.Functor.Product.Product
instance Data.HBifunctor.Associative.Semigroupoidal Data.Functor.Day.Day
instance Data.HBifunctor.Associative.Semigroupoidal (GHC.Generics.:+:)
instance Data.HBifunctor.Associative.Semigroupoidal Data.Functor.Sum.Sum
instance Data.HBifunctor.Associative.Semigroupoidal Data.Functor.These.These1
instance Data.HBifunctor.Associative.Semigroupoidal Control.Monad.Freer.Church.Comp
instance Data.HBifunctor.Associative.Semigroupoidal Data.Bifunctor.Joker.Joker
instance Data.HBifunctor.Associative.Semigroupoidal Data.HBifunctor.LeftF
instance Data.HBifunctor.Associative.Semigroupoidal Data.HBifunctor.RightF
instance Data.HBifunctor.Associative.Associative (GHC.Generics.:*:)
instance Data.HBifunctor.Associative.Associative Data.Functor.Product.Product
instance Data.HBifunctor.Associative.Associative Data.Functor.Day.Day
instance Data.HBifunctor.Associative.Associative (GHC.Generics.:+:)
instance Data.HBifunctor.Associative.Associative Data.Functor.Sum.Sum
instance Data.HBifunctor.Associative.Associative Data.Functor.These.These1
instance Data.HBifunctor.Associative.Associative Control.Applicative.Step.Void3
instance Data.HBifunctor.Associative.Associative Control.Monad.Freer.Church.Comp
instance Data.HBifunctor.Associative.Associative Data.Bifunctor.Joker.Joker
instance Data.HBifunctor.Associative.Associative Data.HBifunctor.LeftF
instance Data.HBifunctor.Associative.Associative Data.HBifunctor.RightF


-- | This module provides tools for working with binary functor
--   combinators.
--   
--   <a>Data.Functor.HFunctor</a> deals with <i>single</i> functor
--   combinators (transforming a single functor). This module provides
--   tools for working with combinators that combine and mix two functors
--   "together".
--   
--   The binary analog of <a>HFunctor</a> is <a>HBifunctor</a>: we can map
--   a structure-transforming function over both of the transformed
--   functors.
--   
--   The binary analog of <a>Interpret</a> is <a>Monoidal</a> (and
--   <a>Tensor</a>). If your combinator is an instance of <a>Monoidal</a>,
--   it means that you can "squish" both arguments together into an
--   <a>Interpret</a>. For example:
--   
--   <pre>
--   <a>toMF</a> :: (f <a>:*:</a> f) a -&gt; <a>ListF</a> f a
--   <a>toMF</a> :: <a>Comp</a> f f a -&gt; <a>Free</a> f a
--   <a>toMF</a> :: <a>Day</a> f f a -&gt; <a>Ap</a> f a
--   </pre>
module Data.HBifunctor.Tensor

-- | An <a>Associative</a> <a>HBifunctor</a> can be a <a>Tensor</a> if
--   there is some identity <tt>i</tt> where <tt>t i f</tt> is equivalent
--   to just <tt>f</tt>.
--   
--   That is, "enhancing" <tt>f</tt> with <tt>t i</tt> does nothing.
--   
--   The methods in this class provide us useful ways of navigating a
--   <tt><a>Tensor</a> t</tt> with respect to this property.
--   
--   The <a>Tensor</a> is essentially the <a>HBifunctor</a> equivalent of
--   <a>Inject</a>, with <a>intro1</a> and <a>intro2</a> taking the place
--   of <a>inject</a>.
class Associative t => Tensor t where {
    
    -- | The identity of <tt><a>Tensor</a> t</tt>. If you "combine" <tt>f</tt>
    --   with the identity, it leaves <tt>f</tt> unchanged.
    --   
    --   For example, the identity of <a>:*:</a> is <a>Proxy</a>. This is
    --   because
    --   
    --   <pre>
    --   (<a>Proxy</a> :*: f) a
    --   </pre>
    --   
    --   is equivalent to just
    --   
    --   <pre>
    --   f a
    --   </pre>
    --   
    --   <a>:*:</a>-ing <tt>f</tt> with <a>Proxy</a> gives you no additional
    --   structure.
    --   
    --   Another example:
    --   
    --   <pre>
    --   (<a>V1</a> <a>:+:</a> f) a
    --   </pre>
    --   
    --   is equivalent to just
    --   
    --   <pre>
    --   f a
    --   </pre>
    --   
    --   because the <a>L1</a> case is unconstructable.
    type family I t :: Type -> Type;
}

-- | Because <tt>t f (I t)</tt> is equivalent to <tt>f</tt>, we can always
--   "insert" <tt>f</tt> into <tt>t f (I t)</tt>.
--   
--   This is analogous to <a>inject</a> from <a>Inject</a>, but for
--   <a>HBifunctor</a>s.
intro1 :: Tensor t => f ~> t f (I t)

-- | Because <tt>t (I t) g</tt> is equivalent to <tt>f</tt>, we can always
--   "insert" <tt>g</tt> into <tt>t (I t) g</tt>.
--   
--   This is analogous to <a>inject</a> from <a>Inject</a>, but for
--   <a>HBifunctor</a>s.
intro2 :: Tensor t => g ~> t (I t) g

-- | Witnesses the property that <tt><a>I</a> t</tt> is the identity of
--   <tt>t</tt>: <tt>t f (I t)</tt> always leaves <tt>f</tt> unchanged, so
--   we can always just drop the <tt><a>I</a> t</tt>.
elim1 :: (Tensor t, Functor f) => t f (I t) ~> f

-- | Witnesses the property that <tt><a>I</a> t</tt> is the identity of
--   <tt>t</tt>: <tt>t (I t) g</tt> always leaves <tt>g</tt> unchanged, so
--   we can always just drop the <tt><a>I</a> t</tt>.
elim2 :: (Tensor t, Functor g) => t (I t) g ~> g

-- | <tt>f</tt> is isomorphic to <tt>t f (<a>I</a> t)</tt>: that is,
--   <tt><a>I</a> t</tt> is the identity of <tt>t</tt>, and leaves
--   <tt>f</tt> unchanged.
rightIdentity :: (Tensor t, Functor f) => f <~> t f (I t)

-- | <tt>g</tt> is isomorphic to <tt>t (<a>I</a> t) g</tt>: that is,
--   <tt><a>I</a> t</tt> is the identity of <tt>t</tt>, and leaves
--   <tt>g</tt> unchanged.
leftIdentity :: (Tensor t, Functor g) => g <~> t (I t) g

-- | <a>leftIdentity</a> (<a>intro1</a> and <a>elim1</a>) for <a>:+:</a>
--   actually does not require <a>Functor</a>. This is the more general
--   version.
sumLeftIdentity :: f <~> (V1 :+: f)

-- | <a>rightIdentity</a> (<a>intro2</a> and <a>elim2</a>) for <a>:+:</a>
--   actually does not require <a>Functor</a>. This is the more general
--   version.
sumRightIdentity :: f <~> (f :+: V1)

-- | <a>leftIdentity</a> (<a>intro1</a> and <a>elim1</a>) for <a>:*:</a>
--   actually does not require <a>Functor</a>. This is the more general
--   version.
prodLeftIdentity :: f <~> (Proxy :*: f)

-- | <a>rightIdentity</a> (<a>intro2</a> and <a>elim2</a>) for <a>:*:</a>
--   actually does not require <a>Functor</a>. This is the more general
--   version.
prodRightIdentity :: g <~> (g :*: Proxy)

-- | A <tt><a>Monoidal</a> t</tt> is a <a>Semigroupoidal</a>, in that it
--   provides some type <tt><a>MF</a> t f</tt> that is equivalent to one
--   of:
--   
--   <ul>
--   <li><tt>I a</tt> -- 0 times</li>
--   <li><tt>f a</tt> -- 1 time</li>
--   <li><tt>t f f a</tt> -- 2 times</li>
--   <li><tt>t f (t f f) a</tt> -- 3 times</li>
--   <li><tt>t f (t f (t f f)) a</tt> -- 4 times</li>
--   <li><tt>t f (t f (t f (t f f))) a</tt> -- 5 times</li>
--   <li>.. etc</li>
--   </ul>
--   
--   The difference is that unlike <tt><a>SF</a> t</tt>, <tt><a>MF</a>
--   t</tt> has the "zero times" value.
--   
--   This typeclass lets you use a type like <a>ListF</a> in terms of
--   repeated applications of <a>:*:</a>, or <a>Ap</a> in terms of repeated
--   applications of <a>Day</a>, or <a>Free</a> in terms of repeated
--   applications of <a>Comp</a>, etc.
--   
--   For example, <tt>f <a>:*:</a> f</tt> can be interpreted as "a free
--   selection of two <tt>f</tt>s", allowing you to specify "I have to
--   <tt>f</tt>s that I can use". If you want to specify "I want 0, 1, or
--   many different <tt>f</tt>s that I can use", you can use
--   <tt><a>ListF</a> f</tt>.
--   
--   At the high level, the thing that <a>Monoidal</a> adds to
--   <a>Semigroupoidal</a> is <a>inL</a>, <a>inR</a>, and <a>nilMF</a>:
--   
--   <pre>
--   <a>inL</a>    :: f a -&gt; t f g a
--   <a>inR</a>    :: g a -&gt; t f g a
--   <a>nilMF</a>  :: I a -&gt; MF t f a
--   </pre>
--   
--   which are like the <a>HBifunctor</a> versions of <a>inject</a>: it
--   lets you inject an <tt>f</tt> into <tt>t f g</tt>, so you can start
--   doing useful mixing operations with it. <a>nilMF</a> lets you
--   construct an "empty" <tt><a>MF</a> t</tt>.
--   
--   Also useful is:
--   
--   <pre>
--   <a>toMF</a> :: t f f a -&gt; MF t f a
--   </pre>
--   
--   Which converts a <tt>t</tt> into its aggregate type <a>MF</a>
class (Tensor t, Semigroupoidal t, Interpret (MF t)) => Monoidal t where {
    
    -- | The "monoidal functor combinator" induced by <tt>t</tt>.
    --   
    --   A value of type <tt>MF t f a</tt> is <i>equivalent</i> to one of:
    --   
    --   <ul>
    --   <li><tt>I a</tt> -- zero fs</li>
    --   <li><tt>f a</tt> -- one f</li>
    --   <li><tt>t f f a</tt> -- two fs</li>
    --   <li><tt>t f (t f f) a</tt> -- three fs</li>
    --   <li><pre>t f (t f (t f f)) a</pre></li>
    --   <li><pre>t f (t f (t f (t f f))) a</pre></li>
    --   <li>.. etc</li>
    --   </ul>
    --   
    --   For example, for <a>:*:</a>, we have <a>ListF</a>. This is because:
    --   
    --   <pre>
    --   <a>Proxy</a>         ~ <a>ListF</a> []         ~ <a>nilMF</a> @(<a>:*:</a>)
    --   x             ~ ListF [x]        ~ <a>inject</a> x
    --   x :*: y       ~ ListF [x,y]      ~ <a>toMF</a> (x :*: y)
    --   x :*: y :*: z ~ ListF [x,y,z]
    --   -- etc.
    --   </pre>
    --   
    --   You can create an "empty" one with <a>nilMF</a>, a "singleton" one
    --   with <a>inject</a>, or else one from a single <tt>t f f</tt> with
    --   <a>toMF</a>.
    type family MF t :: (Type -> Type) -> Type -> Type;
}

-- | If a <tt><a>MF</a> t f</tt> represents multiple applications of <tt>t
--   f</tt> to itself, then we can also "append" two <tt><a>MF</a> t
--   f</tt>s applied to themselves into one giant <tt><a>MF</a> t f</tt>
--   containing all of the <tt>t f</tt>s.
appendMF :: Monoidal t => t (MF t f) (MF t f) ~> MF t f

-- | Lets you convert an <tt><a>SF</a> t f</tt> into a single application
--   of <tt>f</tt> to <tt><a>MF</a> t f</tt>.
--   
--   Analogous to a function <tt><a>NonEmpty</a> a -&gt; (a, [a])</tt>
--   
--   Note that this is not reversible in general unless we have
--   <tt><a>Matchable</a> t</tt>.
splitSF :: Monoidal t => SF t f ~> t f (MF t f)

-- | An <tt><a>MF</a> t f</tt> is either empty, or a single application of
--   <tt>t</tt> to <tt>f</tt> and <tt>MF t f</tt> (the "head" and "tail").
--   This witnesses that isomorphism.
--   
--   To <i>use</i> this property, see <a>nilMF</a>, <a>consMF</a>, and
--   <a>unconsMF</a>.
splittingMF :: Monoidal t => MF t f <~> (I t :+: t f (MF t f))

-- | Embed a direct application of <tt>f</tt> to itself into a
--   <tt><a>MF</a> t f</tt>.
toMF :: Monoidal t => t f f ~> MF t f

-- | <tt><a>SF</a> t f</tt> is "one or more <tt>f</tt>s", and <tt>'MF t
--   f</tt> is "zero or more <tt>f</tt>s". This function lets us convert
--   from one to the other.
--   
--   This is analogous to a function <tt><a>NonEmpty</a> a -&gt; [a]</tt>.
--   
--   Note that because <tt>t</tt> is not inferrable from the input or
--   output type, you should call this using <i>-XTypeApplications</i>:
--   
--   <pre>
--   <a>fromSF</a> @(<a>:*:</a>) :: <a>NonEmptyF</a> f a -&gt; <a>ListF</a> f a
--   fromSF @<a>Comp</a>  :: <a>Free1</a> f a -&gt; <a>Free</a> f a
--   </pre>
fromSF :: Monoidal t => SF t f ~> MF t f

-- | If we have an <tt><a>I</a> t</tt>, we can generate an <tt>f</tt> based
--   on how it interacts with <tt>t</tt>.
--   
--   Specialized (and simplified), this type is:
--   
--   <pre>
--   <a>pureT</a> @<a>Day</a>   :: <a>Applicative</a> f =&gt; <a>Identity</a> a -&gt; f a  -- <a>pure</a>
--   pureT @<a>Comp</a>  :: <a>Monad</a> f =&gt; Identity a -&gt; f a        -- <a>return</a>
--   pureT @(<a>:*:</a>) :: <a>Plus</a> f =&gt; <a>Proxy</a> a -&gt; f a            -- <a>zero</a>
--   </pre>
--   
--   Note that because <tt>t</tt> appears nowhere in the input or output
--   types, you must always use this with explicit type application syntax
--   (like <tt>pureT @Day</tt>)
pureT :: (Monoidal t, CM t f) => I t ~> f

-- | If we have a constraint on the <a>Monoidal</a> satisfied, it should
--   also imply the constraint on the <a>Semigroupoidal</a>.
--   
--   This is basically saying that <tt><a>C</a> (<a>SF</a> t)</tt> should
--   be a superclass of <tt><a>C</a> (<a>MF</a> t)</tt>.
--   
--   For example, for <a>:*:</a>, this type signature says that <a>Alt</a>
--   is a superclass of <a>Plus</a>, so whenever you have <a>Plus</a>, you
--   should always also have <a>Alt</a>.
--   
--   For <a>Day</a>, this type signature says that <a>Apply</a> is a
--   superclass of <a>Applicative</a>, so whenever you have
--   <a>Applicative</a>, you should always also have <a>Apply</a>.
--   
--   This is necessary because in the current class hierarchy, <a>Apply</a>
--   isn't a true superclass of <a>Applicative</a>. <a>upgradeC</a>
--   basically "imbues" <tt>f</tt> with an <a>Apply</a> instance based on
--   its <a>Applicative</a> instance, so things can be easier to use.
--   
--   For example, let's say I have a type <tt>Parser</tt> that is an
--   <a>Applicative</a> instance, but the source library does not define an
--   <a>Apply</a> instance. I cannot use <a>biretract</a> or
--   <a>binterpret</a> with it, even though I should be able to, because
--   they require <a>Apply</a>.
--   
--   That is:
--   
--   <pre>
--   <a>biretract</a> :: <a>Day</a> Parser Parser a -&gt; Parser a
--   </pre>
--   
--   is a type error, because it requires <tt><a>Apply</a> Parser</tt>.
--   
--   But, if we know that <tt>Parser</tt> has an <a>Applicative</a>
--   instance, we can use:
--   
--   <pre>
--   <a>upgradeC</a> @<a>Day</a> (<a>Proxy</a> @Parser) <a>biretract</a>
--     :: Day Parser Parser a -&gt; a
--   </pre>
--   
--   and this will now typecheck properly.
--   
--   Ideally, <tt>Parser</tt> would also have an <a>Apply</a> instance. But
--   we cannot control this if an external library defines <tt>Parser</tt>.
--   
--   (Alternatively you can just use <a>biretractT</a>.)
--   
--   Note that you should only use this if <tt>f</tt> doesn't already have
--   the <a>SF</a> constraint. If it does, this could lead to conflicting
--   instances. Only use this with <i>specific</i>, concrete <tt>f</tt>s.
--   Otherwise this is unsafe and can possibly break coherence guarantees.
--   
--   The <tt>proxy</tt> argument can be provided using something like
--   <tt><a>Proxy</a> @f</tt>, to specify which <tt>f</tt> you want to
--   upgrade.
upgradeC :: (Monoidal t, CM t f) => proxy f -> (CS t f => r) -> r

-- | Convenient alias for the constraint required for <a>inL</a>,
--   <a>inR</a>, <a>pureT</a>, etc.
--   
--   It's usually a constraint on the target/result context of
--   interpretation that allows you to "exit" or "run" a
--   <tt><a>Monoidal</a> t</tt>.
type CM t = C (MF t)

-- | Create the "empty <a>MF</a>@.
--   
--   If <tt><a>MF</a> t f</tt> represents multiple applications of <tt>t
--   f</tt> with itself, then <tt>nilMF</tt> gives us "zero applications of
--   <tt>f</tt>".
--   
--   Note that <tt>t</tt> cannot be inferred from the input or output type
--   of <a>nilMF</a>, so this function must always be called with
--   -XTypeApplications:
--   
--   <pre>
--   <a>nilMF</a> @<a>Day</a> :: <a>Identity</a> <a>~&gt;</a> <a>Ap</a> f
--   nilMF @<a>Comp</a> :: Identity ~&gt; <a>Free</a> f
--   nilMF @(<a>:*:</a>) :: <a>Proxy</a> ~&gt; <a>ListF</a> f
--   </pre>
nilMF :: forall t f. Monoidal t => I t ~> MF t f

-- | Lets us "cons" an application of <tt>f</tt> to the front of an
--   <tt><a>MF</a> t f</tt>.
consMF :: Monoidal t => t f (MF t f) ~> MF t f

-- | "Pattern match" on an <tt><a>MF</a> t</tt>
--   
--   An <tt><a>MF</a> t f</tt> is either empty, or a single application of
--   <tt>t</tt> to <tt>f</tt> and <tt>MF t f</tt> (the "head" and "tail")
--   
--   This is analogous to the function <tt><a>uncons</a> :: [a] -&gt; Maybe
--   (a, [a])</tt>.
unconsMF :: Monoidal t => MF t f ~> (I t :+: t f (MF t f))

-- | Convenient wrapper over <a>intro1</a> that lets us introduce an
--   arbitrary functor <tt>g</tt> to the right of an <tt>f</tt>.
--   
--   You can think of this as an <a>HBifunctor</a> analogue of
--   <a>inject</a>.
inL :: forall t f g. (Monoidal t, CM t g) => f ~> t f g

-- | Convenient wrapper over <a>intro2</a> that lets us introduce an
--   arbitrary functor <tt>f</tt> to the right of a <tt>g</tt>.
--   
--   You can think of this as an <a>HBifunctor</a> analogue of
--   <a>inject</a>.
inR :: forall t f g. (Monoidal t, CM t f) => g ~> t f g

-- | Convenient wrapper over <a>elim1</a> that lets us drop one of the
--   arguments of a <a>Tensor</a> for free, without requiring any extra
--   constraints (like for <a>binterpret</a>).
--   
--   See <a>prodOutL</a> for a version that does not require
--   <tt><a>Functor</a> f</tt>, specifically for <a>:*:</a>.
outL :: (Tensor t, I t ~ Proxy, Functor f) => t f g ~> f

-- | Convenient wrapper over <a>elim2</a> that lets us drop one of the
--   arguments of a <a>Tensor</a> for free, without requiring any
--   constraints (like for <a>binterpret</a>).
--   
--   See <a>prodOutR</a> for a version that does not require
--   <tt><a>Functor</a> g</tt>, specifically for <a>:*:</a>.
outR :: (Tensor t, I t ~ Proxy, Functor g) => t f g ~> g

-- | This is <a>biretract</a>, but taking a <tt><a>C</a> (<a>MF</a> t)</tt>
--   constraint instead of a <tt><a>C</a> (<a>SF</a> t)</tt> constraint.
--   For example, for <a>Day</a>, it takes an <a>Applicative</a> constraint
--   instead of an <a>Apply</a> constraint.
--   
--   In an ideal world, this would be not necessary, and we can use
--   <a>biretract</a>. However, sometimes <tt><a>C</a> (<a>MF</a> t)</tt>
--   is not an actual subclass of <tt><a>C</a> (<a>SF</a> t)</tt> (like
--   <a>Apply</a> and <a>Applicative</a>), even though it should
--   technically always be so.
--   
--   Note that you should only use this if <tt>f</tt> doesn't already have
--   the <a>SF</a> constraint (for example, for <a>Day</a>, if <tt>f</tt>
--   already has an <a>Apply</a> instance). If it does, this could lead to
--   conflicting instances. If <tt>f</tt> already has the <a>SF</a>
--   instance, just use <a>biretract</a> directly. Only use this with
--   <i>specific</i>, concrete <tt>f</tt>s.
biretractT :: forall t f. (Monoidal t, CM t f) => t f f ~> f

-- | This is <a>binterpret</a>, but taking a <tt><a>C</a> (<a>MF</a>
--   t)</tt> constraint instead of a <tt><a>C</a> (<a>SF</a> t)</tt>
--   constraint. For example, for <a>Day</a>, it takes an
--   <a>Applicative</a> constraint instead of an <a>Apply</a> constraint.
--   
--   In an ideal world, this would be not necessary, and we can use
--   <a>biretract</a>. However, sometimes <tt><a>C</a> (<a>MF</a> t)</tt>
--   is not an actual subclass of <tt><a>C</a> (<a>SF</a> t)</tt> (like
--   <a>Apply</a> and <a>Applicative</a>), even though it should
--   technically always be so.
--   
--   Note that you should only use this if <tt>f</tt> doesn't already have
--   the <a>SF</a> constraint (for example, for <a>Day</a>, if <tt>f</tt>
--   already has an <a>Apply</a> instance). If it does, this could lead to
--   conflicting instances. If <tt>f</tt> already has the <a>SF</a>
--   instance, just use <a>biretract</a> directly. Only use this with
--   <i>specific</i>, concrete <tt>f</tt>s.
binterpretT :: forall t f g h. (Monoidal t, CM t h) => (f ~> h) -> (g ~> h) -> t f g ~> h

-- | <a>outL</a> for <a>:*:</a> actually does not require <a>Functor</a>.
--   This is the more general version.
prodOutL :: (f :*: g) ~> f

-- | <a>outR</a> for <a>:*:</a> actually does not require <a>Functor</a>.
--   This is the more general version.
prodOutR :: (f :*: g) ~> g

-- | For some <tt>t</tt>, we have the ability to "statically analyze" the
--   <tt><a>MF</a> t</tt> and pattern match and manipulate the structure
--   without ever interpreting or retracting. These are <a>Matchable</a>.
class Monoidal t => Matchable t

-- | The inverse of <a>splitSF</a>. A consing of <tt>f</tt> to
--   <tt><a>MF</a> t f</tt> is non-empty, so it can be represented as an
--   <tt><a>SF</a> t f</tt>.
--   
--   This is analogous to a function <tt><a>uncurry</a> (<a>:|</a>) :: (a,
--   [a]) -&gt; <a>NonEmpty</a> a</tt>.
unsplitSF :: Matchable t => t f (MF t f) ~> SF t f

-- | "Pattern match" on an <tt><a>MF</a> t f</tt>: it is either empty, or
--   it is non-empty (and so can be an <tt><a>SF</a> t f</tt>).
--   
--   This is analgous to a function <tt><a>nonEmpty</a> :: [a] -&gt; Maybe
--   (<a>NonEmpty</a> a)</tt>.
--   
--   Note that because <tt>t</tt> cannot be inferred from the input or
--   output type, you should use this with <i>-XTypeApplications</i>:
--   
--   <pre>
--   <a>matchMF</a> @<a>Day</a> :: <a>Ap</a> f a -&gt; (<a>Identity</a> :+: <a>Ap1</a> f) a
--   </pre>
matchMF :: Matchable t => MF t f ~> (I t :+: SF t f)

-- | An <tt><a>SF</a> t f</tt> is isomorphic to an <tt>f</tt> consed with
--   an <tt><a>MF</a> t f</tt>, like how a <tt><a>NonEmpty</a> a</tt> is
--   isomorphic to <tt>(a, [a])</tt>.
splittingSF :: Matchable t => SF t f <~> t f (MF t f)

-- | An <tt><a>MF</a> t f</tt> is isomorphic to either the empty case
--   (<tt><a>I</a> t</tt>) or the non-empty case (<tt><a>SF</a> t f</tt>),
--   like how <tt>[a]</tt> is isomorphic to <tt><a>Maybe</a>
--   (<a>NonEmpty</a> a)</tt>.
matchingMF :: forall t f. Matchable t => MF t f <~> (I t :+: SF t f)
instance Data.HBifunctor.Tensor.Matchable (GHC.Generics.:*:)
instance Data.HBifunctor.Tensor.Matchable Data.Functor.Product.Product
instance Data.HBifunctor.Tensor.Matchable Data.Functor.Day.Day
instance Data.HBifunctor.Tensor.Matchable (GHC.Generics.:+:)
instance Data.HBifunctor.Tensor.Matchable Data.Functor.Sum.Sum
instance Data.HBifunctor.Tensor.Monoidal (GHC.Generics.:*:)
instance Data.HBifunctor.Tensor.Monoidal Data.Functor.Product.Product
instance Data.HBifunctor.Tensor.Monoidal Data.Functor.Day.Day
instance Data.HBifunctor.Tensor.Monoidal (GHC.Generics.:+:)
instance Data.HBifunctor.Tensor.Monoidal Data.Functor.Sum.Sum
instance Data.HBifunctor.Tensor.Monoidal Data.Functor.These.These1
instance Data.HBifunctor.Tensor.Monoidal Control.Monad.Freer.Church.Comp
instance Data.HBifunctor.Tensor.Tensor (GHC.Generics.:*:)
instance Data.HBifunctor.Tensor.Tensor Data.Functor.Product.Product
instance Data.HBifunctor.Tensor.Tensor Data.Functor.Day.Day
instance Data.HBifunctor.Tensor.Tensor (GHC.Generics.:+:)
instance Data.HBifunctor.Tensor.Tensor Data.Functor.Sum.Sum
instance Data.HBifunctor.Tensor.Tensor Data.Functor.These.These1
instance Data.HBifunctor.Tensor.Tensor Control.Monad.Freer.Church.Comp


-- | This module provides an <a>Interpret</a>able data type of "linked list
--   of tensor applications".
--   
--   The type <tt><a>Chain</a> t</tt>, for any <tt><a>Monoidal</a> t</tt>,
--   is meant to be the same as <tt><a>MF</a> t</tt> (the monoidal functor
--   combinator for <tt>t</tt>), and represents "zero or more" applications
--   of <tt>f</tt> to <tt>t</tt>.
--   
--   The type <tt><a>Chain1</a> t</tt>, for any <tt><a>Semigroupoidal</a>
--   t</tt>, is meant to be the same as <tt><a>SF</a> t</tt> (the
--   semigroupoidal functor combinator for <tt>t</tt>) and represents "one
--   or more" applications of <tt>f</tt> to <tt>t</tt>.
--   
--   The advantage of using <a>Chain</a> and <a>Chain1</a> over <a>MF</a>
--   or <a>SF</a> is that they provide a universal interface for pattern
--   matching and constructing such values, which may simplify working with
--   new such functor combinators you might encounter.
module Data.HFunctor.Chain

-- | A useful construction that works like a "linked list" of <tt>t f</tt>
--   applied to itself multiple times. That is, it contains <tt>t f f</tt>,
--   <tt>t f (t f f)</tt>, <tt>t f (t f (t f f))</tt>, etc, with <tt>f</tt>
--   occuring <i>zero or more</i> times. It is meant to be the same as
--   <tt><a>MF</a> t</tt>.
--   
--   If <tt>t</tt> is <a>Monoidal</a>, then it means we can "collapse" this
--   linked list into some final type <tt><a>MF</a> t</tt>
--   (<a>rerollMF</a>), and also extract it back into a linked list
--   (<a>unrollMF</a>).
--   
--   So, a value of type <tt><a>Chain</a> t (<a>I</a> t) f a</tt> is one of
--   either:
--   
--   <ul>
--   <li><pre><a>I</a> t a</pre></li>
--   <li><pre>f a</pre></li>
--   <li><pre>t f f a</pre></li>
--   <li><pre>t f (t f f) a</pre></li>
--   <li><pre>t f (t f (t f f)) a</pre></li>
--   <li>.. etc.</li>
--   </ul>
--   
--   Note that this is <i>exactly</i> what an <tt><a>MF</a> t</tt> is
--   supposed to be. Using <a>Chain</a> allows us to work with all
--   <tt><a>MF</a> t</tt>s in a uniform way, with normal pattern matching
--   and normal constructors.
--   
--   You can fully "collapse" a <tt><a>Chain</a> t (I t) f</tt> into an
--   <tt>f</tt> with <a>retract</a>, if <tt>t</tt> is <a>Monoidal</a>; this
--   could be considered a fundamental property of monoidal-ness.
--   
--   This construction is inspired by
--   <a>http://oleg.fi/gists/posts/2018-02-21-single-free.html</a>
data Chain t i f a
Done :: i a -> Chain t i f a
More :: t f (Chain t i f) a -> Chain t i f a

-- | Recursively fold down a <a>Chain</a>. Provide a function on how to
--   handle the "single <tt>f</tt> case" (<a>nilMF</a>), and how to handle
--   the "combined <tt>t f g</tt> case", and this will fold the entire
--   <tt><a>Chain</a> t i) f</tt> into a single <tt>g</tt>.
--   
--   This is a catamorphism.
foldChain :: forall t i f g. HBifunctor t => (i ~> g) -> (t f g ~> g) -> Chain t i f ~> g

-- | Recursively build up a <a>Chain</a>. Provide a function that takes
--   some starting seed <tt>g</tt> and returns either "done" (<tt>i</tt>)
--   or "continue further" (<tt>t f g</tt>), and it will create a
--   <tt><a>Chain</a> t i f</tt> from a <tt>g</tt>.
--   
--   This is an anamorphism.
unfoldChain :: forall t f (g :: Type -> Type) i. HBifunctor t => (g ~> (i :+: t f g)) -> g ~> Chain t i f

-- | A type <tt><a>MF</a> t</tt> is supposed to represent the successive
--   application of <tt>t</tt>s to itself. <a>unrollMF</a> makes that
--   successive application explicit, buy converting it to a literal
--   <a>Chain</a> of applications of <tt>t</tt> to itself.
--   
--   <pre>
--   <a>unrollMF</a> = <a>unfoldChain</a> <a>unconsMF</a>
--   </pre>
unrollMF :: Monoidal t => MF t f ~> Chain t (I t) f

-- | A type <tt><a>MF</a> t</tt> is supposed to represent the successive
--   application of <tt>t</tt>s to itself. <a>rerollSF</a> takes an
--   explicit <a>Chain</a> of applications of <tt>t</tt> to itself and
--   rolls it back up into an <tt><a>MF</a> t</tt>.
--   
--   <pre>
--   <a>rerollMF</a> = <a>foldChain</a> <a>nilMF</a> <a>consMF</a>
--   </pre>
--   
--   Because <tt>t</tt> cannot be inferred from the input or output, you
--   should call this with <i>-XTypeApplications</i>:
--   
--   <pre>
--   <a>rerollMF</a> @<a>Comp</a>
--       :: <a>Chain</a> Comp <a>Identity</a> f a -&gt; <a>Free</a> f a
--   </pre>
rerollMF :: forall t f. Monoidal t => Chain t (I t) f ~> MF t f

-- | A type <tt><a>MF</a> t</tt> is supposed to represent the successive
--   application of <tt>t</tt>s to itself. The type <tt><a>Chain</a> t
--   (<a>I</a> t) f</tt> is an actual concrete ADT that contains successive
--   applications of <tt>t</tt> to itself, and you can pattern match on
--   each layer.
--   
--   <a>unrollingMF</a> states that the two types are isormorphic. Use
--   <a>unrollMF</a> and <a>rerollMF</a> to convert between the two.
unrollingMF :: Monoidal t => MF t f <~> Chain t (I t) f

-- | <a>Chain</a> is a monoid with respect to <tt>t</tt>: we can "combine"
--   them in an associative way. The identity here is anything made with
--   the <a>Done</a> constructor.
appendChain :: forall t f. Monoidal t => t (Chain t (I t) f) (Chain t (I t) f) ~> Chain t (I t) f

-- | A useful construction that works like a "non-empty linked list" of
--   <tt>t f</tt> applied to itself multiple times. That is, it contains
--   <tt>t f f</tt>, <tt>t f (t f f)</tt>, <tt>t f (t f (t f f))</tt>, etc,
--   with <tt>f</tt> occuring <i>one or more</i> times. It is meant to be
--   the same as <tt><a>SF</a> t</tt>.
--   
--   A <tt><a>Chain1</a> t f a</tt> is explicitly one of:
--   
--   <ul>
--   <li><pre>f a</pre></li>
--   <li><pre>t f f a</pre></li>
--   <li><pre>t f (t f f) a</pre></li>
--   <li><pre>t f (t f (t f f)) a</pre></li>
--   <li>.. etc</li>
--   </ul>
--   
--   Note that this is exactly the description of <tt><a>SF</a> t</tt>. And
--   that's "the point": for all instances of <a>Semigroupoidal</a>,
--   <tt><a>Chain1</a> t</tt> is isomorphic to <tt><a>SF</a> t</tt>
--   (witnessed by <a>unrollingSF</a>). That's big picture of <a>SF</a>:
--   it's supposed to be a type that consists of all possible
--   self-applications of <tt>f</tt> to <tt>t</tt>.
--   
--   <a>Chain1</a> gives you a way to work with all <tt><a>SF</a> t</tt> in
--   a uniform way. Unlike for <tt><a>SF</a> t f</tt> in general, you can
--   always explicitly /pattern match/ on a <a>Chain1</a> (with its two
--   constructors) and do what you please with it. You can also
--   <i>construct</i> <a>Chain1</a> using normal constructors and
--   functions.
--   
--   You can convert in between <tt><a>SF</a> t f</tt> and
--   <tt><a>Chain1</a> t f</tt> with <a>unrollSF</a> and <a>rerollSF</a>.
--   You can fully "collapse" a <tt><a>Chain1</a> t f</tt> into an
--   <tt>f</tt> with <a>retract</a>, if <tt>t</tt> is
--   <a>Semigroupoidal</a>; this could be considered a fundamental property
--   of semigroupoidal-ness.
--   
--   See <a>Chain</a> for a version that has an "empty" value.
--   
--   This construction is inspired by iteratees and machines.
data Chain1 t f a
Done1 :: f a -> Chain1 t f a
More1 :: t f (Chain1 t f) a -> Chain1 t f a

-- | Recursively fold down a <a>Chain1</a>. Provide a function on how to
--   handle the "single <tt>f</tt> case" (<a>inject</a>), and how to handle
--   the "combined <tt>t f g</tt> case", and this will fold the entire
--   <tt><a>Chain1</a> t f</tt> into a single <tt>g</tt>.
--   
--   This is a catamorphism.
foldChain1 :: forall t f g. HBifunctor t => (f ~> g) -> (t f g ~> g) -> Chain1 t f ~> g

-- | Recursively build up a <a>Chain1</a>. Provide a function that takes
--   some starting seed <tt>g</tt> and returns either "done" (<tt>f</tt>)
--   or "continue further" (<tt>t f g</tt>), and it will create a
--   <tt><a>Chain1</a> t f</tt> from a <tt>g</tt>.
--   
--   This is an anamorphism.
unfoldChain1 :: forall t f (g :: Type -> Type). HBifunctor t => (g ~> (f :+: t f g)) -> g ~> Chain1 t f

-- | A type <tt><a>SF</a> t</tt> is supposed to represent the successive
--   application of <tt>t</tt>s to itself. The type <tt><a>Chain1</a> t
--   f</tt> is an actual concrete ADT that contains successive applications
--   of <tt>t</tt> to itself, and you can pattern match on each layer.
--   
--   <a>unrollingSF</a> states that the two types are isormorphic. Use
--   <a>unrollSF</a> and <a>rerollSF</a> to convert between the two.
unrollingSF :: forall t f. (Semigroupoidal t, Functor f) => SF t f <~> Chain1 t f

-- | A type <tt><a>SF</a> t</tt> is supposed to represent the successive
--   application of <tt>t</tt>s to itself. <a>unrollSF</a> makes that
--   successive application explicit, buy converting it to a literal
--   <a>Chain1</a> of applications of <tt>t</tt> to itself.
--   
--   <pre>
--   <a>unrollSF</a> = <a>unfoldChain1</a> <a>matchSF</a>
--   </pre>
unrollSF :: (Semigroupoidal t, Functor f) => SF t f ~> Chain1 t f

-- | A type <tt><a>SF</a> t</tt> is supposed to represent the successive
--   application of <tt>t</tt>s to itself. <a>rerollSF</a> takes an
--   explicit <a>Chain1</a> of applications of <tt>t</tt> to itself and
--   rolls it back up into an <tt><a>SF</a> t</tt>.
--   
--   <pre>
--   <a>rerollSF</a> = <a>foldChain1</a> <a>inject</a> <a>consSF</a>
--   </pre>
rerollSF :: Semigroupoidal t => Chain1 t f ~> SF t f

-- | <a>Chain1</a> is a semigroup with respect to <tt>t</tt>: we can
--   "combine" them in an associative way.
appendChain1 :: forall t f. (Semigroupoidal t, Functor f) => t (Chain1 t f) (Chain1 t f) ~> Chain1 t f

-- | A <a>Chain1</a> is "one or more linked <tt>f</tt>s", and a
--   <a>Chain</a> is "zero or more linked <tt>f</tt>s". So, we can convert
--   from a <a>Chain1</a> to a <a>Chain</a> that always has at least one
--   <tt>f</tt>.
--   
--   The result of this function always is made with <a>More</a> at the top
--   level.
fromChain1 :: Tensor t => Chain1 t f ~> Chain t (I t) f

-- | A <tt><a>Chain1</a> t f</tt> is like a non-empty linked list of
--   <tt>f</tt>s, and a <tt><a>Chain</a> t (<a>I</a> t) f</tt> is a
--   possibly-empty linked list of <tt>f</tt>s. This witnesses the fact
--   that the former is isomorphic to <tt>f</tt> consed to the latter.
splittingChain1 :: forall t f. (Matchable t, Functor f) => Chain1 t f <~> t f (Chain t (I t) f)

-- | The "forward" function representing <a>splittingChain1</a>. Provided
--   here as a separate function because it does not require
--   <tt><a>Functor</a> f</tt>.
splitChain1 :: forall t f. Matchable t => Chain1 t f ~> t f (Chain t (I t) f)

-- | A <tt><a>Chain</a> t (<a>I</a> t) f</tt> is a linked list of
--   <tt>f</tt>s, and a <tt><a>Chain1</a> t f</tt> is a non-empty linked
--   list of <tt>f</tt>s. This witnesses the fact that a <tt><a>Chain</a> t
--   (I t) f</tt> is either empty (<tt><a>I</a> t</tt>) or non-empty
--   (<tt><a>Chain1</a> t f</tt>).
matchingChain :: forall t f. (Matchable t, Functor f) => Chain t (I t) f <~> (I t :+: Chain1 t f)

-- | The "reverse" function representing <a>matchingChain</a>. Provided
--   here as a separate function because it does not require
--   <tt><a>Functor</a> f</tt>.
unmatchChain :: forall t f. Matchable t => (I t :+: Chain1 t f) ~> Chain t (I t) f
instance forall k (t :: (k -> *) -> (k -> *) -> k -> *) (f :: k -> *) (a :: k). GHC.Generics.Generic (Data.HFunctor.Chain.Chain1 t f a)
instance forall k (f :: k -> *) (a :: k) (t :: (k -> *) -> (k -> *) -> k -> *). (GHC.Classes.Eq (f a), GHC.Classes.Eq (t f (Data.HFunctor.Chain.Chain1 t f) a)) => GHC.Classes.Eq (Data.HFunctor.Chain.Chain1 t f a)
instance forall k (f :: k -> *) (a :: k) (t :: (k -> *) -> (k -> *) -> k -> *). (GHC.Classes.Ord (f a), GHC.Classes.Ord (t f (Data.HFunctor.Chain.Chain1 t f) a)) => GHC.Classes.Ord (Data.HFunctor.Chain.Chain1 t f a)
instance forall k (f :: k -> *) (a :: k) (t :: (k -> *) -> (k -> *) -> k -> *). (GHC.Show.Show (f a), GHC.Show.Show (t f (Data.HFunctor.Chain.Chain1 t f) a)) => GHC.Show.Show (Data.HFunctor.Chain.Chain1 t f a)
instance forall k (f :: k -> *) (a :: k) (t :: (k -> *) -> (k -> *) -> k -> *). (GHC.Read.Read (f a), GHC.Read.Read (t f (Data.HFunctor.Chain.Chain1 t f) a)) => GHC.Read.Read (Data.HFunctor.Chain.Chain1 t f a)
instance (GHC.Base.Functor f, GHC.Base.Functor (t f (Data.HFunctor.Chain.Chain1 t f))) => GHC.Base.Functor (Data.HFunctor.Chain.Chain1 t f)
instance (Data.Foldable.Foldable f, Data.Foldable.Foldable (t f (Data.HFunctor.Chain.Chain1 t f))) => Data.Foldable.Foldable (Data.HFunctor.Chain.Chain1 t f)
instance (Data.Traversable.Traversable f, Data.Traversable.Traversable (t f (Data.HFunctor.Chain.Chain1 t f))) => Data.Traversable.Traversable (Data.HFunctor.Chain.Chain1 t f)
instance forall k1 k2 (i :: k2 -> *) (a :: k2) (t :: k1 -> (k2 -> *) -> k2 -> *) (f :: k1). (GHC.Classes.Eq (i a), GHC.Classes.Eq (t f (Data.HFunctor.Chain.Chain t i f) a)) => GHC.Classes.Eq (Data.HFunctor.Chain.Chain t i f a)
instance forall k1 k2 (i :: k2 -> *) (a :: k2) (t :: k1 -> (k2 -> *) -> k2 -> *) (f :: k1). (GHC.Classes.Ord (i a), GHC.Classes.Ord (t f (Data.HFunctor.Chain.Chain t i f) a)) => GHC.Classes.Ord (Data.HFunctor.Chain.Chain t i f a)
instance forall k1 k2 (i :: k2 -> *) (a :: k2) (t :: k1 -> (k2 -> *) -> k2 -> *) (f :: k1). (GHC.Show.Show (i a), GHC.Show.Show (t f (Data.HFunctor.Chain.Chain t i f) a)) => GHC.Show.Show (Data.HFunctor.Chain.Chain t i f a)
instance forall k1 k2 (i :: k2 -> *) (a :: k2) (t :: k1 -> (k2 -> *) -> k2 -> *) (f :: k1). (GHC.Read.Read (i a), GHC.Read.Read (t f (Data.HFunctor.Chain.Chain t i f) a)) => GHC.Read.Read (Data.HFunctor.Chain.Chain t i f a)
instance forall k (i :: * -> *) (t :: k -> (* -> *) -> * -> *) (f :: k). (GHC.Base.Functor i, GHC.Base.Functor (t f (Data.HFunctor.Chain.Chain t i f))) => GHC.Base.Functor (Data.HFunctor.Chain.Chain t i f)
instance forall k (i :: * -> *) (t :: k -> (* -> *) -> * -> *) (f :: k). (Data.Foldable.Foldable i, Data.Foldable.Foldable (t f (Data.HFunctor.Chain.Chain t i f))) => Data.Foldable.Foldable (Data.HFunctor.Chain.Chain t i f)
instance forall k (i :: * -> *) (t :: k -> (* -> *) -> * -> *) (f :: k). (Data.Traversable.Traversable i, Data.Traversable.Traversable (t f (Data.HFunctor.Chain.Chain t i f))) => Data.Traversable.Traversable (Data.HFunctor.Chain.Chain t i f)
instance forall k (i :: * -> *) (t :: k -> (* -> *) -> * -> *) (f :: k). (Data.Functor.Classes.Eq1 i, Data.Functor.Classes.Eq1 (t f (Data.HFunctor.Chain.Chain t i f))) => Data.Functor.Classes.Eq1 (Data.HFunctor.Chain.Chain t i f)
instance forall k (i :: * -> *) (t :: k -> (* -> *) -> * -> *) (f :: k). (Data.Functor.Classes.Ord1 i, Data.Functor.Classes.Ord1 (t f (Data.HFunctor.Chain.Chain t i f))) => Data.Functor.Classes.Ord1 (Data.HFunctor.Chain.Chain t i f)
instance forall k (t :: k -> (* -> *) -> * -> *) (f :: k) (i :: * -> *). (Data.Functor.Classes.Show1 (t f (Data.HFunctor.Chain.Chain t i f)), Data.Functor.Classes.Show1 i) => Data.Functor.Classes.Show1 (Data.HFunctor.Chain.Chain t i f)
instance forall k (i :: * -> *) (t :: k -> (* -> *) -> * -> *) (f :: k). (GHC.Base.Functor i, Data.Functor.Classes.Read1 (t f (Data.HFunctor.Chain.Chain t i f)), Data.Functor.Classes.Read1 i) => Data.Functor.Classes.Read1 (Data.HFunctor.Chain.Chain t i f)
instance forall k1 k2 (t :: (k1 -> *) -> (k2 -> *) -> k2 -> *) (i :: k2 -> *). Data.HFunctor.Internal.HBifunctor t => Data.HFunctor.Internal.HFunctor (Data.HFunctor.Chain.Chain t i)
instance (Data.HBifunctor.Tensor.Tensor t, i Data.Type.Equality.~ Data.HBifunctor.Tensor.I t) => Data.HFunctor.Inject (Data.HFunctor.Chain.Chain t i)
instance (Data.HBifunctor.Tensor.Monoidal t, i Data.Type.Equality.~ Data.HBifunctor.Tensor.I t) => Data.HFunctor.Interpret.Interpret (Data.HFunctor.Chain.Chain t i)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 (t f (Data.HFunctor.Chain.Chain1 t f))) => Data.Functor.Classes.Eq1 (Data.HFunctor.Chain.Chain1 t f)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 (t f (Data.HFunctor.Chain.Chain1 t f))) => Data.Functor.Classes.Ord1 (Data.HFunctor.Chain.Chain1 t f)
instance (Data.Functor.Classes.Show1 (t f (Data.HFunctor.Chain.Chain1 t f)), Data.Functor.Classes.Show1 f) => Data.Functor.Classes.Show1 (Data.HFunctor.Chain.Chain1 t f)
instance (GHC.Base.Functor f, Data.Functor.Classes.Read1 (t f (Data.HFunctor.Chain.Chain1 t f)), Data.Functor.Classes.Read1 f) => Data.Functor.Classes.Read1 (Data.HFunctor.Chain.Chain1 t f)
instance forall k (t :: (k -> *) -> (k -> *) -> k -> *). Data.HFunctor.Internal.HBifunctor t => Data.HFunctor.Internal.HFunctor (Data.HFunctor.Chain.Chain1 t)
instance forall k (t :: (k -> *) -> (k -> *) -> k -> *). Data.HFunctor.Internal.HBifunctor t => Data.HFunctor.Inject (Data.HFunctor.Chain.Chain1 t)
instance (Data.HFunctor.Internal.HBifunctor t, Data.HBifunctor.Associative.Semigroupoidal t) => Data.HFunctor.Interpret.Interpret (Data.HFunctor.Chain.Chain1 t)


-- | Functor combinators and tools (typeclasses and utiility functions) to
--   manipulate them. This is the main "entrypoint" of the library.
--   
--   Classes include:
--   
--   <ul>
--   <li><a>HFunctor</a> and <a>HBifunctor</a>, used to swap out the
--   functors that the combinators modify</li>
--   <li><a>Interpret</a>, <a>Associative</a>, <a>Monoidal</a>, used to
--   inject and interpret functor values with respect to their
--   combinators.</li>
--   </ul>
--   
--   We have some helpful utility functions, as well, built on top of these
--   typeclasses.
--   
--   The second half of this module exports the various useful functor
--   combinators that can modify functors to add extra functionality, or
--   join two functors together and mix them in different ways. Use them to
--   build your final structure by combining simpler ones in composable
--   ways!
--   
--   See <a>https://blog.jle.im/entry/functor-combinatorpedia.html</a> and
--   the README for a tutorial and a rundown on each different functor
--   combinator.
module Data.Functor.Combinator

-- | A natural transformation from <tt>f</tt> to <tt>g</tt>.
type (~>) (f :: k -> Type) (g :: k -> Type) = forall (x :: k). () => f x -> g x
infixr 0 ~>

-- | The type of an isomorphism between two functors. <tt>f
--   <a>&lt;~&gt;</a> g</tt> means that <tt>f</tt> and <tt>g</tt> are
--   isomorphic to each other.
--   
--   We can effectively <i>use</i> an <tt>f &lt;~&gt; g</tt> with:
--   
--   <pre>
--   <a>viewF</a>   :: (f &lt;~&gt; g) -&gt; f a -&gt; g a
--   <a>reviewF</a> :: (f &lt;~&gt; g) -&gt; g a -&gt; a a
--   </pre>
--   
--   Use <a>viewF</a> to extract the "<tt>f</tt> to <tt>g</tt>" function,
--   and <a>reviewF</a> to extract the "<tt>g</tt> to <tt>f</tt>" function.
--   Reviewing and viewing the same value (or vice versa) leaves the value
--   unchanged.
--   
--   One nice thing is that we can compose isomorphisms using <a>.</a> from
--   <a>Prelude</a>:
--   
--   <pre>
--   (<a>.</a>) :: f &lt;~&gt; g
--       -&gt; g &lt;~&gt; h
--       -&gt; f &lt;~&gt; h
--   </pre>
--   
--   Another nice thing about this representation is that we have the
--   "identity" isomorphism by using <a>id</a> from <a>Prelude</a>.
--   
--   <pre>
--   <a>id</a> :: f <a>&lt;~&gt;</a> g
--   </pre>
--   
--   As a convention, most isomorphisms have form "X-ing", where the
--   forwards function is "ing". For example, we have:
--   
--   <pre>
--   <a>splittingSF</a> :: <a>Monoidal</a> t =&gt; <a>SF</a> t a <a>&lt;~&gt;</a> t f (<a>MF</a> t f)
--   <a>splitSF</a>     :: Monoidal t =&gt; SF t a  <a>~&gt;</a> t f (MF t f)
--   </pre>
type f <~> g = forall p a. Profunctor p => p (g a) (g a) -> p (f a) (f a)
infixr 0 <~>

-- | An <a>HFunctor</a> can be thought of a unary "functor transformer" ---
--   a basic functor combinator. It takes a functor as input and returns a
--   functor as output.
--   
--   It "enhances" a functor with extra structure (sort of like how a monad
--   transformer enhances a <a>Monad</a> with extra structure).
--   
--   As a uniform inteface, we can "swap the underlying functor" (also
--   sometimes called "hoisting"). This is what <a>hmap</a> does: it lets
--   us swap out the <tt>f</tt> in a <tt>t f</tt> for a <tt>t g</tt>.
--   
--   For example, the free monad <a>Free</a> takes a <a>Functor</a> and
--   returns a new <a>Functor</a>. In the process, it provides a monadic
--   structure over <tt>f</tt>. <a>hmap</a> lets us turn a <tt><a>Free</a>
--   f</tt> into a <tt><a>Free</a> g</tt>: a monad built over <tt>f</tt>
--   can be turned into a monad built over <tt>g</tt>.
--   
--   For the ability to move in and out of the enhanced functor, see
--   <a>Inject</a> and <a>Interpret</a>.
--   
--   This class is similar to <a>MFunctor</a> from
--   <a>Control.Monad.Morph</a>, but instances must work without a
--   <a>Monad</a> constraint.
class HFunctor t

-- | If we can turn an <tt>f</tt> into a <tt>g</tt>, then we can turn a
--   <tt>t f</tt> into a <tt>t g</tt>.
--   
--   It must be the case that
--   
--   <pre>
--   <a>hmap</a> <a>id</a> == id
--   </pre>
--   
--   Essentially, <tt>t f</tt> adds some "extra structure" to <tt>f</tt>.
--   <a>hmap</a> must swap out the functor, <i>without affecting the added
--   structure</i>.
--   
--   For example, <tt><a>ListF</a> f a</tt> is essentially a list of <tt>f
--   a</tt>s. If we <a>hmap</a> to swap out the <tt>f a</tt>s for <tt>g
--   a</tt>s, then we must ensure that the "added structure" (here, the
--   number of items in the list, and the ordering of those items) remains
--   the same. So, <a>hmap</a> must preserve the number of items in the
--   list, and must maintain the ordering.
--   
--   The law <tt><a>hmap</a> <a>id</a> == id</tt> is a way of formalizing
--   this property.
hmap :: HFunctor t => (f ~> g) -> t f ~> t g

-- | A typeclass for <a>HFunctor</a>s where you can "inject" an <tt>f
--   a</tt> into a <tt>t f a</tt>:
--   
--   <pre>
--   <a>inject</a> :: f a -&gt; t f a
--   </pre>
--   
--   If you think of <tt>t f a</tt> as an "enhanced <tt>f</tt>", then
--   <a>inject</a> allows you to use an <tt>f</tt> as its enhanced form.
--   
--   With the exception of directly pattern matching on the result,
--   <a>inject</a> itself is not too useful in the general case without
--   <a>Interpret</a> to allow us to interpret or retrieve back the
--   <tt>f</tt>.
class HFunctor t => Inject t

-- | Lift from <tt>f</tt> into the enhanced <tt>t f</tt> structure.
--   Analogous to <a>lift</a> from <a>MonadTrans</a>.
--   
--   Note that this lets us "lift" a <tt>f a</tt>; if you want to lift an
--   <tt>a</tt> with <tt>a -&gt; t f a</tt>, check if <tt>t f</tt> is an
--   instance of <a>Applicative</a> or <a>Pointed</a>.
inject :: Inject t => f ~> t f

-- | An <a>Interpret</a> lets us move in and out of the "enhanced"
--   <a>Functor</a>.
--   
--   For example, <tt><a>Free</a> f</tt> is <tt>f</tt> enhanced with
--   monadic structure. We get:
--   
--   <pre>
--   <a>inject</a>    :: f a -&gt; <a>Free</a> f a
--   <a>interpret</a> :: <a>Monad</a> m =&gt; (forall x. f x -&gt; m x) -&gt; <a>Free</a> f a -&gt; m a
--   </pre>
--   
--   <a>inject</a> will let us use our <tt>f</tt> inside the enhanced
--   <tt><a>Free</a> f</tt>. <a>interpret</a> will let us "extract" the
--   <tt>f</tt> from a <tt><a>Free</a> f</tt> if we can give an
--   <i>interpreting function</i> that interprets <tt>f</tt> into some
--   target <a>Monad</a>.
--   
--   The type family <a>C</a> tells us the typeclass constraint of the
--   "target" functor. For <a>Free</a>, it is <a>Monad</a>, but for other
--   <a>Interpret</a> instances, we might have other constraints.
--   
--   We enforce that:
--   
--   <pre>
--   <a>interpret</a> id . <a>inject</a> == id
--   -- or
--   <a>retract</a> . <a>inject</a> == id
--   </pre>
--   
--   That is, if we lift a value into our structure, then immediately
--   interpret it out as itself, it should lave the value unchanged.
class Inject t => Interpret t where {
    
    -- | The constraint on the target context of <a>interpret</a>. It's
    --   basically the constraint that allows you to "exit" or "run" an
    --   <a>Interpret</a>.
    type family C t :: (Type -> Type) -> Constraint;
}

-- | Remove the <tt>f</tt> out of the enhanced <tt>t f</tt> structure,
--   provided that <tt>f</tt> satisfies the necessary constraints. If it
--   doesn't, it needs to be properly <a>interpret</a>ed out.
retract :: (Interpret t, C t f) => t f ~> f

-- | Given an "interpeting function" from <tt>f</tt> to <tt>g</tt>,
--   interpret the <tt>f</tt> out of the <tt>t f</tt> into a final context
--   <tt>g</tt>.
interpret :: (Interpret t, C t g) => (f ~> g) -> t f ~> g

-- | A convenient flipped version of <a>interpret</a>.
forI :: (Interpret t, C t g) => t f a -> (f ~> g) -> g a

-- | Useful wrapper over <a>interpret</a> to allow you to directly extract
--   a value <tt>b</tt> out of the <tt>t f a</tt>, if you can convert <tt>f
--   x</tt> into <tt>b</tt>.
--   
--   Note that depending on the constraints on the interpretation of
--   <tt>t</tt>, you may have extra constraints on <tt>b</tt>.
--   
--   <ul>
--   <li>If <tt><a>C</a> t</tt> is <a>Unconstrained</a>, there are no
--   constraints on <tt>b</tt></li>
--   <li>If <tt><a>C</a> t</tt> is <a>Apply</a>, <tt>b</tt> needs to be an
--   instance of <a>Semigroup</a></li>
--   <li>If <tt><a>C</a> t</tt> is <a>Applicative</a>, <tt>b</tt> needs to
--   be an instance of <a>Monoid</a></li>
--   </ul>
--   
--   For some constraints (like <a>Monad</a>), this will not be usable.
--   
--   <pre>
--   -- get the length of the <tt>Map String</tt> in the <a>Step</a>.
--   <a>collectI</a> length
--        :: Step (Map String) Bool
--        -&gt; Int
--   </pre>
getI :: (Interpret t, C t (Const b)) => (forall x. f x -> b) -> t f a -> b

-- | Useful wrapper over <a>getI</a> to allow you to collect a <tt>b</tt>
--   from all instances of <tt>f</tt> inside a <tt>t f a</tt>.
--   
--   This will work if <tt><a>C</a> t</tt> is <a>Unconstrained</a>,
--   <a>Apply</a>, or <a>Applicative</a>.
--   
--   <pre>
--   -- get the lengths of all <tt>Map String</tt>s in the <a>Ap</a>.
--   <a>collectI</a> length
--        :: Ap (Map String) Bool
--        -&gt; [Int]
--   </pre>
collectI :: (Interpret t, C t (Const [b])) => (forall x. f x -> b) -> t f a -> [b]

-- | A <a>HBifunctor</a> is like an <a>HFunctor</a>, but it enhances
--   <i>two</i> different functors instead of just one.
--   
--   Usually, it enhaces them "together" in some sort of combining way.
--   
--   This typeclass provides a uniform instance for "swapping out" or
--   "hoisting" the enhanced functors. We can hoist the first one with
--   <a>hleft</a>, the second one with <a>hright</a>, or both at the same
--   time with <a>hbimap</a>.
--   
--   For example, the <tt>f :*: g</tt> type gives us "both <tt>f</tt> and
--   <tt>g</tt>":
--   
--   <pre>
--   data (f <a>:*:</a> g) a = f a :*: g a
--   </pre>
--   
--   It combines both <tt>f</tt> and <tt>g</tt> into a unified structure
--   --- here, it does it by providing both <tt>f</tt> and <tt>g</tt>.
--   
--   The single law is:
--   
--   <pre>
--   <a>hbimap</a> <a>id</a> id == id
--   </pre>
--   
--   This ensures that <a>hleft</a>, <a>hright</a>, and <a>hbimap</a> do
--   not affect the structure that <tt>t</tt> adds on top of the underlying
--   functors.
class HBifunctor t

-- | Swap out the first transformed functor.
hleft :: HBifunctor t => (f ~> j) -> t f g ~> t j g

-- | Swap out the second transformed functor.
hright :: HBifunctor t => (g ~> k) -> t f g ~> t f k

-- | Swap out both transformed functors at the same time.
hbimap :: HBifunctor t => (f ~> j) -> (g ~> k) -> t f g ~> t j k

-- | An <a>HBifunctor</a> where it doesn't matter which binds first is
--   <a>Associative</a>. Knowing this gives us a lot of power to rearrange
--   the internals of our <a>HFunctor</a> at will.
--   
--   For example, for the functor product:
--   
--   <pre>
--   data (f <a>:*:</a> g) a = f a :*: g a
--   </pre>
--   
--   We know that <tt>f :*: (g :*: h)</tt> is the same as <tt>(f :*: g) :*:
--   h</tt>.
class HBifunctor t => Associative t

-- | The isomorphism between <tt>t f (t g h) a</tt> and <tt>t (t f g) h
--   a</tt>. To use this isomorphism, see <a>assoc</a> and <a>disassoc</a>.
associating :: (Associative t, Functor f, Functor g, Functor h) => t f (t g h) <~> t (t f g) h

-- | For some <tt>t</tt>s, you can represent the act of applying a functor
--   <tt>f</tt> to <tt>t</tt> many times, as a single type. That is, there
--   is some type <tt><a>SF</a> t f</tt> that is equivalent to one of:
--   
--   <ul>
--   <li><tt>f a</tt> -- 1 time</li>
--   <li><tt>t f f a</tt> -- 2 times</li>
--   <li><tt>t f (t f f) a</tt> -- 3 times</li>
--   <li><tt>t f (t f (t f f)) a</tt> -- 4 times</li>
--   <li><tt>t f (t f (t f (t f f))) a</tt> -- 5 times</li>
--   <li>.. etc</li>
--   </ul>
--   
--   This typeclass associates each <tt>t</tt> with its "induced
--   semigroupoidal functor combinator" <tt><a>SF</a> t</tt>.
--   
--   This is useful because sometimes you might want to describe a type
--   that can be <tt>t f f</tt>, <tt>t f (t f f)</tt>, <tt>t f (t f (t f
--   f))</tt>, etc.; "f applied to itself", with at least one <tt>f</tt>.
--   This typeclass lets you use a type like <a>NonEmptyF</a> in terms of
--   repeated applications of <a>:*:</a>, or <a>Ap1</a> in terms of
--   repeated applications of <a>Day</a>, or <a>Free1</a> in terms of
--   repeated applications of <a>Comp</a>, etc.
--   
--   For example, <tt>f <a>:*:</a> f</tt> can be interpreted as "a free
--   selection of two <tt>f</tt>s", allowing you to specify "I have to
--   <tt>f</tt>s that I can use". If you want to specify "I want 1, 2, or
--   many different <tt>f</tt>s that I can use", you can use
--   <tt><a>NonEmptyF</a> f</tt>.
--   
--   At the high level, the main way to <i>use</i> a <a>Semigroupoidal</a>
--   is with <a>biretract</a> and <a>binterpret</a>:
--   
--   <pre>
--   <a>biretract</a> :: t f f <a>~&gt;</a> f
--   <a>binterpret</a> :: (f ~&gt; h) -&gt; (g ~&gt; h) -&gt; t f g ~&gt; h
--   </pre>
--   
--   which are like the <a>HBifunctor</a> versions of <a>retract</a> and
--   <a>interpret</a>: they fully "mix" together the two inputs of
--   <tt>t</tt>.
--   
--   Also useful is:
--   
--   <pre>
--   <a>toSF</a> :: t f f a -&gt; SF t f a
--   </pre>
--   
--   Which converts a <tt>t</tt> into its aggregate type <a>SF</a>.
--   
--   In reality, most <a>Semigroupoidal</a> instances are also
--   <a>Monoidal</a> instances, so you can think of the separation as
--   mostly to help organize functionality. However, there are two
--   non-monoidal semigroupoidal instances of note: <a>LeftF</a> and
--   <a>RightF</a>, which are higher order analogues of the <a>First</a>
--   and <a>Last</a> semigroups, roughly.
class (Associative t, Interpret (SF t)) => Semigroupoidal t where {
    
    -- | The "semigroup functor combinator" generated by <tt>t</tt>.
    --   
    --   A value of type <tt>SF t f a</tt> is <i>equivalent</i> to one of:
    --   
    --   <ul>
    --   <li><pre>f a</pre></li>
    --   <li><pre>t f f a</pre></li>
    --   <li><pre>t f (t f f) a</pre></li>
    --   <li><pre>t f (t f (t f f)) a</pre></li>
    --   <li><pre>t f (t f (t f (t f f))) a</pre></li>
    --   <li>.. etc</li>
    --   </ul>
    --   
    --   For example, for <a>:*:</a>, we have <a>NonEmptyF</a>. This is
    --   because:
    --   
    --   <pre>
    --   x             ~ <a>NonEmptyF</a> (x <a>:|</a> [])      ~ <a>inject</a> x
    --   x <a>:*:</a> y       ~ NonEmptyF (x :| [y])     ~ <a>toSF</a> (x :*: y)
    --   x :*: y :*: z ~ NonEmptyF (x :| [y,z])
    --   -- etc.
    --   </pre>
    --   
    --   You can create an "singleton" one with <a>inject</a>, or else one from
    --   a single <tt>t f f</tt> with <a>toSF</a>.
    type family SF t :: (Type -> Type) -> Type -> Type;
}

-- | If a <tt><a>SF</a> t f</tt> represents multiple applications of <tt>t
--   f</tt> to itself, then we can also "append" two <tt><a>SF</a> t
--   f</tt>s applied to themselves into one giant <tt><a>SF</a> t f</tt>
--   containing all of the <tt>t f</tt>s.
appendSF :: Semigroupoidal t => t (SF t f) (SF t f) ~> SF t f

-- | Prepend an application of <tt>t f</tt> to the front of a <tt><a>SF</a>
--   t f</tt>.
consSF :: Semigroupoidal t => t f (SF t f) ~> SF t f

-- | Embed a direct application of <tt>f</tt> to itself into a
--   <tt><a>SF</a> t f</tt>.
toSF :: Semigroupoidal t => t f f ~> SF t f

-- | The <a>HBifunctor</a> analogy of <a>retract</a>. It retracts
--   <i>both</i> <tt>f</tt>s into a single <tt>f</tt>, effectively fully
--   mixing them together.
biretract :: (Semigroupoidal t, CS t f) => t f f ~> f

-- | The <a>HBifunctor</a> analogy of <a>interpret</a>. It takes two
--   interpreting functions, and mixes them together into a target functor
--   <tt>h</tt>.
binterpret :: (Semigroupoidal t, CS t h) => (f ~> h) -> (g ~> h) -> t f g ~> h

-- | Convenient alias for the constraint required for <a>biretract</a>,
--   <a>binterpret</a>, etc.
--   
--   It's usually a constraint on the target/result context of
--   interpretation that allows you to "exit" or "run" a
--   <tt><a>Semigroupoidal</a> t</tt>.
type CS t = C (SF t)

-- | Useful wrapper over <a>binterpret</a> to allow you to directly extract
--   a value <tt>b</tt> out of the <tt>t f a</tt>, if you can convert <tt>f
--   x</tt> into <tt>b</tt>.
--   
--   Note that depending on the constraints on the interpretation of
--   <tt>t</tt>, you may have extra constraints on <tt>b</tt>.
--   
--   <ul>
--   <li>If <tt><a>C</a> (<a>SF</a> t)</tt> is <a>Unconstrained</a>, there
--   are no constraints on <tt>b</tt></li>
--   <li>If <tt><a>C</a> (<a>SF</a> t)</tt> is <a>Apply</a>, <tt>b</tt>
--   needs to be an instance of <a>Semigroup</a></li>
--   <li>If <tt><a>C</a> (<a>SF</a> t)</tt> is <a>Applicative</a>,
--   <tt>b</tt> needs to be an instance of <a>Monoid</a></li>
--   </ul>
--   
--   For some constraints (like <a>Monad</a>), this will not be usable.
--   
--   <pre>
--   -- Return the length of either the list, or the Map, depending on which
--   --   one s in the <a>+</a>
--   <a>biget</a> <a>length</a> length
--       :: ([] :+: <a>Map</a> <a>Int</a>) <a>Char</a>
--       -&gt; Int
--   
--   -- Return the length of both the list and the map, added together
--   <a>biget</a> (<a>Sum</a> . length) (Sum . length)
--       :: <a>Day</a> [] (Map Int) Char
--       -&gt; Sum Int
--   </pre>
biget :: (Semigroupoidal t, CS t (Const b)) => (forall x. f x -> b) -> (forall x. g x -> b) -> t f g a -> b

-- | Useful wrapper over <a>biget</a> to allow you to collect a <tt>b</tt>
--   from all instances of <tt>f</tt> and <tt>g</tt> inside a <tt>t f g
--   a</tt>.
--   
--   This will work if <tt><a>C</a> t</tt> is <a>Unconstrained</a>,
--   <a>Apply</a>, or <a>Applicative</a>.
bicollect :: (Semigroupoidal t, CS t (Const [b])) => (forall x. f x -> b) -> (forall x. g x -> b) -> t f g a -> [b]

-- | Infix alias for <a>binterpret</a>
(!*!) :: (Semigroupoidal t, CS t h) => (f ~> h) -> (g ~> h) -> t f g ~> h
infixr 5 !*!

-- | Infix alias for <a>biget</a>
--   
--   <pre>
--   -- Return the length of either the list, or the Map, depending on which
--   --   one s in the <a>+</a>
--   <a>length</a> <a>!$!</a> length
--       :: ([] :+: <a>Map</a> <a>Int</a>) <a>Char</a>
--       -&gt; Int
--   
--   -- Return the length of both the list and the map, added together
--   <a>Sum</a> . length !$! Sum . length
--       :: <a>Day</a> [] (Map Int) Char
--       -&gt; Sum Int
--   </pre>
(!$!) :: (Semigroupoidal t, CS t (Const b)) => (forall x. f x -> b) -> (forall x. g x -> b) -> t f g a -> b
infixr 5 !$!

-- | An <a>Associative</a> <a>HBifunctor</a> can be a <a>Tensor</a> if
--   there is some identity <tt>i</tt> where <tt>t i f</tt> is equivalent
--   to just <tt>f</tt>.
--   
--   That is, "enhancing" <tt>f</tt> with <tt>t i</tt> does nothing.
--   
--   The methods in this class provide us useful ways of navigating a
--   <tt><a>Tensor</a> t</tt> with respect to this property.
--   
--   The <a>Tensor</a> is essentially the <a>HBifunctor</a> equivalent of
--   <a>Inject</a>, with <a>intro1</a> and <a>intro2</a> taking the place
--   of <a>inject</a>.
class Associative t => Tensor t where {
    
    -- | The identity of <tt><a>Tensor</a> t</tt>. If you "combine" <tt>f</tt>
    --   with the identity, it leaves <tt>f</tt> unchanged.
    --   
    --   For example, the identity of <a>:*:</a> is <a>Proxy</a>. This is
    --   because
    --   
    --   <pre>
    --   (<a>Proxy</a> :*: f) a
    --   </pre>
    --   
    --   is equivalent to just
    --   
    --   <pre>
    --   f a
    --   </pre>
    --   
    --   <a>:*:</a>-ing <tt>f</tt> with <a>Proxy</a> gives you no additional
    --   structure.
    --   
    --   Another example:
    --   
    --   <pre>
    --   (<a>V1</a> <a>:+:</a> f) a
    --   </pre>
    --   
    --   is equivalent to just
    --   
    --   <pre>
    --   f a
    --   </pre>
    --   
    --   because the <a>L1</a> case is unconstructable.
    type family I t :: Type -> Type;
}

-- | Because <tt>t f (I t)</tt> is equivalent to <tt>f</tt>, we can always
--   "insert" <tt>f</tt> into <tt>t f (I t)</tt>.
--   
--   This is analogous to <a>inject</a> from <a>Inject</a>, but for
--   <a>HBifunctor</a>s.
intro1 :: Tensor t => f ~> t f (I t)

-- | Because <tt>t (I t) g</tt> is equivalent to <tt>f</tt>, we can always
--   "insert" <tt>g</tt> into <tt>t (I t) g</tt>.
--   
--   This is analogous to <a>inject</a> from <a>Inject</a>, but for
--   <a>HBifunctor</a>s.
intro2 :: Tensor t => g ~> t (I t) g

-- | Witnesses the property that <tt><a>I</a> t</tt> is the identity of
--   <tt>t</tt>: <tt>t f (I t)</tt> always leaves <tt>f</tt> unchanged, so
--   we can always just drop the <tt><a>I</a> t</tt>.
elim1 :: (Tensor t, Functor f) => t f (I t) ~> f

-- | Witnesses the property that <tt><a>I</a> t</tt> is the identity of
--   <tt>t</tt>: <tt>t (I t) g</tt> always leaves <tt>g</tt> unchanged, so
--   we can always just drop the <tt><a>I</a> t</tt>.
elim2 :: (Tensor t, Functor g) => t (I t) g ~> g

-- | A <tt><a>Monoidal</a> t</tt> is a <a>Semigroupoidal</a>, in that it
--   provides some type <tt><a>MF</a> t f</tt> that is equivalent to one
--   of:
--   
--   <ul>
--   <li><tt>I a</tt> -- 0 times</li>
--   <li><tt>f a</tt> -- 1 time</li>
--   <li><tt>t f f a</tt> -- 2 times</li>
--   <li><tt>t f (t f f) a</tt> -- 3 times</li>
--   <li><tt>t f (t f (t f f)) a</tt> -- 4 times</li>
--   <li><tt>t f (t f (t f (t f f))) a</tt> -- 5 times</li>
--   <li>.. etc</li>
--   </ul>
--   
--   The difference is that unlike <tt><a>SF</a> t</tt>, <tt><a>MF</a>
--   t</tt> has the "zero times" value.
--   
--   This typeclass lets you use a type like <a>ListF</a> in terms of
--   repeated applications of <a>:*:</a>, or <a>Ap</a> in terms of repeated
--   applications of <a>Day</a>, or <a>Free</a> in terms of repeated
--   applications of <a>Comp</a>, etc.
--   
--   For example, <tt>f <a>:*:</a> f</tt> can be interpreted as "a free
--   selection of two <tt>f</tt>s", allowing you to specify "I have to
--   <tt>f</tt>s that I can use". If you want to specify "I want 0, 1, or
--   many different <tt>f</tt>s that I can use", you can use
--   <tt><a>ListF</a> f</tt>.
--   
--   At the high level, the thing that <a>Monoidal</a> adds to
--   <a>Semigroupoidal</a> is <a>inL</a>, <a>inR</a>, and <a>nilMF</a>:
--   
--   <pre>
--   <a>inL</a>    :: f a -&gt; t f g a
--   <a>inR</a>    :: g a -&gt; t f g a
--   <a>nilMF</a>  :: I a -&gt; MF t f a
--   </pre>
--   
--   which are like the <a>HBifunctor</a> versions of <a>inject</a>: it
--   lets you inject an <tt>f</tt> into <tt>t f g</tt>, so you can start
--   doing useful mixing operations with it. <a>nilMF</a> lets you
--   construct an "empty" <tt><a>MF</a> t</tt>.
--   
--   Also useful is:
--   
--   <pre>
--   <a>toMF</a> :: t f f a -&gt; MF t f a
--   </pre>
--   
--   Which converts a <tt>t</tt> into its aggregate type <a>MF</a>
class (Tensor t, Semigroupoidal t, Interpret (MF t)) => Monoidal t where {
    
    -- | The "monoidal functor combinator" induced by <tt>t</tt>.
    --   
    --   A value of type <tt>MF t f a</tt> is <i>equivalent</i> to one of:
    --   
    --   <ul>
    --   <li><tt>I a</tt> -- zero fs</li>
    --   <li><tt>f a</tt> -- one f</li>
    --   <li><tt>t f f a</tt> -- two fs</li>
    --   <li><tt>t f (t f f) a</tt> -- three fs</li>
    --   <li><pre>t f (t f (t f f)) a</pre></li>
    --   <li><pre>t f (t f (t f (t f f))) a</pre></li>
    --   <li>.. etc</li>
    --   </ul>
    --   
    --   For example, for <a>:*:</a>, we have <a>ListF</a>. This is because:
    --   
    --   <pre>
    --   <a>Proxy</a>         ~ <a>ListF</a> []         ~ <a>nilMF</a> @(<a>:*:</a>)
    --   x             ~ ListF [x]        ~ <a>inject</a> x
    --   x :*: y       ~ ListF [x,y]      ~ <a>toMF</a> (x :*: y)
    --   x :*: y :*: z ~ ListF [x,y,z]
    --   -- etc.
    --   </pre>
    --   
    --   You can create an "empty" one with <a>nilMF</a>, a "singleton" one
    --   with <a>inject</a>, or else one from a single <tt>t f f</tt> with
    --   <a>toMF</a>.
    type family MF t :: (Type -> Type) -> Type -> Type;
}

-- | If a <tt><a>MF</a> t f</tt> represents multiple applications of <tt>t
--   f</tt> to itself, then we can also "append" two <tt><a>MF</a> t
--   f</tt>s applied to themselves into one giant <tt><a>MF</a> t f</tt>
--   containing all of the <tt>t f</tt>s.
appendMF :: Monoidal t => t (MF t f) (MF t f) ~> MF t f

-- | Lets you convert an <tt><a>SF</a> t f</tt> into a single application
--   of <tt>f</tt> to <tt><a>MF</a> t f</tt>.
--   
--   Analogous to a function <tt><a>NonEmpty</a> a -&gt; (a, [a])</tt>
--   
--   Note that this is not reversible in general unless we have
--   <tt><a>Matchable</a> t</tt>.
splitSF :: Monoidal t => SF t f ~> t f (MF t f)

-- | Embed a direct application of <tt>f</tt> to itself into a
--   <tt><a>MF</a> t f</tt>.
toMF :: Monoidal t => t f f ~> MF t f

-- | <tt><a>SF</a> t f</tt> is "one or more <tt>f</tt>s", and <tt>'MF t
--   f</tt> is "zero or more <tt>f</tt>s". This function lets us convert
--   from one to the other.
--   
--   This is analogous to a function <tt><a>NonEmpty</a> a -&gt; [a]</tt>.
--   
--   Note that because <tt>t</tt> is not inferrable from the input or
--   output type, you should call this using <i>-XTypeApplications</i>:
--   
--   <pre>
--   <a>fromSF</a> @(<a>:*:</a>) :: <a>NonEmptyF</a> f a -&gt; <a>ListF</a> f a
--   fromSF @<a>Comp</a>  :: <a>Free1</a> f a -&gt; <a>Free</a> f a
--   </pre>
fromSF :: Monoidal t => SF t f ~> MF t f

-- | If we have an <tt><a>I</a> t</tt>, we can generate an <tt>f</tt> based
--   on how it interacts with <tt>t</tt>.
--   
--   Specialized (and simplified), this type is:
--   
--   <pre>
--   <a>pureT</a> @<a>Day</a>   :: <a>Applicative</a> f =&gt; <a>Identity</a> a -&gt; f a  -- <a>pure</a>
--   pureT @<a>Comp</a>  :: <a>Monad</a> f =&gt; Identity a -&gt; f a        -- <a>return</a>
--   pureT @(<a>:*:</a>) :: <a>Plus</a> f =&gt; <a>Proxy</a> a -&gt; f a            -- <a>zero</a>
--   </pre>
--   
--   Note that because <tt>t</tt> appears nowhere in the input or output
--   types, you must always use this with explicit type application syntax
--   (like <tt>pureT @Day</tt>)
pureT :: (Monoidal t, CM t f) => I t ~> f

-- | If we have a constraint on the <a>Monoidal</a> satisfied, it should
--   also imply the constraint on the <a>Semigroupoidal</a>.
--   
--   This is basically saying that <tt><a>C</a> (<a>SF</a> t)</tt> should
--   be a superclass of <tt><a>C</a> (<a>MF</a> t)</tt>.
--   
--   For example, for <a>:*:</a>, this type signature says that <a>Alt</a>
--   is a superclass of <a>Plus</a>, so whenever you have <a>Plus</a>, you
--   should always also have <a>Alt</a>.
--   
--   For <a>Day</a>, this type signature says that <a>Apply</a> is a
--   superclass of <a>Applicative</a>, so whenever you have
--   <a>Applicative</a>, you should always also have <a>Apply</a>.
--   
--   This is necessary because in the current class hierarchy, <a>Apply</a>
--   isn't a true superclass of <a>Applicative</a>. <a>upgradeC</a>
--   basically "imbues" <tt>f</tt> with an <a>Apply</a> instance based on
--   its <a>Applicative</a> instance, so things can be easier to use.
--   
--   For example, let's say I have a type <tt>Parser</tt> that is an
--   <a>Applicative</a> instance, but the source library does not define an
--   <a>Apply</a> instance. I cannot use <a>biretract</a> or
--   <a>binterpret</a> with it, even though I should be able to, because
--   they require <a>Apply</a>.
--   
--   That is:
--   
--   <pre>
--   <a>biretract</a> :: <a>Day</a> Parser Parser a -&gt; Parser a
--   </pre>
--   
--   is a type error, because it requires <tt><a>Apply</a> Parser</tt>.
--   
--   But, if we know that <tt>Parser</tt> has an <a>Applicative</a>
--   instance, we can use:
--   
--   <pre>
--   <a>upgradeC</a> @<a>Day</a> (<a>Proxy</a> @Parser) <a>biretract</a>
--     :: Day Parser Parser a -&gt; a
--   </pre>
--   
--   and this will now typecheck properly.
--   
--   Ideally, <tt>Parser</tt> would also have an <a>Apply</a> instance. But
--   we cannot control this if an external library defines <tt>Parser</tt>.
--   
--   (Alternatively you can just use <a>biretractT</a>.)
--   
--   Note that you should only use this if <tt>f</tt> doesn't already have
--   the <a>SF</a> constraint. If it does, this could lead to conflicting
--   instances. Only use this with <i>specific</i>, concrete <tt>f</tt>s.
--   Otherwise this is unsafe and can possibly break coherence guarantees.
--   
--   The <tt>proxy</tt> argument can be provided using something like
--   <tt><a>Proxy</a> @f</tt>, to specify which <tt>f</tt> you want to
--   upgrade.
upgradeC :: (Monoidal t, CM t f) => proxy f -> (CS t f => r) -> r

-- | Convenient alias for the constraint required for <a>inL</a>,
--   <a>inR</a>, <a>pureT</a>, etc.
--   
--   It's usually a constraint on the target/result context of
--   interpretation that allows you to "exit" or "run" a
--   <tt><a>Monoidal</a> t</tt>.
type CM t = C (MF t)

-- | Create the "empty <a>MF</a>@.
--   
--   If <tt><a>MF</a> t f</tt> represents multiple applications of <tt>t
--   f</tt> with itself, then <tt>nilMF</tt> gives us "zero applications of
--   <tt>f</tt>".
--   
--   Note that <tt>t</tt> cannot be inferred from the input or output type
--   of <a>nilMF</a>, so this function must always be called with
--   -XTypeApplications:
--   
--   <pre>
--   <a>nilMF</a> @<a>Day</a> :: <a>Identity</a> <a>~&gt;</a> <a>Ap</a> f
--   nilMF @<a>Comp</a> :: Identity ~&gt; <a>Free</a> f
--   nilMF @(<a>:*:</a>) :: <a>Proxy</a> ~&gt; <a>ListF</a> f
--   </pre>
nilMF :: forall t f. Monoidal t => I t ~> MF t f

-- | Lets us "cons" an application of <tt>f</tt> to the front of an
--   <tt><a>MF</a> t f</tt>.
consMF :: Monoidal t => t f (MF t f) ~> MF t f

-- | Convenient wrapper over <a>intro1</a> that lets us introduce an
--   arbitrary functor <tt>g</tt> to the right of an <tt>f</tt>.
--   
--   You can think of this as an <a>HBifunctor</a> analogue of
--   <a>inject</a>.
inL :: forall t f g. (Monoidal t, CM t g) => f ~> t f g

-- | Convenient wrapper over <a>intro2</a> that lets us introduce an
--   arbitrary functor <tt>f</tt> to the right of a <tt>g</tt>.
--   
--   You can think of this as an <a>HBifunctor</a> analogue of
--   <a>inject</a>.
inR :: forall t f g. (Monoidal t, CM t f) => g ~> t f g

-- | Convenient wrapper over <a>elim1</a> that lets us drop one of the
--   arguments of a <a>Tensor</a> for free, without requiring any extra
--   constraints (like for <a>binterpret</a>).
--   
--   See <a>prodOutL</a> for a version that does not require
--   <tt><a>Functor</a> f</tt>, specifically for <a>:*:</a>.
outL :: (Tensor t, I t ~ Proxy, Functor f) => t f g ~> f

-- | Convenient wrapper over <a>elim2</a> that lets us drop one of the
--   arguments of a <a>Tensor</a> for free, without requiring any
--   constraints (like for <a>binterpret</a>).
--   
--   See <a>prodOutR</a> for a version that does not require
--   <tt><a>Functor</a> g</tt>, specifically for <a>:*:</a>.
outR :: (Tensor t, I t ~ Proxy, Functor g) => t f g ~> g

-- | A covariant <a>Functor</a> suitable for Yoneda reduction
data Coyoneda (f :: Type -> Type) a
[Coyoneda] :: forall (f :: Type -> Type) a b. () => (b -> a) -> f b -> Coyoneda f a

-- | A list of <tt>f a</tt>s. Can be used to describe a product of many
--   different values of type <tt>f a</tt>.
--   
--   This is the Free <a>Plus</a>.
newtype ListF f a
ListF :: [f a] -> ListF f a
[runListF] :: ListF f a -> [f a]

-- | A non-empty list of <tt>f a</tt>s. Can be used to describe a product
--   between many different possible values of type <tt>f a</tt>.
--   
--   Essentially:
--   
--   <pre>
--   <a>NonEmptyF</a> f
--       ~ f                          -- one f
--     <a>:+:</a> (f <a>:*:</a> f)              -- two f's
--     :+: (f :*: f :*: f)            -- three f's
--     :+: (f :*: f :*: f :*: f)      -- four f's
--     :+: ...                        -- etc.
--   </pre>
--   
--   This is the Free <a>Plus</a>.
newtype NonEmptyF f a
NonEmptyF :: NonEmpty (f a) -> NonEmptyF f a
[runNonEmptyF] :: NonEmptyF f a -> NonEmpty (f a)

-- | A maybe <tt>f a</tt>.
--   
--   Can be useful for describing a "an <tt>f a</tt> that may or may not be
--   there".
--   
--   This is the free structure for a "fail"-like typeclass that would only
--   have <tt>zero :: f a</tt>.
newtype MaybeF f a
MaybeF :: Maybe (f a) -> MaybeF f a
[runMaybeF] :: MaybeF f a -> Maybe (f a)

-- | A map of <tt>f a</tt>s, indexed by keys of type <tt>k</tt>. It can be
--   useful for represeting a product of many different values of type
--   <tt>f a</tt>, each "at" a different <tt>k</tt> location.
--   
--   Can be considered a combination of <a>EnvT</a> and <a>ListF</a>, in a
--   way --- a <tt><a>MapF</a> k f a</tt> is like a <tt><a>ListF</a>
--   (<a>EnvT</a> k f) a</tt> with unique (and ordered) keys.
--   
--   One use case might be to extend a schema with many "options", indexed
--   by some string.
--   
--   For example, if you had a command line argument parser for a single
--   command
--   
--   <pre>
--   data Command a
--   </pre>
--   
--   Then you can represent a command line argument parser for
--   <i>multiple</i> named commands with
--   
--   <pre>
--   type Commands = <a>MapF</a> <a>String</a> Command
--   </pre>
--   
--   See <a>NEMapF</a> for a non-empty variant, if you want to enforce that
--   your bag has at least one <tt>f a</tt>.
newtype MapF k f a
MapF :: Map k (f a) -> MapF k f a
[runMapF] :: MapF k f a -> Map k (f a)

-- | A non-empty map of <tt>f a</tt>s, indexed by keys of type <tt>k</tt>.
--   It can be useful for represeting a product of many different values of
--   type <tt>f a</tt>, each "at" a different <tt>k</tt> location, where
--   you need to have at least one <tt>f a</tt> at all times.
--   
--   Can be considered a combination of <a>EnvT</a> and <a>NonEmptyF</a>,
--   in a way --- an <tt><a>NEMapF</a> k f a</tt> is like a
--   <tt><a>NonEmptyF</a> (<a>EnvT</a> k f) a</tt> with unique (and
--   ordered) keys.
--   
--   See <a>MapF</a> for some use cases.
newtype NEMapF k f a
NEMapF :: NEMap k (f a) -> NEMapF k f a
[runNEMapF] :: NEMapF k f a -> NEMap k (f a)

-- | The free <a>Applicative</a> for a <a>Functor</a> <tt>f</tt>.
data Ap (f :: Type -> Type) a

-- | One or more <tt>f</tt>s convolved with itself.
--   
--   Essentially:
--   
--   <pre>
--   <a>Ap1</a> f
--       ~ f                            -- one f
--     <a>:+:</a> (f `<tt>Day'</tt> f)          -- two f's
--     :+: (f `Day` f `Day` f)           -- three f's
--     :+: (f `Day` f `Day` f `Day` f)  -- four f's
--     :+: ...                          -- etc.
--   </pre>
--   
--   Useful if you want to promote an <tt>f</tt> to a situation with "at
--   least one <tt>f</tt> sequenced with itself".
--   
--   Mostly useful for its <a>HFunctor</a> and <a>Interpret</a> instance,
--   along with its relationship with <a>Ap</a> and <a>Day</a>.
--   
--   This is the free <a>Apply</a> --- Basically a "non-empty" <a>Ap</a>.
--   
--   The construction here is based on <a>Ap</a>, similar to now
--   <a>NonEmpty</a> is built on list.
data Ap1 :: (Type -> Type) -> Type -> Type
[Ap1] :: f a -> Ap f (a -> b) -> Ap1 f b
data Alt (f :: Type -> Type) a

-- | A <tt><a>Free</a> f</tt> is <tt>f</tt> enhanced with "sequential
--   binding" capabilities. It allows you to sequence multiple <tt>f</tt>s
--   one after the other, and also to determine "what <tt>f</tt> to
--   sequence" based on the result of the computation so far.
--   
--   Essentially, you can think of this as "giving <tt>f</tt> a
--   <a>Monad</a> instance", with all that that entails (<a>return</a>,
--   <a>&gt;&gt;=</a>, etc.).
--   
--   Lift <tt>f</tt> into it with <tt><a>inject</a> :: f a -&gt; Free f
--   a</tt>. When you finally want to "use" it, you can interpret it into
--   any monadic context:
--   
--   <pre>
--   <a>interpret</a>
--       :: <a>Monad</a> g
--       =&gt; (forall x. f x -&gt; g x)
--       -&gt; <a>Free</a> f a
--       -&gt; g a
--   </pre>
--   
--   Structurally, this is equivalent to many "nested" f's. A value of type
--   <tt><a>Free</a> f a</tt> is either:
--   
--   <ul>
--   <li><pre>a</pre></li>
--   <li><pre>f a</pre></li>
--   <li><pre>f (f a)</pre></li>
--   <li><pre>f (f (f a))</pre></li>
--   <li>.. etc.</li>
--   </ul>
--   
--   Under the hood, this is the Church-encoded Freer monad. It's
--   <a>Free</a>, or <a>F</a>, but in a way that is compatible with
--   <a>HFunctor</a> and <a>Interpret</a>.
data Free f a

-- | The Free <a>Bind</a>. Imbues any functor <tt>f</tt> with a <a>Bind</a>
--   instance.
--   
--   Conceptually, this is "<a>Free</a> without pure". That is, while
--   normally <tt><a>Free</a> f a</tt> is an <tt>a</tt>, a <tt>f a</tt>, a
--   <tt>f (f a)</tt>, etc., a <tt><a>Free1</a> f a</tt> is an <tt>f
--   a</tt>, <tt>f (f a)</tt>, <tt>f (f (f a))</tt>, etc. It's a
--   <a>Free</a> with "at least one layer of <tt>f</tt>", excluding the
--   <tt>a</tt> case.
--   
--   It can be useful as the semigroup formed by <a>:.:</a> (functor
--   composition): Sometimes we want an <tt>f :.: f</tt>, or an <tt>f :.: f
--   :.: f</tt>, or an <tt>f :.: f :.: f :.: f</tt>...just as long as we
--   have at least one <tt>f</tt>.
data Free1 f a

-- | Applicative functor formed by adding pure computations to a given
--   applicative functor.
data Lift (f :: Type -> Type) a

-- | An <tt>f a</tt>, along with a <a>Natural</a> index.
--   
--   <pre>
--   <a>Step</a> f a ~ (<a>Natural</a>, f a)
--   Step f   ~ ((,) Natural) <a>:.:</a> f       -- functor composition
--   </pre>
--   
--   It is the fixed point of infinite applications of <a>:+:</a> (functor
--   sums).
--   
--   Intuitively, in an infinite <tt>f :+: f :+: f :+: f ...</tt>, you have
--   exactly one <tt>f</tt> <i>somewhere</i>. A <tt><a>Step</a> f a</tt>
--   has that <tt>f</tt>, with a <a>Natural</a> giving you "where" the
--   <tt>f</tt> is in the long chain.
--   
--   Can be useful for using with the <a>Monoidal</a> instance of
--   <a>:+:</a>.
--   
--   <a>interpret</a>ing it requires no constraint on the target context.
--   
--   Note that this type and its instances equivalent to <tt><a>EnvT</a>
--   (<a>Sum</a> <a>Natural</a>)</tt>.
data Step f a
Step :: Natural -> f a -> Step f a
[stepPos] :: Step f a -> Natural
[stepVal] :: Step f a -> f a

-- | A non-empty map of <a>Natural</a> to <tt>f a</tt>. Basically, contains
--   multiple <tt>f a</tt>s, each at a given <a>Natural</a> index.
--   
--   <pre>
--   Steps f a ~ <a>Map</a> <a>Natural</a> (f a)
--   Steps f   ~ <a>Map</a> <a>Natural</a> <a>:.:</a> f       -- functor composition
--   </pre>
--   
--   It is the fixed point of applications of <a>TheseT</a>.
--   
--   You can think of this as an infinite sparse array of <tt>f a</tt>s.
--   
--   Intuitively, in an infinite <tt>f `TheseT` f `TheseT` f `TheseT` f
--   ...</tt>, each of those infinite positions may have an <tt>f</tt> in
--   them. However, because of the at-least-one nature of <a>TheseT</a>, we
--   know we have at least one f at one position <i>somewhere</i>.
--   
--   A <tt><a>Steps</a> f a</tt> has potentially many <tt>f</tt>s, each
--   stored at a different <a>Natural</a> position, with the guaruntee that
--   at least one <tt>f</tt> exists.
--   
--   Can be useful for using with the <a>Monoidal</a> instance of
--   <a>TheseT</a>.
--   
--   <a>interpret</a>ing it requires at least an <a>Alt</a> instance in the
--   target context, since we have to handle potentially more than one
--   <tt>f</tt>.
--   
--   This type is essentailly the same as <tt><a>NEMapF</a> (<a>Sum</a>
--   <a>Natural</a>)</tt> (except with a different <a>Semigroup</a>
--   instance).
newtype Steps f a
Steps :: NEMap Natural (f a) -> Steps f a
[getSteps] :: Steps f a -> NEMap Natural (f a)

-- | The functor combinator that forgets all structure in the input.
--   Ignores the input structure and stores no information.
--   
--   Acts like the "zero" with respect to functor combinator composition.
--   
--   <pre>
--   <a>ComposeT</a> ProxyF f      ~ ProxyF
--   <a>ComposeT</a> f      ProxyF ~ ProxyF
--   </pre>
--   
--   It can be <a>inject</a>ed into (losing all information), but it is
--   impossible to ever <a>retract</a> or <a>interpret</a> it.
--   
--   This is essentially <tt><a>ConstF</a> ()</tt>.
data ProxyF f a
ProxyF :: ProxyF f a

-- | Functor combinator that forgets all structure on the input, and
--   instead stores a value of type <tt>e</tt>.
--   
--   Like <a>ProxyF</a>, acts like a "zero" with functor combinator
--   composition.
--   
--   It can be <a>inject</a>ed into (losing all information), but it is
--   impossible to ever <a>retract</a> or <a>interpret</a> it.
data ConstF e f a
ConstF :: e -> ConstF e f a
[getConstF] :: ConstF e f a -> e
data EnvT e (w :: Type -> Type) a
EnvT :: e -> w a -> EnvT e a

-- | The reader monad transformer, which adds a read-only environment to
--   the given monad.
--   
--   The <a>return</a> function ignores the environment, while
--   <tt>&gt;&gt;=</tt> passes the inherited environment to both
--   subcomputations.
newtype ReaderT r (m :: k -> Type) (a :: k) :: forall k. () => Type -> k -> Type -> k -> Type
ReaderT :: (r -> m a) -> ReaderT r
[runReaderT] :: ReaderT r -> r -> m a

-- | An <tt>f a</tt>, along with a <a>Bool</a> flag
--   
--   <pre>
--   <a>Flagged</a> f a ~ (<a>Bool</a>, f a)
--   Flagged f   ~ ((,) Bool) <a>:.:</a> f       -- functor composition
--   </pre>
--   
--   Creation with <a>inject</a> or <a>pure</a> uses <a>False</a> as the
--   boolean.
--   
--   You can think of it as an <tt>f a</tt> that is "flagged" with a
--   boolean value, and that value can indicuate whether or not it is
--   "pure" (made with <a>inject</a> or <a>pure</a>) as <a>False</a>, or
--   "impure" (made from some other source) as <a>True</a>. However,
--   <a>False</a> may be always created directly, of course, using the
--   constructor.
--   
--   You can think of it like a <a>Step</a> that is either 0 or 1, as well.
--   
--   <a>interpret</a>ing it requires no constraint on the target context.
--   
--   This type is equivalent (along with its instances) to:
--   
--   <ul>
--   <li><pre><a>HLift</a> <a>IdentityT</a></pre></li>
--   <li><pre><a>EnvT</a> <a>Any</a></pre></li>
--   </ul>
data Flagged f a
Flagged :: Bool -> f a -> Flagged f a
[flaggedFlag] :: Flagged f a -> Bool
[flaggedVal] :: Flagged f a -> f a

-- | The trivial monad transformer, which maps a monad to an equivalent
--   monad.
newtype IdentityT (f :: k -> Type) (a :: k) :: forall k. () => k -> Type -> k -> Type
IdentityT :: f a -> IdentityT
[runIdentityT] :: IdentityT -> f a

-- | <tt><a>Void2</a> a b</tt> is uninhabited for all <tt>a</tt> and
--   <tt>b</tt>.
data Void2 a b

-- | A simple way to inject/reject into any eventual typeclass.
--   
--   In a way, this is the "ultimate" multi-purpose <a>Interpret</a>
--   instance. You can use this to inject an <tt>f</tt> into a free
--   structure of any typeclass. If you want <tt>f</tt> to have a
--   <a>Monad</a> instance, for example, just use
--   
--   <pre>
--   <a>inject</a> :: f a -&gt; <a>Final</a> <a>Monad</a> f a
--   </pre>
--   
--   When you want to eventually interpret out the data, use:
--   
--   <pre>
--   <a>interpret</a> :: (f <a>~&gt;</a> g) -&gt; <a>Final</a> c f a -&gt; g a
--   </pre>
--   
--   Essentially, <tt><a>Final</a> c</tt> is the "free c". <tt><a>Final</a>
--   <a>Monad</a></tt> is the free <a>Monad</a>, etc.
--   
--   <a>Final</a> can theoretically replace <a>Ap</a>, <a>Ap1</a>,
--   <a>ListF</a>, <a>NonEmptyF</a>, <a>MaybeF</a>, <a>Free</a>,
--   <a>Identity</a>, <a>Coyoneda</a>, and other instances of
--   <a>FreeOf</a>, if you don't care about being able to pattern match on
--   explicit structure.
--   
--   However, it cannot replace <a>Interpret</a> instances that are not
--   free structures, like <a>Step</a>, <a>Steps</a>, <a>Backwards</a>,
--   etc.
--   
--   Note that this doesn't have instances for <i>all</i> the typeclasses
--   you could lift things into; you probably have to define your own if
--   you want to use <tt><a>Final</a> c</tt> as an <i>instance</i> of
--   <tt>c</tt> (using <a>liftFinal0</a>, <a>liftFinal1</a>,
--   <a>liftFinal2</a> for help).
newtype Final c f a
Final :: (forall g. c g => (forall x. f x -> g x) -> g a) -> Final c f a
[runFinal] :: Final c f a -> forall g. c g => (forall x. f x -> g x) -> g a

-- | A typeclass associating a free structure with the typeclass it is free
--   on.
--   
--   This essentially lists instances of <a>Interpret</a> where a "trip"
--   through <a>Final</a> will leave it unchanged.
--   
--   <pre>
--   <a>fromFree</a> . <a>toFree</a> == id
--   <a>toFree</a> . <a>fromFree</a> == id
--   </pre>
--   
--   This can be useful because <a>Final</a> doesn't have a concrete
--   structure that you can pattern match on and inspect, but <tt>t</tt>
--   might. This lets you work on a concrete structure if you desire.
class Interpret t => FreeOf c t | t -> c
fromFree :: FreeOf c t => t f ~> Final c f
toFree :: (FreeOf c t, Functor f) => Final c f ~> t f
fromFree :: (FreeOf c t, C t (Final c f)) => t f ~> Final c f
toFree :: (FreeOf c t, c (t f)) => Final c f ~> t f

-- | Composition of monad transformers.
newtype ComposeT (f :: Type -> Type -> Type -> Type) (g :: Type -> Type -> Type -> Type) (m :: Type -> Type) a
ComposeT :: f (g m) a -> ComposeT a
[getComposeT] :: ComposeT a -> f (g m) a
infixr 9 `ComposeT`
infixr 9 `ComposeT`

-- | The Day convolution of two covariant functors.
data Day (f :: Type -> Type) (g :: Type -> Type) a
[Day] :: forall (f :: Type -> Type) (g :: Type -> Type) a b c. () => f b -> g c -> (b -> c -> a) -> Day f g a

-- | Products: encode multiple arguments to constructors
data (:*:) (f :: k -> Type) (g :: k -> Type) (p :: k) :: forall k. () => k -> Type -> k -> Type -> k -> Type
(:*:) :: f p -> g p -> (:*:)
infixr 6 :*:
infixr 6 :*:

-- | <a>outL</a> for <a>:*:</a> actually does not require <a>Functor</a>.
--   This is the more general version.
prodOutL :: (f :*: g) ~> f

-- | <a>outR</a> for <a>:*:</a> actually does not require <a>Functor</a>.
--   This is the more general version.
prodOutR :: (f :*: g) ~> g

-- | Sums: encode choice between constructors
data (:+:) (f :: k -> Type) (g :: k -> Type) (p :: k) :: forall k. () => k -> Type -> k -> Type -> k -> Type
L1 :: f p -> (:+:)
R1 :: g p -> (:+:)
infixr 5 :+:

-- | Void: used for datatypes without constructors
data V1 (p :: k) :: forall k. () => k -> Type
data These1 (f :: Type -> Type) (g :: Type -> Type) a
This1 :: f a -> These1 a
That1 :: g a -> These1 a
These1 :: f a -> g a -> These1 a

-- | Functor composition. <tt><a>Comp</a> f g a</tt> is equivalent to <tt>f
--   (g a)</tt>, and the <a>Comp</a> pattern synonym is a way of getting
--   the <tt>f (g a)</tt> in a <tt><a>Comp</a> f g a</tt>.
--   
--   For example, <tt><a>Maybe</a> (<a>IO</a> <a>Bool</a>)</tt> is
--   <tt><a>Comp</a> <a>Maybe</a> <a>IO</a> <a>Bool</a></tt>.
--   
--   This is mostly useful for its typeclass instances: in particular,
--   <a>Functor</a>, <a>Applicative</a>, <a>HBifunctor</a>, and
--   <a>Monoidal</a>.
--   
--   This is essentially a version of <a>:.:</a> and <a>Compose</a> that
--   allows for an <a>HBifunctor</a> instance.
--   
--   It is slightly less performant. Using <tt><a>comp</a> .
--   <a>unComp</a></tt> every once in a while will concretize a <a>Comp</a>
--   value (if you have <tt><a>Functor</a> f</tt>) and remove some
--   indirection if you have a lot of chained operations.
--   
--   The "free monoid" over <a>Comp</a> is <a>Free</a>, and the "free
--   semigroup" over <a>Comp</a> is <a>Free1</a>.
data Comp f g a

-- | An <a>HBifunctor</a> that ignores its second input. Like a <a>:+:</a>
--   with no <a>R1</a>/right branch.
--   
--   This is <a>Joker</a> from <a>Data.Bifunctors.Joker</a>, but given a
--   more sensible name for its purpose.
newtype LeftF f g a
LeftF :: f a -> LeftF f g a
[runLeftF] :: LeftF f g a -> f a

-- | An <a>HBifunctor</a> that ignores its first input. Like a <a>:+:</a>
--   with no <a>L1</a>/left branch.
--   
--   In its polykinded form (on <tt>f</tt>), it is essentially a
--   higher-order version of <a>Tagged</a>.
newtype RightF f g a
RightF :: g a -> RightF f g a
[runRightF] :: RightF f g a -> g a

-- | An "<a>HFunctor</a> combinator" that enhances an <a>HFunctor</a> with
--   the ability to hold a single <tt>f a</tt>. This is the higher-order
--   analogue of <a>Lift</a>.
--   
--   You can think of it as a free <a>Inject</a> for any <tt>f</tt>.
--   
--   Note that <tt><a>HLift</a> <a>IdentityT</a></tt> is equivalent to
--   <tt><a>EnvT</a> <a>Any</a></tt>.
data HLift t f a
HPure :: f a -> HLift t f a
HOther :: t f a -> HLift t f a

-- | An "<a>HFunctor</a> combinator" that turns an <a>HFunctor</a> into
--   potentially infinite nestings of that <a>HFunctor</a>.
--   
--   An <tt><a>HFree</a> t f a</tt> is either <tt>f a</tt>, <tt>t f a</tt>,
--   <tt>t (t f) a</tt>, <tt>t (t (t f)) a</tt>, etc.
--   
--   This effectively turns <tt>t</tt> into a tree with <tt>t</tt>
--   branches.
--   
--   One particularly useful usage is with <a>MapF</a>. For example if you
--   had a data type representing a command line command parser:
--   
--   <pre>
--   data Command a
--   </pre>
--   
--   You could represent "many possible named commands" using
--   
--   <pre>
--   type Commands = <a>MapF</a> <a>String</a> Command
--   </pre>
--   
--   And you can represent multiple <i>nested</i> named commands using:
--   
--   <pre>
--   type NestedCommands = <a>HFree</a> (<a>MapF</a> <a>String</a>)
--   </pre>
--   
--   This has an <a>Interpret</a> instance, but it can be more useful to
--   use via direct pattern matching, or through
--   
--   <pre>
--   <a>foldHFree</a>
--       :: <a>HBifunctor</a> t
--       =&gt; f <a>~&gt;</a> g
--       -&gt; t g ~&gt; g
--       -&gt; HFree t f ~&gt; g
--   </pre>
--   
--   which requires no extra constriant on <tt>g</tt>, and lets you
--   consider each branch separately.
--   
--   This can be considered the higher-oder analogue of <a>Free</a>; it is
--   the free <a>HBind</a> for any <tt><a>HFunctor</a> t</tt>.
--   
--   Note that <tt><a>HFree</a> <a>IdentityT</a></tt> is equivalent to
--   <a>Step</a>.
data HFree t f a
HReturn :: f a -> HFree t f a
HJoin :: t (HFree t f) a -> HFree t f a

-- | Turn <a>Identity</a> into any <tt><a>Applicative</a> f</tt>. Can be
--   useful as an argument to <a>hmap</a>, <a>hbimap</a>, or
--   <a>interpret</a>.
--   
--   It is a more general form of <a>generalize</a> from <i>mmorph</i>.
generalize :: Applicative f => Identity ~> f

-- | Natural transformation from any functor <tt>f</tt> into <a>Proxy</a>.
--   Can be useful for "zeroing out" a functor with <a>hmap</a> or
--   <a>hbimap</a> or <a>interpret</a>.
absorb :: f ~> Proxy