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

-- | Various extra monoid-related definitions and utilities
--   
--   Various extra monoid-related definitions and utilities, such as monoid
--   actions, monoid coproducts, semi-direct products, "deletable" monoids,
--   "split" monoids, and "cut" monoids.
@package monoid-extras
@version 0.7

-- | Monoid and semigroup actions.
module Data.Monoid.Action

-- | Type class for monoid (and semigroup) actions, where monoidal values
--   of type m "act" on values of another type s.
--   Instances are required to satisfy the laws
--   
--   
--   
- 
act mempty = id

--   
- 
act (m1 `mappend` m2) = act m1 . act m2

--   
--   
--   Semigroup instances are required to satisfy the second law but with
--   (<>) instead of mappend. Additionally, if the type
--   s has any algebraic structure, act m should be a
--   homomorphism. For example, if s is also a monoid we should
--   have act m mempty = mempty and act m (s1 `mappend` s2) =
--   (act m s1) `mappend` (act m s2).
--   
--   By default, act = const id, so for a type M which
--   should have no action on anything, it suffices to write
--   
--   
--   instance Action M s
--   
--   
--   with no method implementations.
--   
--   It is a bit awkward dealing with instances of Action, since
--   it is a multi-parameter type class but we can't add any functional
--   dependencies---the relationship between monoids and the types on which
--   they act is truly many-to-many. In practice, this library has chosen
--   to have instance selection for Action driven by the
--   first type parameter. That is, you should never write an
--   instance of the form Action m SomeType since it will overlap
--   with instances of the form Action SomeMonoid t. Newtype
--   wrappers can be used to (awkwardly) get around this.
class Action m s

-- | Convert a value of type m to an action on s values.
act :: Action m s => m -> s -> s

-- | Any monoid acts on itself by left multiplication. This newtype
--   witnesses this action: getRegular $ Regular m1
--   `act' Regular m2 = m1 <> m2
newtype Regular m
Regular :: m -> Regular m
[getRegular] :: Regular m -> m

-- | Any group acts on itself by conjugation.
newtype Conjugate m
Conjugate :: m -> Conjugate m
[getConjugate] :: Conjugate m -> m

-- | An action of a group is "free transitive", "regular", or a "torsor"
--   iff it is invertible.
--   
--   Given an original value sOrig, and a value sActed
--   that is the result of acting on sOrig by some m, it
--   is possible to recover this m. This is encoded in the laws:
--   
--   
--   
- 
(m `<tt>act'</tt> s) `difference' s = m

--   
- 
(sActed `<tt>difference'</tt> sOrig) `act' sOrig =
--   sActed

--   
class Group m => Torsor m s

-- | difference sActed sOrig is the element m such
--   that sActed = m `act' sOrig.
difference :: Torsor m s => s -> s -> m
instance Data.Monoid.Action.Action (GHC.Internal.Data.Semigroup.Internal.Endo a) a
instance Data.Monoid.Action.Action (GHC.Internal.Data.Monoid.First a) a
instance Data.Monoid.Action.Action (Data.Semigroup.First a) a
instance Data.Monoid.Action.Action m s => Data.Monoid.Action.Action (GHC.Internal.Data.Functor.Identity.Identity m) s
instance GHC.Internal.Num.Num a => Data.Monoid.Action.Action GHC.Num.Integer.Integer (GHC.Internal.Data.Semigroup.Internal.Product a)
instance GHC.Internal.Num.Num a => Data.Monoid.Action.Action GHC.Num.Integer.Integer (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Monoid.Action.Action m s => Data.Monoid.Action.Action [m] s
instance Data.Monoid.Action.Action m s => Data.Monoid.Action.Action (GHC.Internal.Maybe.Maybe m) s
instance GHC.Internal.Real.Fractional a => Data.Monoid.Action.Action GHC.Internal.Real.Rational (GHC.Internal.Data.Semigroup.Internal.Product a)
instance GHC.Internal.Real.Fractional a => Data.Monoid.Action.Action GHC.Internal.Real.Rational (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Monoid.Action.Action () l
instance Data.Monoid.Action.Action GHC.Internal.Base.Void a
instance Data.Group.Group m => Data.Monoid.Action.Action m (Data.Monoid.Action.Conjugate m)
instance GHC.Internal.Base.Semigroup m => Data.Monoid.Action.Action m (Data.Monoid.Action.Regular m)
instance Data.Group.Group m => Data.Monoid.Action.Torsor m (Data.Monoid.Action.Regular m)

-- | The Cut monoid transformer introduces "cut points" such that
--   all values between any two cut points are thrown away. That is,
--   
--   
--   a b c | d e | f g h i | j k  ==  a b c | j k
--   
module Data.Monoid.Cut

-- | A value of type Cut m is either a single m, or a
--   pair of m's separated by a divider. The divider represents a
--   "cut point".
--   
--   Cut is similar to Data.Monoid.Split, but split keeps
--   only the rightmost divider and accumulates all values, whereas cut
--   always keeps the leftmost and rightmost divider, coalescing them into
--   one and throwing away all the information in between.
--   
--   Split uses the asymmetric constructor :|, and
--   Cut the symmetric constructor :||:, to emphasize the
--   inherent asymmetry of Split and symmetry of Cut.
--   Split keeps only the rightmost split and combines everything
--   on the left; Cut keeps the outermost splits and throws away
--   everything in between.
data Cut m
Uncut :: m -> Cut m
(:||:) :: m -> m -> Cut m
infix 5 :||:

-- | A convenient name for mempty :||: mempty, so composing with
--   cut introduces a cut point. For example, Uncut a <>
--   cut <> Uncut b == a :||: b.
cut :: Monoid m => Cut m
instance GHC.Internal.Data.Data.Data m => GHC.Internal.Data.Data.Data (Data.Monoid.Cut.Cut m)
instance GHC.Internal.Data.Foldable.Foldable Data.Monoid.Cut.Cut
instance GHC.Internal.Base.Functor Data.Monoid.Cut.Cut
instance (GHC.Internal.Base.Semigroup m, GHC.Internal.Base.Monoid m) => GHC.Internal.Base.Monoid (Data.Monoid.Cut.Cut m)
instance GHC.Internal.Read.Read m => GHC.Internal.Read.Read (Data.Monoid.Cut.Cut m)
instance GHC.Internal.Base.Semigroup m => GHC.Internal.Base.Semigroup (Data.Monoid.Cut.Cut m)
instance GHC.Internal.Show.Show m => GHC.Internal.Show.Show (Data.Monoid.Cut.Cut m)
instance GHC.Internal.Data.Traversable.Traversable Data.Monoid.Cut.Cut

-- | A monoid transformer that allows deleting information from a
--   concatenation of monoidal values.
module Data.Monoid.Deletable

-- | If m is a Monoid, then Deletable m
--   (intuitively speaking) adds two distinguished new elements [
--   and ], such that an occurrence of [ "deletes" everything from
--   it to the next ]. For example,
--   
--   
--   abc[def]gh == abcgh
--   
--   
--   This is all you really need to know to use Deletable m
--   values; to understand the actual implementation, read on.
--   
--   To properly deal with nesting and associativity we need to be able to
--   assign meanings to things like [[, ][, and so on.
--   (We cannot just define, say, [[ == [, since then ([[)] ==
--   [] == id but [([]) == [id == [.) Formally, elements of
--   Deletable m are triples of the form (r, m, l) representing
--   words ]^r m [^l. When combining two triples (r1, m1, l1) and
--   (r2, m2, l2) there are three cases:
--   
--   
--   
- If l1 == r2 then the [s from the left and ]s from the right
--   exactly cancel, and we are left with (r1, m1 <> m2, l2).
--   
- If l1 < r2 then all of the [s cancel with some of the ]s, but
--   m1 is still inside the remaining ]s and is deleted, yielding (r1 + r2
--   - l1, m2, l2)
--   
- The remaining case is symmetric with the second.
--   
data Deletable m
Deletable :: Int -> m -> Int -> Deletable m

-- | Project the wrapped value out of a Deletable value.
unDelete :: Deletable m -> m

-- | Inject a value into a Deletable wrapper. Satisfies the property
--   
--   
--   unDelete . toDeletable === id
--   
toDeletable :: m -> Deletable m

-- | A "left bracket", which causes everything between it and the next
--   right bracket to be deleted.
deleteL :: Monoid m => Deletable m

-- | A "right bracket", denoting the end of the section that should be
--   deleted.
deleteR :: Monoid m => Deletable m
instance GHC.Internal.Data.Data.Data m => GHC.Internal.Data.Data.Data (Data.Monoid.Deletable.Deletable m)
instance GHC.Internal.Data.Foldable.Foldable Data.Monoid.Deletable.Deletable
instance GHC.Internal.Base.Functor Data.Monoid.Deletable.Deletable
instance (GHC.Internal.Base.Semigroup m, GHC.Internal.Base.Monoid m) => GHC.Internal.Base.Monoid (Data.Monoid.Deletable.Deletable m)
instance GHC.Internal.Read.Read m => GHC.Internal.Read.Read (Data.Monoid.Deletable.Deletable m)
instance GHC.Internal.Base.Semigroup m => GHC.Internal.Base.Semigroup (Data.Monoid.Deletable.Deletable m)
instance GHC.Internal.Show.Show m => GHC.Internal.Show.Show (Data.Monoid.Deletable.Deletable m)
instance GHC.Internal.Data.Traversable.Traversable Data.Monoid.Deletable.Deletable

-- | The monoid of endomorphisms over any Category.
module Data.Monoid.Endomorphism

-- | An Endomorphism in a given Category is a morphism from
--   some object to itself. The set of endomorphisms for a particular
--   object form a monoid, with composition as the combining operation and
--   the identity morphism as the identity element.
newtype Endomorphism (k :: Type -> Type -> Type) a
Endomorphism :: k a a -> Endomorphism (k :: Type -> Type -> Type) a
[getEndomorphism] :: Endomorphism (k :: Type -> Type -> Type) a -> k a a
instance (GHC.Internal.Control.Category.Category k, Data.Groupoid.Groupoid k) => Data.Group.Group (Data.Monoid.Endomorphism.Endomorphism k a)
instance (Data.Semigroupoid.Semigroupoid k, GHC.Internal.Control.Category.Category k) => GHC.Internal.Base.Monoid (Data.Monoid.Endomorphism.Endomorphism k a)
instance Data.Semigroupoid.Semigroupoid k => GHC.Internal.Base.Semigroup (Data.Monoid.Endomorphism.Endomorphism k a)
instance GHC.Internal.Show.Show (k a a) => GHC.Internal.Show.Show (Data.Monoid.Endomorphism.Endomorphism k a)

-- | Make semigroups under min or max into monoids by
--   adjoining an element corresponding to infinity (positive or negative,
--   respectively). These types are similar to Maybe (Min a) and
--   Maybe (Max a) respectively, except that the Ord
--   instance matches the Monoid instance.
module Data.Monoid.Inf

-- | Inf p a represents the type a extended with a new
--   "infinite" value, which is treated as either positive or negative
--   infinity depending on the type index p. This type exists
--   mostly for its Ord, Semigroup, and Monoid
--   instances.
data Inf p a
Infinity :: Inf p a
Finite :: a -> Inf p a

-- | Type index indicating positive infinity.
data Pos

-- | Type index indicating negative infinity.
data Neg

-- | The type a extended with positive infinity.
type PosInf a = Inf Pos a

-- | The type a extended with negative infinity.
type NegInf a = Inf Neg a

-- | Find the minimum of a list of values. Returns positive infinity iff
--   the list is empty.
minimum :: Ord a => [a] -> PosInf a

-- | Find the maximum of a list of values. Returns negative infinity iff
--   the list is empty.
maximum :: Ord a => [a] -> NegInf a

-- | Positive infinity.
posInfty :: PosInf a

-- | Negative infinity.
negInfty :: NegInf a

-- | Embed a finite value into the space of such values extended with
--   positive infinity.
posFinite :: a -> PosInf a

-- | Embed a finite value into the space of such values extended with
--   negative infinity.
negFinite :: a -> NegInf a
instance GHC.Internal.Base.Applicative (Data.Monoid.Inf.Inf p)
instance GHC.Internal.Enum.Bounded a => GHC.Internal.Enum.Bounded (Data.Monoid.Inf.NegInf a)
instance GHC.Internal.Enum.Bounded a => GHC.Internal.Enum.Bounded (Data.Monoid.Inf.PosInf a)
instance (GHC.Internal.Data.Data.Data p, GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Data.Monoid.Inf.Inf p a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Monoid.Inf.Inf p a)
instance GHC.Internal.Data.Foldable.Foldable (Data.Monoid.Inf.Inf p)
instance GHC.Internal.Base.Functor (Data.Monoid.Inf.Inf p)
instance GHC.Internal.Base.Monad (Data.Monoid.Inf.Inf p)
instance GHC.Classes.Ord a => GHC.Internal.Base.Monoid (Data.Monoid.Inf.Inf Data.Monoid.Inf.Pos a)
instance GHC.Classes.Ord a => GHC.Internal.Base.Monoid (Data.Monoid.Inf.Inf Data.Monoid.Inf.Neg a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Monoid.Inf.Inf Data.Monoid.Inf.Pos a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Monoid.Inf.Inf Data.Monoid.Inf.Neg a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Monoid.Inf.Inf p a)
instance GHC.Classes.Ord a => GHC.Internal.Base.Semigroup (Data.Monoid.Inf.Inf Data.Monoid.Inf.Pos a)
instance GHC.Classes.Ord a => GHC.Internal.Base.Semigroup (Data.Monoid.Inf.Inf Data.Monoid.Inf.Neg a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Monoid.Inf.Inf p a)
instance GHC.Internal.Data.Traversable.Traversable (Data.Monoid.Inf.Inf p)

-- | Heterogeneous lists of monoids.
module Data.Monoid.MList
type a ::: l = (Maybe a, l)
infixr 5 :::
(*:) :: a -> l -> a ::: l
infixr 5 *:

-- | Type class for heterogeneous monoidal lists, with a single method
--   allowing construction of an empty list.
class MList l

-- | The empty heterogeneous list of type l. Of course,
--   empty == mempty, but unlike mempty,
--   empty does not require Monoid constraints on all the
--   elements of l.
empty :: MList l => l

-- | The relation l :>: a holds when a is the type of
--   an element in l. For example, (Char ::: Int ::: Bool :::
--   Nil) :>: Int.
class l :>: a

-- | Inject a value into an otherwise empty heterogeneous list.
inj :: (:>:) l a => a -> l

-- | Get the value of type a from a heterogeneous list, if there
--   is one.
get :: (:>:) l a => l -> Maybe a

-- | Alter the value of type a by applying the given function to
--   it.
alt :: (:>:) l a => (Maybe a -> Maybe a) -> l -> l

-- | SM, an abbreviation for "single monoid" (as opposed to a
--   heterogeneous list of monoids), is only used internally to help guide
--   instance selection when defining the action of heterogeneous monoidal
--   lists on each other.
newtype SM m
SM :: m -> SM m
instance Data.Monoid.MList.MList t => (a Data.Monoid.MList.::: t) Data.Monoid.MList.:>: a
instance (t Data.Monoid.MList.:>: a) => (b Data.Monoid.MList.::: t) Data.Monoid.MList.:>: a
instance (Data.Monoid.Action.Action a a', Data.Monoid.Action.Action (Data.Monoid.MList.SM a) l) => Data.Monoid.Action.Action (Data.Monoid.MList.SM a) (GHC.Internal.Maybe.Maybe a', l)
instance Data.Monoid.Action.Action (Data.Monoid.MList.SM a) ()
instance (Data.Monoid.Action.Action (Data.Monoid.MList.SM a) l2, Data.Monoid.Action.Action l1 l2) => Data.Monoid.Action.Action (a, l1) l2
instance Data.Monoid.MList.MList l => Data.Monoid.MList.MList (a Data.Monoid.MList.::: l)
instance Data.Monoid.MList.MList ()
instance GHC.Internal.Show.Show m => GHC.Internal.Show.Show (Data.Monoid.MList.SM m)

-- | A type for representing values with an additional bit saying whether
--   the value is "just a recommendation" (to be used only if nothing
--   better comes along) or a "commitment" (to certainly be used,
--   overriding merely recommended values), along with corresponding
--   Semigroup and Monoid instances.
module Data.Monoid.Recommend

-- | A value of type Recommend a consists of a value of type
--   a wrapped up in one of two constructors. The
--   Recommend constructor indicates a "non-committal
--   recommendation"---that is, the given value should be used if no
--   other/better values are available. The Commit constructor
--   indicates a "commitment"---a value which should definitely be used,
--   overriding any Recommended values.
data Recommend a
Recommend :: a -> Recommend a
Commit :: a -> Recommend a

-- | Extract the value of type a wrapped in Recommend a.
getRecommend :: Recommend a -> a
instance GHC.Internal.Data.Data.Data a => GHC.Internal.Data.Data.Data (Data.Monoid.Recommend.Recommend a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Monoid.Recommend.Recommend a)
instance GHC.Internal.Data.Foldable.Foldable Data.Monoid.Recommend.Recommend
instance GHC.Internal.Base.Functor Data.Monoid.Recommend.Recommend
instance (GHC.Internal.Base.Semigroup a, GHC.Internal.Base.Monoid a) => GHC.Internal.Base.Monoid (Data.Monoid.Recommend.Recommend a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Monoid.Recommend.Recommend a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Monoid.Recommend.Recommend a)
instance GHC.Internal.Base.Semigroup a => GHC.Internal.Base.Semigroup (Data.Monoid.Recommend.Recommend a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Monoid.Recommend.Recommend a)
instance GHC.Internal.Data.Traversable.Traversable Data.Monoid.Recommend.Recommend

module Data.Monoid.SemiDirectProduct

-- | The semi-direct product of monoids s and m, which is
--   a monoid when m acts on s. Structurally, the
--   semi-direct product is just a pair (s,m). However, the monoid
--   instance is different. In particular, we have
--   
--   
--   (s1,m1) <> (s2,m2) = (s1 <> (m1 `act` s2), m1 <> m2)
--   
--   
--   We think of the m values as a "tag" decorating the s
--   values, which also affect the way the s values combine.
--   
--   We call the monoid m the quotient monoid and the monoid
--   s the sub-monoid of the semi-direct product. The semi-direct
--   product Semi s m is an extension of the monoid s
--   with m being the quotient.
data Semi s m
unSemi :: Semi s m -> (s, m)

-- | Tag an s value with an m value to create an element
--   of the semi-direct product.
tag :: s -> m -> Semi s m

-- | The injection map, i.e. give an s value a trivial tag.
inject :: Monoid m => s -> Semi s m

-- | Forget the monoidal tag. Of course, untag . inject = id, and
--   untag (tag s m) = s.
untag :: Semi s m -> s

-- | Embed a "tag" value as a value of type Semi s m. Note that
--   
--   
--   inject s <> embed m = tag s m
--   
--   
--   and
--   
--   embed m <> inject s = tag (act m s) m@
--   
--   The semi-direct product gives a split extension of s by
--   m. This allows us to embed m into the semi-direct
--   product. This is the embedding map. The quotient and embed maps should
--   satisfy the equation quotient . embed = id.
embed :: Monoid s => m -> Semi s m

-- | The quotient map, i.e. retrieve the monoidal tag value.
quotient :: Semi s m -> m
instance (GHC.Internal.Base.Monoid m, GHC.Internal.Base.Monoid s, Data.Monoid.Action.Action m s) => GHC.Internal.Base.Monoid (Data.Monoid.SemiDirectProduct.Semi s m)
instance (GHC.Internal.Base.Semigroup m, GHC.Internal.Base.Semigroup s, Data.Monoid.Action.Action m s) => GHC.Internal.Base.Semigroup (Data.Monoid.SemiDirectProduct.Semi s m)

-- | The coproduct of two monoids.
module Data.Monoid.Coproduct

-- | m :+: n is the coproduct of monoids m and
--   n. Values of type m :+: n consist of alternating
--   lists of m and n values. The empty list is the
--   identity, and composition is list concatenation, with appropriate
--   combining of adjacent elements and removing identities when possible.
data m :+: n

-- | Injection from the left monoid into a coproduct.
inL :: m -> m :+: n

-- | Injection from the right monoid into a coproduct.
inR :: n -> m :+: n

-- | Prepend a value from the left monoid.
mappendL :: m -> (m :+: n) -> m :+: n

-- | Prepend a value from the right monoid.
mappendR :: n -> (m :+: n) -> m :+: n

-- | Universal map of the coproduct. The name cop is an
--   abbreviation for copairing. Both functions in the signature should be
--   monoid homomorphisms. If they are general functions then the copairing
--   may not be well defined in the sense that it may send equal elements
--   to unequal elements. This is also the reason why cop is not
--   the Data.Bifoldable.bifoldMap function even though they have
--   the same signature.
cop :: Monoid k => (m -> k) -> (n -> k) -> (m :+: n) -> k

-- | killL takes a value in a coproduct monoid and sends all the
--   values from the left monoid to the identity.
killL :: Monoid n => (m :+: n) -> n

-- | killR takes a value in a coproduct monoid and sends all the
--   values from the right monoid to the identity.
killR :: Monoid m => (m :+: n) -> m

-- | Extract a monoid coproduct to a list of Either values. The
--   resulting list is guaranteed to be normalized, in the sense that it
--   will strictly alternate between Left and Right.
toAltList :: (Semigroup m, Semigroup n) => (m :+: n) -> [Either m n]

-- | Extract a monoid coproduct to a list of Either values. The
--   resulting list is guaranteed to be normalized, in the sense that it
--   will strictly alternate between Left and Right and
--   no identity element from m or n will occur in the
--   list.
toReducedAltList :: (Eq m, Eq n, Monoid m, Monoid n) => (m :+: n) -> [Either m n]

-- | Same as untangleSemi but the result is uwrapped. Concretely,
--   given a value from a coproduct monoid where the left monoid has an
--   action on the right, and "untangle" it into a pair of values. In
--   particular,
--   
--   
--   m1 <> n1 <> m2 <> n2 <> m3 <> n3 <> ...
--   
--   
--   is sent to
--   
--   
--   (m1 <> m2 <> m3 <> ..., (act m1 n1) <> (act (m1 <> m2) n2) <> (act (m1 <> m2 <> m3) n3) <> ...)
--   
--   
--   That is, before combining n values, every n value is
--   acted on by all the m values to its left.
untangle :: (Action m n, Monoid m, Monoid n) => (m :+: n) -> (m, n)

-- | The copairing of embed and inject homomorphisms into
--   the semidirect product. Note that embed and inject
--   are monoid homomorphisms. Therefore untangleSemi is also a
--   monoid homomorphism.
untangleSemi :: (Action m n, Monoid m, Monoid n) => (m :+: n) -> Semi n m
instance (Data.Monoid.Action.Action m r, Data.Monoid.Action.Action n r) => Data.Monoid.Action.Action (m Data.Monoid.Coproduct.:+: n) r
instance (GHC.Classes.Eq m, GHC.Classes.Eq n, GHC.Internal.Base.Monoid m, GHC.Internal.Base.Monoid n) => GHC.Classes.Eq (m Data.Monoid.Coproduct.:+: n)
instance GHC.Internal.Base.Monoid (m Data.Monoid.Coproduct.:+: n)
instance GHC.Internal.Base.Semigroup (m Data.Monoid.Coproduct.:+: n)
instance (GHC.Internal.Show.Show m, GHC.Internal.Show.Show n) => GHC.Internal.Show.Show (m Data.Monoid.Coproduct.:+: n)

-- | A strict version of the semi-direct product. If a monoid m acts on s
--   then this version of the semi-direct product is strict in the
--   m-portion of the semi-direct product.
module Data.Monoid.SemiDirectProduct.Strict

-- | The semi-direct product of monoids s and m, which is
--   a monoid when m acts on s. Structurally, the
--   semi-direct product is just a pair (s,m). However, the monoid
--   instance is different. In particular, we have
--   
--   
--   (s1,m1) <> (s2,m2) = (s1 <> (m1 `act` s2), m1 <> m2)
--   
--   
--   We call the monoid m the quotient monoid and the monoid
--   s the sub-monoid of the semi-direct product. The semi-direct
--   product Semi s m is an extension of the monoid s
--   with m being the quotient.
data Semi s m
unSemi :: Semi s m -> (s, m)

-- | Tag an s value with an m value to create an element
--   of the semi-direct product.
tag :: s -> m -> Semi s m

-- | The injection map, i.e. give an s value a trivial tag.
inject :: Monoid m => s -> Semi s m

-- | Forget the monoidal tag. Of course, untag . inject = id, and
--   untag (tag s m) = s.
untag :: Semi s m -> s

-- | Embed a "tag" value as a value of type Semi s m. Note that
--   
--   
--   inject s <> embed m = tag s m
--   
--   
--   and
--   
--   embed m <> inject s = tag (act m s) m@
--   
--   The semi-direct product gives a split extension of s by
--   m. This allows us to embed m into the semi-direct
--   product. This is the embedding map. The quotient and embed maps should
--   satisfy the equation quotient . embed = id.
embed :: Monoid s => m -> Semi s m

-- | The quotient map, i.e. retrieve the monoidal tag value.
quotient :: Semi s m -> m
instance (GHC.Internal.Base.Monoid m, GHC.Internal.Base.Monoid s, Data.Monoid.Action.Action m s) => GHC.Internal.Base.Monoid (Data.Monoid.SemiDirectProduct.Strict.Semi s m)
instance (GHC.Internal.Base.Semigroup m, GHC.Internal.Base.Semigroup s, Data.Monoid.Action.Action m s) => GHC.Internal.Base.Semigroup (Data.Monoid.SemiDirectProduct.Strict.Semi s m)

-- | Sometimes we want to accumulate values from some monoid, but have the
--   ability to introduce a "split" which separates values on either side.
--   Only the rightmost split is kept. For example,
--   
--   
--   a b c | d e | f g h == a b c d e | f g h
--   
--   
--   In the diagrams graphics framework this is used when accumulating
--   transformations to be applied to primitive diagrams: the
--   freeze operation introduces a split, since only
--   transformations occurring outside the freeze should be applied to
--   attributes.
module Data.Monoid.Split

-- | A value of type Split m is either a single m, or a
--   pair of m's separated by a divider. Single m's
--   combine as usual; single m's combine with split values by
--   combining with the value on the appropriate side; when two split
--   values meet only the rightmost split is kept, with both the values
--   from the left split combining with the left-hand value of the right
--   split.
--   
--   Data.Monoid.Cut is similar, but uses a different scheme for
--   composition. Split uses the asymmetric constructor
--   :|, and Cut the symmetric constructor :||:,
--   to emphasize the inherent asymmetry of Split and symmetry of
--   Cut. Split keeps only the rightmost split and
--   combines everything on the left; Cut keeps the outermost
--   splits and throws away everything in between.
data Split m
M :: m -> Split m
(:|) :: m -> m -> Split m
infix 5 :|

-- | A convenient name for mempty :| mempty, so M a <>
--   split <> M b == a :| b.
split :: Monoid m => Split m

-- | "Unsplit" a split monoid value, combining the two values into one (or
--   returning the single value if there is no split).
unsplit :: Semigroup m => Split m -> m
instance Data.Monoid.Action.Action m n => Data.Monoid.Action.Action (Data.Monoid.Split.Split m) n
instance GHC.Internal.Data.Data.Data m => GHC.Internal.Data.Data.Data (Data.Monoid.Split.Split m)
instance GHC.Classes.Eq m => GHC.Classes.Eq (Data.Monoid.Split.Split m)
instance GHC.Internal.Data.Foldable.Foldable Data.Monoid.Split.Split
instance GHC.Internal.Base.Functor Data.Monoid.Split.Split
instance (GHC.Internal.Base.Semigroup m, GHC.Internal.Base.Monoid m) => GHC.Internal.Base.Monoid (Data.Monoid.Split.Split m)
instance GHC.Internal.Read.Read m => GHC.Internal.Read.Read (Data.Monoid.Split.Split m)
instance GHC.Internal.Base.Semigroup m => GHC.Internal.Base.Semigroup (Data.Monoid.Split.Split m)
instance GHC.Internal.Show.Show m => GHC.Internal.Show.Show (Data.Monoid.Split.Split m)
instance GHC.Internal.Data.Traversable.Traversable Data.Monoid.Split.Split

-- | Convenience alias for the combination of Monoid and
--   Semigroup constraints.
module Data.Monoid.WithSemigroup

-- | For base < 4.11, the Monoid' constraint is a synonym for
--   things which are instances of both Semigroup and Monoid.
--   For base version 4.11 and onwards, Monoid has
--   Semigroup as a superclass already, so for backwards
--   compatibility Monoid' is provided as a synonym for
--   Monoid.
type Monoid' = Monoid

module Data.Semigroup.Coproduct

-- | m :+. n is the coproduct of semigroups m and
--   n. Values of type m :+. n consist of alternating
--   non-empty lists of m and n values. Composition is
--   list concatenation, with appropriate combining of adjacent elements
data m :+. n

-- | Injection from the left semigroup into a coproduct.
inL :: m -> m :+. n

-- | Injection from the right semigroup into a coproduct.
inR :: n -> m :+. n

-- | Universal map of the coproduct. The name cop is an
--   abbreviation for copairing. Both functions in the signature should be
--   semigroup homomorphisms. If they are general functions then the
--   copairing may not be well defined in the sense that it may send equal
--   elements to unequal elements. This is also the reason why cop
--   is not the Data.Bifoldable1.bifoldMap1 function even though
--   they have the same signature.
cop :: Semigroup k => (m -> k) -> (n -> k) -> (m :+. n) -> k

-- | Extract a semigroup coproduct to a non-empty list of Either
--   values. The resulting list is guaranteed to be normalized, in the
--   sense that it will strictly alternate between Left and
--   Right.
toAltList :: (Semigroup m, Semigroup n) => (m :+. n) -> NonEmpty (Either m n)

-- | Given monoids m and n, we can form their semigroup
--   coproduct m :+. n. Every monoid homomorphism is a semigroup
--   homomorphism. In particular the canonical inections of the monoid
--   coproduct from m and n into m :+: n are
--   semigroup homomorphisms. By pairing them using the universal property
--   of the semigroup coproduct we obtain a canonical semigroup
--   homomorphism toMonoid from m :+. n to m :+:
--   n.
toMonoid :: (Monoid m, Monoid n) => (m :+. n) -> m :+: n
instance (Data.Monoid.Action.Action m r, Data.Monoid.Action.Action n r) => Data.Monoid.Action.Action (m Data.Semigroup.Coproduct.:+. n) r
instance (GHC.Classes.Eq m, GHC.Classes.Eq n, GHC.Internal.Base.Semigroup m, GHC.Internal.Base.Semigroup n) => GHC.Classes.Eq (m Data.Semigroup.Coproduct.:+. n)
instance GHC.Internal.Base.Semigroup (m Data.Semigroup.Coproduct.:+. n)
instance (GHC.Internal.Show.Show m, GHC.Internal.Show.Show n) => GHC.Internal.Show.Show (m Data.Semigroup.Coproduct.:+. n)
