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


-- | Subclasses of Monoid
--   
--   A hierarchy of subclasses of <a>Monoid</a> together with their
--   instances for all data structures from base, containers, and text
--   packages.
@package monoid-subclasses
@version 1.2.6


-- | This module defines the MonoidNull class and some of its instances.
module Data.Monoid.Null

-- | Extension of <a>Monoid</a> that allows testing a value for equality
--   with <a>mempty</a>. The following law must hold:
--   
--   <pre>
--   null x == (x == mempty)
--   </pre>
--   
--   Furthermore, the performance of this method should be constant,
--   <i>i.e.</i>, independent of the length of its argument.
class Monoid m => MonoidNull m
null :: MonoidNull m => m -> Bool
($dmnull) :: (MonoidNull m, Eq m) => m -> Bool

-- | Subclass of <a>Monoid</a> for types whose values have no inverse, with
--   the exception of <a>mempty</a>. More formally, the class instances
--   must satisfy the following law:
--   
--   <pre>
--   null (x &lt;&gt; y) == (null x &amp;&amp; null y)
--   </pre>
class MonoidNull m => PositiveMonoid m
instance (Data.Monoid.Null.MonoidNull (f p), Data.Monoid.Null.MonoidNull (g p)) => Data.Monoid.Null.MonoidNull ((GHC.Internal.Generics.:*:) f g p)
instance Data.Monoid.Null.MonoidNull (f (g p)) => Data.Monoid.Null.MonoidNull ((GHC.Internal.Generics.:.:) f g p)
instance Data.Monoid.Null.MonoidNull GHC.Internal.Data.Semigroup.Internal.All
instance Data.Monoid.Null.MonoidNull GHC.Internal.Data.Semigroup.Internal.Any
instance Data.Monoid.Null.MonoidNull Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.Null.MonoidNull Data.ByteString.Internal.Type.ByteString
instance Data.Monoid.Null.MonoidNull (f (g a)) => Data.Monoid.Null.MonoidNull (Data.Functor.Compose.Compose f g a)
instance Data.Monoid.Null.MonoidNull a => Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.Null.MonoidNull a => Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Ord.Down a)
instance Data.Monoid.Null.MonoidNull a => Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Monoid.First a)
instance Data.Monoid.Null.MonoidNull a => Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.Null.MonoidNull (Data.IntMap.Internal.IntMap v)
instance Data.Monoid.Null.MonoidNull Data.IntSet.Internal.IntSet
instance Data.Monoid.Null.MonoidNull c => Data.Monoid.Null.MonoidNull (GHC.Internal.Generics.K1 i c p)
instance Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Monoid.Last a)
instance Data.Monoid.Null.MonoidNull [x]
instance Data.Monoid.Null.MonoidNull (f p) => Data.Monoid.Null.MonoidNull (GHC.Internal.Generics.M1 i c f p)
instance GHC.Classes.Ord k => Data.Monoid.Null.MonoidNull (Data.Map.Internal.Map k v)
instance (GHC.Classes.Ord a, GHC.Internal.Enum.Bounded a) => Data.Monoid.Null.MonoidNull (Data.Semigroup.Max a)
instance GHC.Internal.Base.Monoid a => Data.Monoid.Null.MonoidNull (GHC.Internal.Maybe.Maybe a)
instance (GHC.Classes.Ord a, GHC.Internal.Enum.Bounded a) => Data.Monoid.Null.MonoidNull (Data.Semigroup.Min a)
instance Data.Monoid.Null.MonoidNull GHC.Types.Ordering
instance Data.Monoid.Null.MonoidNull p => Data.Monoid.Null.MonoidNull (GHC.Internal.Generics.Par1 p)
instance (Data.Monoid.Null.MonoidNull (f a), Data.Monoid.Null.MonoidNull (g a)) => Data.Monoid.Null.MonoidNull (Data.Functor.Product.Product f g a)
instance (GHC.Internal.Num.Num a, GHC.Classes.Eq a) => Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Semigroup.Internal.Product a)
instance Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Proxy.Proxy a)
instance Data.Monoid.Null.MonoidNull (f p) => Data.Monoid.Null.MonoidNull (GHC.Internal.Generics.Rec1 f p)
instance Data.Monoid.Null.MonoidNull (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Monoid.Null.MonoidNull (Data.Set.Internal.Set a)
instance (GHC.Internal.Num.Num a, GHC.Classes.Eq a) => Data.Monoid.Null.MonoidNull (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Monoid.Null.MonoidNull Data.Text.Internal.Lazy.Text
instance Data.Monoid.Null.MonoidNull Data.Text.Internal.Text
instance (Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b) => Data.Monoid.Null.MonoidNull (a, b)
instance (Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b, Data.Monoid.Null.MonoidNull c) => Data.Monoid.Null.MonoidNull (a, b, c)
instance (Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b, Data.Monoid.Null.MonoidNull c, Data.Monoid.Null.MonoidNull d) => Data.Monoid.Null.MonoidNull (a, b, c, d)
instance (Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b, Data.Monoid.Null.MonoidNull c, Data.Monoid.Null.MonoidNull d, Data.Monoid.Null.MonoidNull e) => Data.Monoid.Null.MonoidNull (a, b, c, d, e)
instance Data.Monoid.Null.MonoidNull (GHC.Internal.Generics.U1 p)
instance Data.Monoid.Null.MonoidNull ()
instance Data.Monoid.Null.MonoidNull (Data.Vector.Vector a)
instance Data.Monoid.Null.MonoidNull a => Data.Monoid.Null.MonoidNull (Data.Semigroup.WrappedMonoid a)
instance Data.Monoid.Null.PositiveMonoid (f (g p)) => Data.Monoid.Null.PositiveMonoid ((GHC.Internal.Generics.:.:) f g p)
instance Data.Monoid.Null.PositiveMonoid GHC.Internal.Data.Semigroup.Internal.All
instance Data.Monoid.Null.PositiveMonoid GHC.Internal.Data.Semigroup.Internal.Any
instance Data.Monoid.Null.PositiveMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.Null.PositiveMonoid Data.ByteString.Internal.Type.ByteString
instance Data.Monoid.Null.PositiveMonoid (f (g a)) => Data.Monoid.Null.PositiveMonoid (Data.Functor.Compose.Compose f g a)
instance Data.Monoid.Null.PositiveMonoid r => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Functor.Const.Const r a)
instance Data.Monoid.Null.PositiveMonoid a => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Ord.Down a)
instance Data.Monoid.Null.PositiveMonoid a => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Monoid.First a)
instance Data.Monoid.Null.PositiveMonoid a => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.Null.PositiveMonoid (Data.IntMap.Internal.IntMap v)
instance Data.Monoid.Null.PositiveMonoid Data.IntSet.Internal.IntSet
instance Data.Monoid.Null.PositiveMonoid c => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Generics.K1 i c p)
instance Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Monoid.Last a)
instance Data.Monoid.Null.PositiveMonoid [x]
instance Data.Monoid.Null.PositiveMonoid (f p) => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Generics.M1 i c f p)
instance GHC.Classes.Ord k => Data.Monoid.Null.PositiveMonoid (Data.Map.Internal.Map k v)
instance (GHC.Classes.Ord a, GHC.Internal.Enum.Bounded a) => Data.Monoid.Null.PositiveMonoid (Data.Semigroup.Max a)
instance GHC.Internal.Base.Monoid a => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Maybe.Maybe a)
instance (GHC.Classes.Ord a, GHC.Internal.Enum.Bounded a) => Data.Monoid.Null.PositiveMonoid (Data.Semigroup.Min a)
instance Data.Monoid.Null.PositiveMonoid GHC.Types.Ordering
instance Data.Monoid.Null.PositiveMonoid p => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Generics.Par1 p)
instance Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Proxy.Proxy a)
instance Data.Monoid.Null.PositiveMonoid (f p) => Data.Monoid.Null.PositiveMonoid (GHC.Internal.Generics.Rec1 f p)
instance Data.Monoid.Null.PositiveMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Monoid.Null.PositiveMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.Null.PositiveMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.Null.PositiveMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.Null.PositiveMonoid Data.Text.Internal.Text
instance Data.Monoid.Null.PositiveMonoid (GHC.Internal.Generics.U1 p)
instance Data.Monoid.Null.PositiveMonoid ()
instance Data.Monoid.Null.PositiveMonoid (Data.Vector.Vector a)
instance Data.Monoid.Null.PositiveMonoid a => Data.Monoid.Null.PositiveMonoid (Data.Semigroup.WrappedMonoid a)


-- | This module defines the <a>Semigroup</a> =&gt; <a>Reductive</a> =&gt;
--   <a>Cancellative</a> class hierarchy.
--   
--   The <a>Reductive</a> class introduces operation <a>&lt;/&gt;</a> which
--   is the inverse of <a>&lt;&gt;</a>. For the <a>Sum</a> semigroup, this
--   operation is subtraction; for <a>Product</a> it is division and for
--   <tt>Set</tt> it's the set difference. A <a>Reductive</a> semigroup is
--   not a full group because <a>&lt;/&gt;</a> may return <a>Nothing</a>.
--   
--   The <a>Cancellative</a> subclass does not add any operation but it
--   provides the additional guarantee that <a>&lt;&gt;</a> can always be
--   undone with <a>&lt;/&gt;</a>. Thus <a>Sum</a> is <a>Cancellative</a>
--   but <a>Product</a> is not because <tt>(0*n)/0</tt> is not defined.
--   
--   All semigroup subclasses listed above are for Abelian, <i>i.e.</i>,
--   commutative or symmetric semigroups. Since most practical semigroups
--   in Haskell are not Abelian, each of the these classes has two
--   symmetric superclasses:
--   
--   <ul>
--   <li><a>LeftReductive</a></li>
--   <li><a>LeftCancellative</a></li>
--   <li><a>RightReductive</a></li>
--   <li><a>RightCancellative</a></li>
--   </ul>
module Data.Semigroup.Cancellative

-- | A <a>Commutative</a> semigroup is a <a>Semigroup</a> that follows the
--   rule:
--   
--   <pre>
--   a &lt;&gt; b == b &lt;&gt; a
--   </pre>
class Semigroup g => Commutative g

-- | Class of Abelian semigroups with a partial inverse for the Semigroup
--   <a>&lt;&gt;</a> operation. The inverse operation <a>&lt;/&gt;</a> must
--   satisfy the following laws:
--   
--   <pre>
--   maybe a (b &lt;&gt;) (a &lt;/&gt; b) == a
--   maybe a (&lt;&gt; b) (a &lt;/&gt; b) == a
--   </pre>
--   
--   The <a>&lt;/&gt;</a> operator is a synonym for both <a>stripPrefix</a>
--   and <a>stripSuffix</a>, which must be equivalent as <a>&lt;&gt;</a> is
--   both associative and commutative.
--   
--   <pre>
--   (&lt;/&gt;) = flip stripPrefix
--   (&lt;/&gt;) = flip stripSuffix
--   </pre>
class (Commutative m, LeftReductive m, RightReductive m) => Reductive m
(</>) :: Reductive m => m -> m -> Maybe m
infix 5 </>

-- | Subclass of <a>Reductive</a> where <a>&lt;/&gt;</a> is a complete
--   inverse of the Semigroup <a>&lt;&gt;</a> operation. The class
--   instances must satisfy the following additional laws:
--   
--   <pre>
--   (a &lt;&gt; b) &lt;/&gt; a == Just b
--   (a &lt;&gt; b) &lt;/&gt; b == Just a
--   </pre>
class (LeftCancellative m, RightCancellative m, Reductive m) => Cancellative m

-- | Helper class to avoid <tt>FlexibleInstances</tt>
class Num a => SumCancellative a
cancelAddition :: SumCancellative a => a -> a -> Maybe a

-- | Class of semigroups with a left inverse of <a>&lt;&gt;</a>, satisfying
--   the following law:
--   
--   <pre>
--   isPrefixOf a b == isJust (stripPrefix a b)
--   maybe b (a &lt;&gt;) (stripPrefix a b) == b
--   a `isPrefixOf` (a &lt;&gt; b)
--   </pre>
--   
--   Every instance definition has to implement at least the
--   <a>stripPrefix</a> method.
class Semigroup m => LeftReductive m
isPrefixOf :: LeftReductive m => m -> m -> Bool
stripPrefix :: LeftReductive m => m -> m -> Maybe m

-- | Class of semigroups with a right inverse of <a>&lt;&gt;</a>,
--   satisfying the following law:
--   
--   <pre>
--   isSuffixOf a b == isJust (stripSuffix a b)
--   maybe b (&lt;&gt; a) (stripSuffix a b) == b
--   b `isSuffixOf` (a &lt;&gt; b)
--   </pre>
--   
--   Every instance definition has to implement at least the
--   <a>stripSuffix</a> method.
class Semigroup m => RightReductive m
isSuffixOf :: RightReductive m => m -> m -> Bool
stripSuffix :: RightReductive m => m -> m -> Maybe m

-- | Subclass of <a>LeftReductive</a> where <a>stripPrefix</a> is a
--   complete inverse of <a>&lt;&gt;</a>, satisfying the following
--   additional law:
--   
--   <pre>
--   stripPrefix a (a &lt;&gt; b) == Just b
--   </pre>
class LeftReductive m => LeftCancellative m

-- | Subclass of <a>LeftReductive</a> where <a>stripPrefix</a> is a
--   complete inverse of <a>&lt;&gt;</a>, satisfying the following
--   additional law:
--   
--   <pre>
--   stripSuffix b (a &lt;&gt; b) == Just a
--   </pre>
class RightReductive m => RightCancellative m
instance Data.Semigroup.Cancellative.Cancellative a => Data.Semigroup.Cancellative.Cancellative (GHC.Internal.Data.Functor.Const.Const a x)
instance Data.Semigroup.Cancellative.Cancellative a => Data.Semigroup.Cancellative.Cancellative (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Cancellative.Cancellative a => Data.Semigroup.Cancellative.Cancellative (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.Cancellative (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance (Data.Semigroup.Cancellative.Cancellative a, Data.Semigroup.Cancellative.Cancellative b) => Data.Semigroup.Cancellative.Cancellative (a, b)
instance (Data.Semigroup.Cancellative.Cancellative a, Data.Semigroup.Cancellative.Cancellative b, Data.Semigroup.Cancellative.Cancellative c) => Data.Semigroup.Cancellative.Cancellative (a, b, c)
instance (Data.Semigroup.Cancellative.Cancellative a, Data.Semigroup.Cancellative.Cancellative b, Data.Semigroup.Cancellative.Cancellative c, Data.Semigroup.Cancellative.Cancellative d) => Data.Semigroup.Cancellative.Cancellative (a, b, c, d)
instance Data.Semigroup.Cancellative.Cancellative ()
instance Data.Semigroup.Cancellative.LeftCancellative Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Cancellative.LeftCancellative Data.ByteString.Internal.Type.ByteString
instance Data.Semigroup.Cancellative.LeftCancellative a => Data.Semigroup.Cancellative.LeftCancellative (GHC.Internal.Data.Functor.Const.Const a x)
instance Data.Semigroup.Cancellative.RightCancellative a => Data.Semigroup.Cancellative.LeftCancellative (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Cancellative.LeftCancellative a => Data.Semigroup.Cancellative.LeftCancellative (GHC.Internal.Data.Functor.Identity.Identity a)
instance GHC.Classes.Eq x => Data.Semigroup.Cancellative.LeftCancellative [x]
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftCancellative (Data.Sequence.Internal.Seq a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.LeftCancellative (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.LeftCancellative Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Cancellative.LeftCancellative Data.Text.Internal.Text
instance (Data.Semigroup.Cancellative.LeftCancellative a, Data.Semigroup.Cancellative.LeftCancellative b) => Data.Semigroup.Cancellative.LeftCancellative (a, b)
instance (Data.Semigroup.Cancellative.LeftCancellative a, Data.Semigroup.Cancellative.LeftCancellative b, Data.Semigroup.Cancellative.LeftCancellative c) => Data.Semigroup.Cancellative.LeftCancellative (a, b, c)
instance (Data.Semigroup.Cancellative.LeftCancellative a, Data.Semigroup.Cancellative.LeftCancellative b, Data.Semigroup.Cancellative.LeftCancellative c, Data.Semigroup.Cancellative.LeftCancellative d) => Data.Semigroup.Cancellative.LeftCancellative (a, b, c, d)
instance Data.Semigroup.Cancellative.LeftCancellative ()
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftCancellative (Data.Vector.Vector a)
instance Data.Semigroup.Cancellative.LeftReductive GHC.Internal.Data.Semigroup.Internal.All
instance Data.Semigroup.Cancellative.LeftReductive GHC.Internal.Data.Semigroup.Internal.Any
instance Data.Semigroup.Cancellative.LeftReductive Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Cancellative.LeftReductive Data.ByteString.Internal.Type.ByteString
instance Data.Semigroup.Cancellative.LeftReductive a => Data.Semigroup.Cancellative.LeftReductive (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Semigroup.Cancellative.RightReductive a => Data.Semigroup.Cancellative.LeftReductive (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Cancellative.LeftReductive a => Data.Semigroup.Cancellative.LeftReductive (GHC.Internal.Data.Functor.Identity.Identity a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftReductive (Data.IntMap.Internal.IntMap a)
instance Data.Semigroup.Cancellative.LeftReductive Data.IntSet.Internal.IntSet
instance GHC.Classes.Eq x => Data.Semigroup.Cancellative.LeftReductive [x]
instance (GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Semigroup.Cancellative.LeftReductive (Data.Map.Internal.Map k a)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.LeftReductive (Data.Semigroup.Max a)
instance Data.Semigroup.Cancellative.LeftReductive x => Data.Semigroup.Cancellative.LeftReductive (GHC.Internal.Maybe.Maybe x)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.LeftReductive (Data.Semigroup.Min a)
instance (Numeric.Product.Commutative.CommutativeProduct a, GHC.Internal.Real.Integral a) => Data.Semigroup.Cancellative.LeftReductive (GHC.Internal.Data.Semigroup.Internal.Product a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftReductive (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.LeftReductive (Data.Set.Internal.Set a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.LeftReductive (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.LeftReductive Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Cancellative.LeftReductive Data.Text.Internal.Text
instance (Data.Semigroup.Cancellative.LeftReductive a, Data.Semigroup.Cancellative.LeftReductive b) => Data.Semigroup.Cancellative.LeftReductive (a, b)
instance (Data.Semigroup.Cancellative.LeftReductive a, Data.Semigroup.Cancellative.LeftReductive b, Data.Semigroup.Cancellative.LeftReductive c) => Data.Semigroup.Cancellative.LeftReductive (a, b, c)
instance (Data.Semigroup.Cancellative.LeftReductive a, Data.Semigroup.Cancellative.LeftReductive b, Data.Semigroup.Cancellative.LeftReductive c, Data.Semigroup.Cancellative.LeftReductive d) => Data.Semigroup.Cancellative.LeftReductive (a, b, c, d)
instance Data.Semigroup.Cancellative.LeftReductive ()
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftReductive (Data.Vector.Vector a)
instance Data.Semigroup.Cancellative.Reductive GHC.Internal.Data.Semigroup.Internal.All
instance Data.Semigroup.Cancellative.Reductive GHC.Internal.Data.Semigroup.Internal.Any
instance Data.Semigroup.Cancellative.Reductive a => Data.Semigroup.Cancellative.Reductive (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Semigroup.Cancellative.Reductive a => Data.Semigroup.Cancellative.Reductive (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Cancellative.Reductive a => Data.Semigroup.Cancellative.Reductive (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Semigroup.Cancellative.Reductive Data.IntSet.Internal.IntSet
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.Reductive (Data.Semigroup.Max a)
instance Data.Semigroup.Cancellative.Reductive x => Data.Semigroup.Cancellative.Reductive (GHC.Internal.Maybe.Maybe x)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.Reductive (Data.Semigroup.Min a)
instance (Numeric.Product.Commutative.CommutativeProduct a, GHC.Internal.Real.Integral a) => Data.Semigroup.Cancellative.Reductive (GHC.Internal.Data.Semigroup.Internal.Product a)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.Reductive (Data.Set.Internal.Set a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.Reductive (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance (Data.Semigroup.Cancellative.Reductive a, Data.Semigroup.Cancellative.Reductive b) => Data.Semigroup.Cancellative.Reductive (a, b)
instance (Data.Semigroup.Cancellative.Reductive a, Data.Semigroup.Cancellative.Reductive b, Data.Semigroup.Cancellative.Reductive c) => Data.Semigroup.Cancellative.Reductive (a, b, c)
instance (Data.Semigroup.Cancellative.Reductive a, Data.Semigroup.Cancellative.Reductive b, Data.Semigroup.Cancellative.Reductive c, Data.Semigroup.Cancellative.Reductive d) => Data.Semigroup.Cancellative.Reductive (a, b, c, d)
instance Data.Semigroup.Cancellative.Reductive ()
instance Data.Semigroup.Cancellative.RightCancellative Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Cancellative.RightCancellative Data.ByteString.Internal.Type.ByteString
instance Data.Semigroup.Cancellative.RightCancellative a => Data.Semigroup.Cancellative.RightCancellative (GHC.Internal.Data.Functor.Const.Const a x)
instance Data.Semigroup.Cancellative.LeftCancellative a => Data.Semigroup.Cancellative.RightCancellative (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Cancellative.RightCancellative a => Data.Semigroup.Cancellative.RightCancellative (GHC.Internal.Data.Functor.Identity.Identity a)
instance GHC.Classes.Eq x => Data.Semigroup.Cancellative.RightCancellative [x]
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightCancellative (Data.Sequence.Internal.Seq a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.RightCancellative (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.RightCancellative Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Cancellative.RightCancellative Data.Text.Internal.Text
instance (Data.Semigroup.Cancellative.RightCancellative a, Data.Semigroup.Cancellative.RightCancellative b) => Data.Semigroup.Cancellative.RightCancellative (a, b)
instance (Data.Semigroup.Cancellative.RightCancellative a, Data.Semigroup.Cancellative.RightCancellative b, Data.Semigroup.Cancellative.RightCancellative c) => Data.Semigroup.Cancellative.RightCancellative (a, b, c)
instance (Data.Semigroup.Cancellative.RightCancellative a, Data.Semigroup.Cancellative.RightCancellative b, Data.Semigroup.Cancellative.RightCancellative c, Data.Semigroup.Cancellative.RightCancellative d) => Data.Semigroup.Cancellative.RightCancellative (a, b, c, d)
instance Data.Semigroup.Cancellative.RightCancellative ()
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightCancellative (Data.Vector.Vector a)
instance Data.Semigroup.Cancellative.RightReductive GHC.Internal.Data.Semigroup.Internal.All
instance Data.Semigroup.Cancellative.RightReductive GHC.Internal.Data.Semigroup.Internal.Any
instance Data.Semigroup.Cancellative.RightReductive Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Cancellative.RightReductive Data.ByteString.Internal.Type.ByteString
instance Data.Semigroup.Cancellative.RightReductive a => Data.Semigroup.Cancellative.RightReductive (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Semigroup.Cancellative.LeftReductive a => Data.Semigroup.Cancellative.RightReductive (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Cancellative.RightReductive a => Data.Semigroup.Cancellative.RightReductive (GHC.Internal.Data.Functor.Identity.Identity a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightReductive (Data.IntMap.Internal.IntMap a)
instance Data.Semigroup.Cancellative.RightReductive Data.IntSet.Internal.IntSet
instance GHC.Classes.Eq x => Data.Semigroup.Cancellative.RightReductive [x]
instance (GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Semigroup.Cancellative.RightReductive (Data.Map.Internal.Map k a)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.RightReductive (Data.Semigroup.Max a)
instance Data.Semigroup.Cancellative.RightReductive x => Data.Semigroup.Cancellative.RightReductive (GHC.Internal.Maybe.Maybe x)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.RightReductive (Data.Semigroup.Min a)
instance (Numeric.Product.Commutative.CommutativeProduct a, GHC.Internal.Real.Integral a) => Data.Semigroup.Cancellative.RightReductive (GHC.Internal.Data.Semigroup.Internal.Product a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightReductive (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.RightReductive (Data.Set.Internal.Set a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.RightReductive (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.RightReductive Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Cancellative.RightReductive Data.Text.Internal.Text
instance (Data.Semigroup.Cancellative.RightReductive a, Data.Semigroup.Cancellative.RightReductive b) => Data.Semigroup.Cancellative.RightReductive (a, b)
instance (Data.Semigroup.Cancellative.RightReductive a, Data.Semigroup.Cancellative.RightReductive b, Data.Semigroup.Cancellative.RightReductive c) => Data.Semigroup.Cancellative.RightReductive (a, b, c)
instance (Data.Semigroup.Cancellative.RightReductive a, Data.Semigroup.Cancellative.RightReductive b, Data.Semigroup.Cancellative.RightReductive c, Data.Semigroup.Cancellative.RightReductive d) => Data.Semigroup.Cancellative.RightReductive (a, b, c, d)
instance Data.Semigroup.Cancellative.RightReductive ()
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightReductive (Data.Vector.Vector a)
instance Data.Semigroup.Cancellative.SumCancellative GHC.Types.Int
instance Data.Semigroup.Cancellative.SumCancellative GHC.Num.Integer.Integer
instance Data.Semigroup.Cancellative.SumCancellative GHC.Num.Natural.Natural
instance Data.Semigroup.Cancellative.SumCancellative GHC.Internal.Real.Rational


-- | This module defines the <a>OverlappingGCDMonoid</a> =&gt; <a>Monus</a>
--   subclass of the <a>Monoid</a> class.
module Data.Monoid.Monus

-- | Class of Abelian monoids with monus.
--   
--   The monus operation <a>&lt;\&gt;</a> is a synonym for both
--   <a>stripPrefixOverlap</a> and <a>stripSuffixOverlap</a>, which must be
--   equivalent as <a>&lt;&gt;</a> is both associative and commutative:
--   
--   <pre>
--   (&lt;\&gt;) = flip stripPrefixOverlap
--   (&lt;\&gt;) = flip stripSuffixOverlap
--   </pre>
--   
--   In addition, the monus operation <a>&lt;\&gt;</a> must satisfy the
--   following laws:
--   
--   <pre>
--   a <a>&lt;\&gt;</a> a <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <pre>
--   <a>mempty</a> <a>&lt;\&gt;</a> a <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <pre>
--   a <a>&lt;&gt;</a> (b <a>&lt;\&gt;</a> a) <a>==</a> b <a>&lt;&gt;</a> (a <a>&lt;\&gt;</a> b)
--   </pre>
--   
--   <pre>
--   (a <a>&lt;\&gt;</a> b) <a>&lt;\&gt;</a> c <a>==</a> a <a>&lt;\&gt;</a> (b <a>&lt;&gt;</a> c)
--   </pre>
class (Commutative m, Monoid m, OverlappingGCDMonoid m) => Monus m
(<\>) :: Monus m => m -> m -> m
infix 5 <\>

-- | Class of monoids for which the greatest overlap can be found between
--   any two values, such that
--   
--   <pre>
--   a == a' &lt;&gt; overlap a b
--   b == overlap a b &lt;&gt; b'
--   </pre>
--   
--   The methods must satisfy the following laws:
--   
--   <pre>
--   stripOverlap a b == (stripSuffixOverlap b a, overlap a b, stripPrefixOverlap a b)
--   stripSuffixOverlap b a &lt;&gt; overlap a b == a
--   overlap a b &lt;&gt; stripPrefixOverlap a b == b
--   </pre>
--   
--   The result of <tt>overlap a b</tt> must be the largest prefix of
--   <tt>b</tt> and suffix of <tt>a</tt>, in the sense that it contains any
--   other value <tt>x</tt> that satifies the property <tt>(x
--   <a>isPrefixOf</a> b) &amp;&amp; (x <a>isSuffixOf</a> a)</tt>:
--   
--   <pre>
--   ∀x. (x `isPrefixOf` b &amp;&amp; x `isSuffixOf` a) =&gt; (x `isPrefixOf` overlap a b &amp;&amp; x `isSuffixOf` overlap a b)
--   </pre>
--   
--   and it must be unique so there's no other value <tt>y</tt> that
--   satisfies the same properties for every such <tt>x</tt>:
--   
--   <pre>
--   ∀y. ((∀x. (x `isPrefixOf` b &amp;&amp; x `isSuffixOf` a) =&gt; x `isPrefixOf` y &amp;&amp; x `isSuffixOf` y) =&gt; y == overlap a b)
--   </pre>
--   
--   In addition, the <a>overlap</a> operation must satisfy the following
--   properties:
--   
--   <b><i>Idempotence</i></b>
--   
--   <pre>
--   <a>overlap</a> a a <a>==</a> a
--   </pre>
--   
--   <b><i>Identity</i></b>
--   
--   <pre>
--   <a>overlap</a> <a>mempty</a> a <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <pre>
--   <a>overlap</a> a <a>mempty</a> <a>==</a> <a>mempty</a>
--   </pre>
class (Monoid m, LeftReductive m, RightReductive m) => OverlappingGCDMonoid m
stripPrefixOverlap :: OverlappingGCDMonoid m => m -> m -> m
stripSuffixOverlap :: OverlappingGCDMonoid m => m -> m -> m
overlap :: OverlappingGCDMonoid m => m -> m -> m
stripOverlap :: OverlappingGCDMonoid m => m -> m -> (m, m, m)
instance Data.Monoid.Monus.Monus a => Data.Monoid.Monus.Monus (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.Monus.Monus a => Data.Monoid.Monus.Monus (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.Monus.Monus a => Data.Monoid.Monus.Monus (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.Monus.Monus Data.IntSet.Internal.IntSet
instance (Data.Monoid.Monus.Monus a, Data.Monoid.Null.MonoidNull a) => Data.Monoid.Monus.Monus (GHC.Internal.Maybe.Maybe a)
instance Data.Monoid.Monus.Monus (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Ord a => Data.Monoid.Monus.Monus (Data.Set.Internal.Set a)
instance Data.Monoid.Monus.Monus (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance (Data.Monoid.Monus.Monus a, Data.Monoid.Monus.Monus b) => Data.Monoid.Monus.Monus (a, b)
instance (Data.Monoid.Monus.Monus a, Data.Monoid.Monus.Monus b, Data.Monoid.Monus.Monus c) => Data.Monoid.Monus.Monus (a, b, c)
instance (Data.Monoid.Monus.Monus a, Data.Monoid.Monus.Monus b, Data.Monoid.Monus.Monus c, Data.Monoid.Monus.Monus d) => Data.Monoid.Monus.Monus (a, b, c, d)
instance Data.Monoid.Monus.Monus ()
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.ByteString.Internal.Type.ByteString
instance Data.Monoid.Monus.OverlappingGCDMonoid a => Data.Monoid.Monus.OverlappingGCDMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.Monus.OverlappingGCDMonoid a => Data.Monoid.Monus.OverlappingGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.Monus.OverlappingGCDMonoid a => Data.Monoid.Monus.OverlappingGCDMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance GHC.Classes.Eq a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.IntMap.Internal.IntMap a)
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.IntSet.Internal.IntSet
instance GHC.Classes.Eq a => Data.Monoid.Monus.OverlappingGCDMonoid [a]
instance (GHC.Classes.Ord k, GHC.Classes.Eq v) => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Map.Internal.Map k v)
instance (Data.Monoid.Monus.OverlappingGCDMonoid a, Data.Monoid.Null.MonoidNull a) => Data.Monoid.Monus.OverlappingGCDMonoid (GHC.Internal.Maybe.Maybe a)
instance Data.Monoid.Monus.OverlappingGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Eq a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.Monus.OverlappingGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.Text.Internal.Text
instance (Data.Monoid.Monus.OverlappingGCDMonoid a, Data.Monoid.Monus.OverlappingGCDMonoid b) => Data.Monoid.Monus.OverlappingGCDMonoid (a, b)
instance (Data.Monoid.Monus.OverlappingGCDMonoid a, Data.Monoid.Monus.OverlappingGCDMonoid b, Data.Monoid.Monus.OverlappingGCDMonoid c) => Data.Monoid.Monus.OverlappingGCDMonoid (a, b, c)
instance (Data.Monoid.Monus.OverlappingGCDMonoid a, Data.Monoid.Monus.OverlappingGCDMonoid b, Data.Monoid.Monus.OverlappingGCDMonoid c, Data.Monoid.Monus.OverlappingGCDMonoid d) => Data.Monoid.Monus.OverlappingGCDMonoid (a, b, c, d)
instance Data.Monoid.Monus.OverlappingGCDMonoid ()
instance GHC.Classes.Eq a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Vector.Vector a)


-- | This module defines the <a>GCDMonoid</a> subclass of the <a>Monoid</a>
--   class.
--   
--   The <a>GCDMonoid</a> subclass adds the <a>gcd</a> operation which
--   takes two monoidal arguments and finds their greatest common divisor,
--   or (more generally) the greatest monoid that can be extracted with the
--   <a>&lt;/&gt;</a> operation from both.
--   
--   The <a>GCDMonoid</a> class is for Abelian, <i>i.e.</i>,
--   <a>Commutative</a> monoids.
--   
--   <h2>Non-commutative GCD monoids</h2>
--   
--   Since most practical monoids in Haskell are not Abelian, the
--   <a>GCDMonoid</a> class has three symmetric superclasses:
--   
--   <ul>
--   <li><a>LeftGCDMonoid</a>Class of monoids for which it is possible to
--   find the greatest common <i>prefix</i> of two monoidal values.</li>
--   <li><a>RightGCDMonoid</a>Class of monoids for which it is possible to
--   find the greatest common <i>suffix</i> of two monoidal values.</li>
--   <li><a>OverlappingGCDMonoid</a>Class of monoids for which it is
--   possible to find the greatest common <i>overlap</i> of two monoidal
--   values.</li>
--   </ul>
--   
--   <h2>Distributive GCD monoids</h2>
--   
--   Since some (but not all) GCD monoids are also distributive, there are
--   three subclasses that add distributivity:
--   
--   <ul>
--   <li><a>DistributiveGCDMonoid</a>Subclass of <a>GCDMonoid</a> with
--   <i>symmetric</i> distributivity.</li>
--   <li><a>LeftDistributiveGCDMonoid</a>Subclass of <a>LeftGCDMonoid</a>
--   with <i>left</i>-distributivity.</li>
--   <li><a>RightDistributiveGCDMonoid</a>Subclass of <a>RightGCDMonoid</a>
--   with <i>right</i>-distributivity.</li>
--   </ul>
module Data.Monoid.GCD

-- | Class of Abelian monoids that allow the greatest common divisor to be
--   found for any two given values. The operations must satisfy the
--   following laws:
--   
--   <pre>
--   gcd a b == commonPrefix a b == commonSuffix a b
--   Just a' = a &lt;/&gt; p &amp;&amp; Just b' = b &lt;/&gt; p
--      where p = gcd a b
--   </pre>
--   
--   In addition, the <a>gcd</a> operation must satisfy the following
--   properties:
--   
--   <b><i>Uniqueness</i></b>
--   
--   <pre>
--   <a>all</a> <a>isJust</a>
--       [ a <a>&lt;/&gt;</a> c
--       , b <a>&lt;/&gt;</a> c
--       , c <a>&lt;/&gt;</a> <a>gcd</a> a b
--       ]
--   ==&gt;
--       (c <a>==</a> <a>gcd</a> a b)
--   </pre>
--   
--   <b><i>Idempotence</i></b>
--   
--   <pre>
--   <a>gcd</a> a a <a>==</a> a
--   </pre>
--   
--   <b><i>Identity</i></b>
--   
--   <pre>
--   <a>gcd</a> <a>mempty</a> a <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <pre>
--   <a>gcd</a> a <a>mempty</a> <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <b><i>Commutativity</i></b>
--   
--   <pre>
--   <a>gcd</a> a b <a>==</a> <a>gcd</a> b a
--   </pre>
--   
--   <b><i>Associativity</i></b>
--   
--   <pre>
--   <a>gcd</a> (<a>gcd</a> a b) c <a>==</a> <a>gcd</a> a (<a>gcd</a> b c)
--   </pre>
class (Monoid m, Commutative m, Reductive m, LeftGCDMonoid m, RightGCDMonoid m, OverlappingGCDMonoid m) => GCDMonoid m
gcd :: GCDMonoid m => m -> m -> m

-- | Class of monoids capable of finding the equivalent of greatest common
--   divisor on the left side of two monoidal values. The following laws
--   must be respected:
--   
--   <pre>
--   stripCommonPrefix a b == (p, a', b')
--      where p = commonPrefix a b
--            Just a' = stripPrefix p a
--            Just b' = stripPrefix p b
--   p == commonPrefix a b &amp;&amp; p &lt;&gt; a' == a &amp;&amp; p &lt;&gt; b' == b
--      where (p, a', b') = stripCommonPrefix a b
--   </pre>
--   
--   Furthermore, <a>commonPrefix</a> must return the unique greatest
--   common prefix that contains, as its prefix, any other prefix
--   <tt>x</tt> of both values:
--   
--   <pre>
--   not (x `isPrefixOf` a &amp;&amp; x `isPrefixOf` b) || x `isPrefixOf` commonPrefix a b
--   </pre>
--   
--   and it cannot itself be a suffix of any other common prefix <tt>y</tt>
--   of both values:
--   
--   <pre>
--   not (y `isPrefixOf` a &amp;&amp; y `isPrefixOf` b &amp;&amp; commonPrefix a b `isSuffixOf` y)
--   </pre>
--   
--   In addition, the <a>commonPrefix</a> operation must satisfy the
--   following properties:
--   
--   <b><i>Idempotence</i></b>
--   
--   <pre>
--   <a>commonPrefix</a> a a <a>==</a> a
--   </pre>
--   
--   <b><i>Identity</i></b>
--   
--   <pre>
--   <a>commonPrefix</a> <a>mempty</a> a <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <pre>
--   <a>commonPrefix</a> a <a>mempty</a> <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <b><i>Commutativity</i></b>
--   
--   <pre>
--   <a>commonPrefix</a> a b <a>==</a> <a>commonPrefix</a> b a
--   </pre>
--   
--   <b><i>Associativity</i></b>
--   
--   <pre>
--   <a>commonPrefix</a> (<a>commonPrefix</a> a b) c
--   <a>==</a>
--   <a>commonPrefix</a> a (<a>commonPrefix</a> b c)
--   </pre>
class (Monoid m, LeftReductive m) => LeftGCDMonoid m
commonPrefix :: LeftGCDMonoid m => m -> m -> m
stripCommonPrefix :: LeftGCDMonoid m => m -> m -> (m, m, m)

-- | Class of monoids capable of finding the equivalent of greatest common
--   divisor on the right side of two monoidal values. The following laws
--   must be respected:
--   
--   <pre>
--   stripCommonSuffix a b == (a', b', s)
--      where s = commonSuffix a b
--            Just a' = stripSuffix p a
--            Just b' = stripSuffix p b
--   s == commonSuffix a b &amp;&amp; a' &lt;&gt; s == a &amp;&amp; b' &lt;&gt; s == b
--      where (a', b', s) = stripCommonSuffix a b
--   </pre>
--   
--   Furthermore, <a>commonSuffix</a> must return the unique greatest
--   common suffix that contains, as its suffix, any other suffix
--   <tt>x</tt> of both values:
--   
--   <pre>
--   not (x `isSuffixOf` a &amp;&amp; x `isSuffixOf` b) || x `isSuffixOf` commonSuffix a b
--   </pre>
--   
--   and it cannot itself be a prefix of any other common suffix <tt>y</tt>
--   of both values:
--   
--   <pre>
--   not (y `isSuffixOf` a &amp;&amp; y `isSuffixOf` b &amp;&amp; commonSuffix a b `isPrefixOf` y)
--   </pre>
--   
--   In addition, the <a>commonSuffix</a> operation must satisfy the
--   following properties:
--   
--   <b><i>Idempotence</i></b>
--   
--   <pre>
--   <a>commonSuffix</a> a a <a>==</a> a
--   </pre>
--   
--   <b><i>Identity</i></b>
--   
--   <pre>
--   <a>commonSuffix</a> <a>mempty</a> a <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <pre>
--   <a>commonSuffix</a> a <a>mempty</a> <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <b><i>Commutativity</i></b>
--   
--   <pre>
--   <a>commonSuffix</a> a b <a>==</a> <a>commonSuffix</a> b a
--   </pre>
--   
--   <b><i>Associativity</i></b>
--   
--   <pre>
--   <a>commonSuffix</a> (<a>commonSuffix</a> a b) c
--   <a>==</a>
--   <a>commonSuffix</a> a (<a>commonSuffix</a> b c)
--   </pre>
class (Monoid m, RightReductive m) => RightGCDMonoid m
commonSuffix :: RightGCDMonoid m => m -> m -> m
stripCommonSuffix :: RightGCDMonoid m => m -> m -> (m, m, m)

-- | Class of monoids for which the greatest overlap can be found between
--   any two values, such that
--   
--   <pre>
--   a == a' &lt;&gt; overlap a b
--   b == overlap a b &lt;&gt; b'
--   </pre>
--   
--   The methods must satisfy the following laws:
--   
--   <pre>
--   stripOverlap a b == (stripSuffixOverlap b a, overlap a b, stripPrefixOverlap a b)
--   stripSuffixOverlap b a &lt;&gt; overlap a b == a
--   overlap a b &lt;&gt; stripPrefixOverlap a b == b
--   </pre>
--   
--   The result of <tt>overlap a b</tt> must be the largest prefix of
--   <tt>b</tt> and suffix of <tt>a</tt>, in the sense that it contains any
--   other value <tt>x</tt> that satifies the property <tt>(x
--   <a>isPrefixOf</a> b) &amp;&amp; (x <a>isSuffixOf</a> a)</tt>:
--   
--   <pre>
--   ∀x. (x `isPrefixOf` b &amp;&amp; x `isSuffixOf` a) =&gt; (x `isPrefixOf` overlap a b &amp;&amp; x `isSuffixOf` overlap a b)
--   </pre>
--   
--   and it must be unique so there's no other value <tt>y</tt> that
--   satisfies the same properties for every such <tt>x</tt>:
--   
--   <pre>
--   ∀y. ((∀x. (x `isPrefixOf` b &amp;&amp; x `isSuffixOf` a) =&gt; x `isPrefixOf` y &amp;&amp; x `isSuffixOf` y) =&gt; y == overlap a b)
--   </pre>
--   
--   In addition, the <a>overlap</a> operation must satisfy the following
--   properties:
--   
--   <b><i>Idempotence</i></b>
--   
--   <pre>
--   <a>overlap</a> a a <a>==</a> a
--   </pre>
--   
--   <b><i>Identity</i></b>
--   
--   <pre>
--   <a>overlap</a> <a>mempty</a> a <a>==</a> <a>mempty</a>
--   </pre>
--   
--   <pre>
--   <a>overlap</a> a <a>mempty</a> <a>==</a> <a>mempty</a>
--   </pre>
class (Monoid m, LeftReductive m, RightReductive m) => OverlappingGCDMonoid m
stripPrefixOverlap :: OverlappingGCDMonoid m => m -> m -> m
stripSuffixOverlap :: OverlappingGCDMonoid m => m -> m -> m
overlap :: OverlappingGCDMonoid m => m -> m -> m
stripOverlap :: OverlappingGCDMonoid m => m -> m -> (m, m, m)

-- | Class of <i>commutative</i> GCD monoids with <i>symmetric</i>
--   distributivity.
--   
--   In addition to the general <a>GCDMonoid</a> laws, instances of this
--   class must also satisfy the following laws:
--   
--   <pre>
--   <a>gcd</a> (a <a>&lt;&gt;</a> b) (a <a>&lt;&gt;</a> c) <a>==</a> a <a>&lt;&gt;</a> <a>gcd</a> b c
--   </pre>
--   
--   <pre>
--   <a>gcd</a> (a <a>&lt;&gt;</a> c) (b <a>&lt;&gt;</a> c) <a>==</a> <a>gcd</a> a b <a>&lt;&gt;</a> c
--   </pre>
class (LeftDistributiveGCDMonoid m, RightDistributiveGCDMonoid m, GCDMonoid m) => DistributiveGCDMonoid m

-- | Class of <i>left</i> GCD monoids with <i>left</i>-distributivity.
--   
--   In addition to the general <a>LeftGCDMonoid</a> laws, instances of
--   this class must also satisfy the following law:
--   
--   <pre>
--   <a>commonPrefix</a> (a <a>&lt;&gt;</a> b) (a <a>&lt;&gt;</a> c) <a>==</a> a <a>&lt;&gt;</a> <a>commonPrefix</a> b c
--   </pre>
class LeftGCDMonoid m => LeftDistributiveGCDMonoid m

-- | Class of <i>right</i> GCD monoids with <i>right</i>-distributivity.
--   
--   In addition to the general <a>RightGCDMonoid</a> laws, instances of
--   this class must also satisfy the following law:
--   
--   <pre>
--   <a>commonSuffix</a> (a <a>&lt;&gt;</a> c) (b <a>&lt;&gt;</a> c) <a>==</a> <a>commonSuffix</a> a b <a>&lt;&gt;</a> c
--   </pre>
class RightGCDMonoid m => RightDistributiveGCDMonoid m
instance Data.Monoid.GCD.DistributiveGCDMonoid a => Data.Monoid.GCD.DistributiveGCDMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.GCD.DistributiveGCDMonoid a => Data.Monoid.GCD.DistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.GCD.DistributiveGCDMonoid a => Data.Monoid.GCD.DistributiveGCDMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.GCD.DistributiveGCDMonoid Data.IntSet.Internal.IntSet
instance Data.Monoid.GCD.DistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Ord a => Data.Monoid.GCD.DistributiveGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.DistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.DistributiveGCDMonoid ()
instance Data.Monoid.GCD.GCDMonoid a => Data.Monoid.GCD.GCDMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.GCD.GCDMonoid a => Data.Monoid.GCD.GCDMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.GCD.GCDMonoid a => Data.Monoid.GCD.GCDMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.GCD.GCDMonoid Data.IntSet.Internal.IntSet
instance Data.Monoid.GCD.GCDMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Ord a => Data.Monoid.GCD.GCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.GCDMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance (Data.Monoid.GCD.GCDMonoid a, Data.Monoid.GCD.GCDMonoid b) => Data.Monoid.GCD.GCDMonoid (a, b)
instance (Data.Monoid.GCD.GCDMonoid a, Data.Monoid.GCD.GCDMonoid b, Data.Monoid.GCD.GCDMonoid c) => Data.Monoid.GCD.GCDMonoid (a, b, c)
instance (Data.Monoid.GCD.GCDMonoid a, Data.Monoid.GCD.GCDMonoid b, Data.Monoid.GCD.GCDMonoid c, Data.Monoid.GCD.GCDMonoid d) => Data.Monoid.GCD.GCDMonoid (a, b, c, d)
instance Data.Monoid.GCD.GCDMonoid ()
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid Data.ByteString.Internal.Type.ByteString
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid a => Data.Monoid.GCD.LeftDistributiveGCDMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.GCD.RightDistributiveGCDMonoid a => Data.Monoid.GCD.LeftDistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid a => Data.Monoid.GCD.LeftDistributiveGCDMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid Data.IntSet.Internal.IntSet
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftDistributiveGCDMonoid [a]
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftDistributiveGCDMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Monoid.GCD.LeftDistributiveGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid Data.Text.Internal.Text
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid ()
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftDistributiveGCDMonoid (Data.Vector.Vector a)
instance Data.Monoid.GCD.LeftGCDMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.GCD.LeftGCDMonoid Data.ByteString.Internal.Type.ByteString
instance Data.Monoid.GCD.LeftGCDMonoid a => Data.Monoid.GCD.LeftGCDMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.GCD.RightGCDMonoid a => Data.Monoid.GCD.LeftGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.GCD.LeftGCDMonoid a => Data.Monoid.GCD.LeftGCDMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftGCDMonoid (Data.IntMap.Internal.IntMap a)
instance Data.Monoid.GCD.LeftGCDMonoid Data.IntSet.Internal.IntSet
instance GHC.Classes.Eq x => Data.Monoid.GCD.LeftGCDMonoid [x]
instance (GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Monoid.GCD.LeftGCDMonoid (Data.Map.Internal.Map k a)
instance Data.Monoid.GCD.LeftGCDMonoid x => Data.Monoid.GCD.LeftGCDMonoid (GHC.Internal.Maybe.Maybe x)
instance Data.Monoid.GCD.LeftGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftGCDMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Monoid.GCD.LeftGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.LeftGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.LeftGCDMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.GCD.LeftGCDMonoid Data.Text.Internal.Text
instance (Data.Monoid.GCD.LeftGCDMonoid a, Data.Monoid.GCD.LeftGCDMonoid b) => Data.Monoid.GCD.LeftGCDMonoid (a, b)
instance (Data.Monoid.GCD.LeftGCDMonoid a, Data.Monoid.GCD.LeftGCDMonoid b, Data.Monoid.GCD.LeftGCDMonoid c) => Data.Monoid.GCD.LeftGCDMonoid (a, b, c)
instance (Data.Monoid.GCD.LeftGCDMonoid a, Data.Monoid.GCD.LeftGCDMonoid b, Data.Monoid.GCD.LeftGCDMonoid c, Data.Monoid.GCD.LeftGCDMonoid d) => Data.Monoid.GCD.LeftGCDMonoid (a, b, c, d)
instance Data.Monoid.GCD.LeftGCDMonoid ()
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftGCDMonoid (Data.Vector.Vector a)
instance Data.Monoid.GCD.RightDistributiveGCDMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.GCD.RightDistributiveGCDMonoid Data.ByteString.Internal.Type.ByteString
instance Data.Monoid.GCD.RightDistributiveGCDMonoid a => Data.Monoid.GCD.RightDistributiveGCDMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.GCD.LeftDistributiveGCDMonoid a => Data.Monoid.GCD.RightDistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.GCD.RightDistributiveGCDMonoid a => Data.Monoid.GCD.RightDistributiveGCDMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.GCD.RightDistributiveGCDMonoid Data.IntSet.Internal.IntSet
instance GHC.Classes.Eq a => Data.Monoid.GCD.RightDistributiveGCDMonoid [a]
instance Data.Monoid.GCD.RightDistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Eq a => Data.Monoid.GCD.RightDistributiveGCDMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Monoid.GCD.RightDistributiveGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.RightDistributiveGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.RightDistributiveGCDMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.GCD.RightDistributiveGCDMonoid Data.Text.Internal.Text
instance Data.Monoid.GCD.RightDistributiveGCDMonoid ()
instance GHC.Classes.Eq a => Data.Monoid.GCD.RightDistributiveGCDMonoid (Data.Vector.Vector a)
instance Data.Monoid.GCD.RightGCDMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.GCD.RightGCDMonoid Data.ByteString.Internal.Type.ByteString
instance Data.Monoid.GCD.RightGCDMonoid a => Data.Monoid.GCD.RightGCDMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.GCD.LeftGCDMonoid a => Data.Monoid.GCD.RightGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.GCD.RightGCDMonoid a => Data.Monoid.GCD.RightGCDMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.GCD.RightGCDMonoid Data.IntSet.Internal.IntSet
instance GHC.Classes.Eq x => Data.Monoid.GCD.RightGCDMonoid [x]
instance Data.Monoid.GCD.RightGCDMonoid x => Data.Monoid.GCD.RightGCDMonoid (GHC.Internal.Maybe.Maybe x)
instance Data.Monoid.GCD.RightGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Eq a => Data.Monoid.GCD.RightGCDMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Monoid.GCD.RightGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.RightGCDMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.RightGCDMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.GCD.RightGCDMonoid Data.Text.Internal.Text
instance (Data.Monoid.GCD.RightGCDMonoid a, Data.Monoid.GCD.RightGCDMonoid b) => Data.Monoid.GCD.RightGCDMonoid (a, b)
instance (Data.Monoid.GCD.RightGCDMonoid a, Data.Monoid.GCD.RightGCDMonoid b, Data.Monoid.GCD.RightGCDMonoid c) => Data.Monoid.GCD.RightGCDMonoid (a, b, c)
instance (Data.Monoid.GCD.RightGCDMonoid a, Data.Monoid.GCD.RightGCDMonoid b, Data.Monoid.GCD.RightGCDMonoid c, Data.Monoid.GCD.RightGCDMonoid d) => Data.Monoid.GCD.RightGCDMonoid (a, b, c, d)
instance Data.Monoid.GCD.RightGCDMonoid ()
instance GHC.Classes.Eq a => Data.Monoid.GCD.RightGCDMonoid (Data.Vector.Vector a)


-- | This module defines the <a>LCMMonoid</a> subclass of the <a>Monoid</a>
--   class.
--   
--   The <a>LCMMonoid</a> subclass adds the <a>lcm</a> operation, which
--   takes two monoidal arguments and finds their <i>least common
--   multiple</i>, or (more generally) the least monoid from which either
--   argument can be subtracted with the <a>&lt;/&gt;</a> operation.
--   
--   For LCM monoids that are distributive, this module also provides the
--   <a>DistributiveLCMMonoid</a> subclass of <a>LCMMonoid</a>.
--   
--   All classes in this module are for Abelian, <i>i.e.</i>,
--   <a>Commutative</a> monoids.
module Data.Monoid.LCM

-- | Class of Abelian monoids that allow the <i>least common multiple</i>
--   to be found for any two given values.
--   
--   Operations must satisfy the following laws:
--   
--   <b><i>Reductivity</i></b>
--   
--   <pre>
--   <a>isJust</a> (<a>lcm</a> a b <a>&lt;/&gt;</a> a)
--   </pre>
--   
--   <pre>
--   <a>isJust</a> (<a>lcm</a> a b <a>&lt;/&gt;</a> b)
--   </pre>
--   
--   <b><i>Uniqueness</i></b>
--   
--   <pre>
--   <a>all</a> <a>isJust</a>
--       [       c <a>&lt;/&gt;</a> a
--       ,       c <a>&lt;/&gt;</a> b
--       , <a>lcm</a> a b <a>&lt;/&gt;</a> c
--       ]
--   ==&gt;
--       (<a>lcm</a> a b <a>==</a> c)
--   </pre>
--   
--   <b><i>Idempotence</i></b>
--   
--   <pre>
--   <a>lcm</a> a a <a>==</a> a
--   </pre>
--   
--   <b><i>Identity</i></b>
--   
--   <pre>
--   <a>lcm</a> <a>mempty</a> a <a>==</a> a
--   </pre>
--   
--   <pre>
--   <a>lcm</a> a <a>mempty</a> <a>==</a> a
--   </pre>
--   
--   <b><i>Commutativity</i></b>
--   
--   <pre>
--   <a>lcm</a> a b <a>==</a> <a>lcm</a> b a
--   </pre>
--   
--   <b><i>Associativity</i></b>
--   
--   <pre>
--   <a>lcm</a> (<a>lcm</a> a b) c <a>==</a> <a>lcm</a> a (<a>lcm</a> b c)
--   </pre>
--   
--   <b><i>Absorption</i></b>
--   
--   <pre>
--   <a>lcm</a> a (<a>gcd</a> a b) <a>==</a> a
--   </pre>
--   
--   <pre>
--   <a>gcd</a> a (<a>lcm</a> a b) <a>==</a> a
--   </pre>
class GCDMonoid m => LCMMonoid m
lcm :: LCMMonoid m => m -> m -> m

-- | Class of <i>commutative</i> LCM monoids with <i>distributivity</i>.
--   
--   In addition to the general <a>LCMMonoid</a> laws, instances of this
--   class must also satisfy the following laws:
--   
--   The <a>lcm</a> operation itself must be <i>both</i> left-distributive
--   <i>and</i> right-distributive:
--   
--   <pre>
--   <a>lcm</a> (a <a>&lt;&gt;</a> b) (a <a>&lt;&gt;</a> c) <a>==</a> a <a>&lt;&gt;</a> <a>lcm</a> b c
--   </pre>
--   
--   <pre>
--   <a>lcm</a> (a <a>&lt;&gt;</a> c) (b <a>&lt;&gt;</a> c) <a>==</a> <a>lcm</a> a b <a>&lt;&gt;</a> c
--   </pre>
--   
--   The <a>lcm</a> and <a>gcd</a> operations must distribute over one
--   another:
--   
--   <pre>
--   <a>lcm</a> a (<a>gcd</a> b c) <a>==</a> <a>gcd</a> (<a>lcm</a> a b) (<a>lcm</a> a c)
--   </pre>
--   
--   <pre>
--   <a>gcd</a> a (<a>lcm</a> b c) <a>==</a> <a>lcm</a> (<a>gcd</a> a b) (<a>gcd</a> a c)
--   </pre>
class (DistributiveGCDMonoid m, LCMMonoid m) => DistributiveLCMMonoid m
instance Data.Monoid.LCM.DistributiveLCMMonoid a => Data.Monoid.LCM.DistributiveLCMMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.LCM.DistributiveLCMMonoid a => Data.Monoid.LCM.DistributiveLCMMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.LCM.DistributiveLCMMonoid a => Data.Monoid.LCM.DistributiveLCMMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.LCM.DistributiveLCMMonoid Data.IntSet.Internal.IntSet
instance Data.Monoid.LCM.DistributiveLCMMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Ord a => Data.Monoid.LCM.DistributiveLCMMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.LCM.DistributiveLCMMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.LCM.DistributiveLCMMonoid ()
instance Data.Monoid.LCM.LCMMonoid a => Data.Monoid.LCM.LCMMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.LCM.LCMMonoid a => Data.Monoid.LCM.LCMMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.LCM.LCMMonoid a => Data.Monoid.LCM.LCMMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.LCM.LCMMonoid Data.IntSet.Internal.IntSet
instance Data.Monoid.LCM.LCMMonoid (GHC.Internal.Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance GHC.Classes.Ord a => Data.Monoid.LCM.LCMMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.LCM.LCMMonoid (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance (Data.Monoid.LCM.LCMMonoid a, Data.Monoid.LCM.LCMMonoid b) => Data.Monoid.LCM.LCMMonoid (a, b)
instance (Data.Monoid.LCM.LCMMonoid a, Data.Monoid.LCM.LCMMonoid b, Data.Monoid.LCM.LCMMonoid c) => Data.Monoid.LCM.LCMMonoid (a, b, c)
instance (Data.Monoid.LCM.LCMMonoid a, Data.Monoid.LCM.LCMMonoid b, Data.Monoid.LCM.LCMMonoid c, Data.Monoid.LCM.LCMMonoid d) => Data.Monoid.LCM.LCMMonoid (a, b, c, d)
instance Data.Monoid.LCM.LCMMonoid ()


-- | This module defines the <a>Monoid</a> =&gt; <a>CommutativeMonoid</a>
--   =&gt; <a>ReductiveMonoid</a> =&gt; <a>CancellativeMonoid</a>
--   constraint synonym hierarchy.
--   
--   Since most practical monoids in Haskell are not commutative, the last
--   two of these synonyms have two symmetric superclasses each:
--   
--   <ul>
--   <li><a>LeftReductiveMonoid</a></li>
--   <li><a>LeftCancellativeMonoid</a></li>
--   <li><a>RightReductiveMonoid</a></li>
--   <li><a>RightCancellativeMonoid</a></li>
--   </ul>
--   
--   This module and its constraint synonyms are provided for compatibility
--   with the older versions of the <tt>monoid-sublasses</tt> library.
--   Starting with version 1.0, the classes from the
--   <a>Data.Semigroup.Cancellative</a> module are recommended instead.
module Data.Monoid.Cancellative
type CommutativeMonoid m = (Monoid m, Commutative m)
type ReductiveMonoid m = (Monoid m, Reductive m)
type CancellativeMonoid m = (Monoid m, Cancellative m)
type LeftReductiveMonoid m = (Monoid m, LeftReductive m)
type RightReductiveMonoid m = (Monoid m, RightReductive m)
type LeftCancellativeMonoid m = (Monoid m, LeftCancellative m)
type RightCancellativeMonoid m = (Monoid m, RightCancellative m)


-- | This module defines the <a>Semigroup</a> =&gt; <a>Factorial</a> =&gt;
--   <a>StableFactorial</a> classes and some of their instances.
module Data.Semigroup.Factorial

-- | Class of semigroups that can be split into irreducible (<i>i.e.</i>,
--   atomic or prime) <a>factors</a> in a unique way. Factors of a
--   <a>Product</a> are literally its prime factors:
--   
--   <pre>
--   factors (Product 12) == [Product 2, Product 2, Product 3]
--   </pre>
--   
--   Factors of a list are <i>not</i> its elements but all its single-item
--   sublists:
--   
--   <pre>
--   factors "abc" == ["a", "b", "c"]
--   </pre>
--   
--   The methods of this class satisfy the following laws:
--   
--   <pre>
--   maybe id sconcat  . nonEmpty . factors == id
--   List.all (\prime-&gt; factors prime == [prime]) . factors
--   primePrefix s == foldr const s s
--   foldl f a == List.foldl f a . factors
--   foldl' f a == List.foldl' f a . factors
--   foldr f a == List.foldr f a . factors
--   </pre>
--   
--   A minimal instance definition must implement <a>factors</a> or
--   <a>foldr</a>. Other methods can and should be implemented only for
--   performance reasons.
class Semigroup m => Factorial m

-- | Returns a list of all prime factors; inverse of mconcat.
factors :: Factorial m => m -> [m]

-- | The prime prefix; <tt>primePrefix mempty == mempty</tt> for monoids.
primePrefix :: Factorial m => m -> m

-- | The prime suffix; <tt>primeSuffix mempty == mempty</tt> for monoids.
primeSuffix :: Factorial m => m -> m

-- | Like <a>foldl</a> from <a>Data.List</a> on the list of prime
--   <a>factors</a>.
foldl :: Factorial m => (a -> m -> a) -> a -> m -> a

-- | Like <a>foldl'</a> from <a>Data.List</a> on the list of prime
--   <a>factors</a>.
foldl' :: Factorial m => (a -> m -> a) -> a -> m -> a

-- | Like <a>foldr</a> from <a>Data.List</a> on the list of prime
--   <a>factors</a>.
foldr :: Factorial m => (m -> a -> a) -> a -> m -> a

-- | The <a>length</a> of the list of prime <a>factors</a>.
length :: Factorial m => m -> Int

-- | Generalizes <a>foldMap</a> from <a>Data.Foldable</a>, except the
--   function arguments are prime <a>factors</a> rather than the structure
--   elements.
foldMap :: (Factorial m, Monoid n) => (m -> n) -> m -> n

-- | Equivalent to <a>reverse</a> from <a>Data.List</a>.
reverse :: Factorial m => m -> m

-- | A subclass of <a>Factorial</a> whose instances satisfy the following
--   additional laws:
--   
--   <pre>
--   factors (a &lt;&gt; b) == factors a &lt;&gt; factors b
--   factors . reverse == List.reverse . factors
--   primeSuffix s == primePrefix (reverse s)
--   </pre>
class Factorial m => StableFactorial m

-- | A <a>mapM</a> equivalent.
mapM :: (Factorial a, Semigroup b, Monoid b, Monad m) => (a -> m b) -> a -> m b

-- | A <a>mapM_</a> equivalent.
mapM_ :: (Factorial a, Applicative m) => (a -> m b) -> a -> m ()
instance Data.Semigroup.Factorial.Factorial Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Factorial.Factorial Data.ByteString.Internal.Type.ByteString
instance Data.Semigroup.Factorial.Factorial a => Data.Semigroup.Factorial.Factorial (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Semigroup.Factorial.Factorial a => Data.Semigroup.Factorial.Factorial (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Factorial.Factorial a => Data.Semigroup.Factorial.Factorial (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Semigroup.Factorial.Factorial (Data.IntMap.Internal.IntMap a)
instance Data.Semigroup.Factorial.Factorial Data.IntSet.Internal.IntSet
instance Data.Semigroup.Factorial.Factorial [x]
instance GHC.Classes.Ord k => Data.Semigroup.Factorial.Factorial (Data.Map.Internal.Map k v)
instance Data.Semigroup.Factorial.Factorial a => Data.Semigroup.Factorial.Factorial (GHC.Internal.Maybe.Maybe a)
instance GHC.Internal.Real.Integral a => Data.Semigroup.Factorial.Factorial (GHC.Internal.Data.Semigroup.Internal.Product a)
instance Data.Semigroup.Factorial.Factorial (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Semigroup.Factorial.Factorial (Data.Set.Internal.Set a)
instance (GHC.Internal.Real.Integral a, GHC.Classes.Eq a) => Data.Semigroup.Factorial.Factorial (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Factorial.Factorial Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Factorial.Factorial Data.Text.Internal.Text
instance (Data.Semigroup.Factorial.Factorial a, Data.Semigroup.Factorial.Factorial b, Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b) => Data.Semigroup.Factorial.Factorial (a, b)
instance (Data.Semigroup.Factorial.Factorial a, Data.Semigroup.Factorial.Factorial b, Data.Semigroup.Factorial.Factorial c, Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b, Data.Monoid.Null.MonoidNull c) => Data.Semigroup.Factorial.Factorial (a, b, c)
instance (Data.Semigroup.Factorial.Factorial a, Data.Semigroup.Factorial.Factorial b, Data.Semigroup.Factorial.Factorial c, Data.Semigroup.Factorial.Factorial d, Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b, Data.Monoid.Null.MonoidNull c, Data.Monoid.Null.MonoidNull d) => Data.Semigroup.Factorial.Factorial (a, b, c, d)
instance Data.Semigroup.Factorial.Factorial ()
instance Data.Semigroup.Factorial.Factorial (Data.Vector.Vector a)
instance Data.Semigroup.Factorial.StableFactorial Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Factorial.StableFactorial Data.ByteString.Internal.Type.ByteString
instance Data.Semigroup.Factorial.StableFactorial a => Data.Semigroup.Factorial.StableFactorial (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Semigroup.Factorial.StableFactorial a => Data.Semigroup.Factorial.StableFactorial (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Factorial.StableFactorial a => Data.Semigroup.Factorial.StableFactorial (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Semigroup.Factorial.StableFactorial [x]
instance Data.Semigroup.Factorial.StableFactorial (Data.Sequence.Internal.Seq a)
instance Data.Semigroup.Factorial.StableFactorial (GHC.Internal.Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Semigroup.Factorial.StableFactorial Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Factorial.StableFactorial Data.Text.Internal.Text
instance Data.Semigroup.Factorial.StableFactorial ()
instance Data.Semigroup.Factorial.StableFactorial (Data.Vector.Vector a)


-- | This module defines the <a>FactorialMonoid</a> class and some of its
--   instances.
module Data.Monoid.Factorial

-- | Class of monoids that can be split into irreducible (<i>i.e.</i>,
--   atomic or prime) <a>factors</a> in a unique way. Note that
--   <a>mempty</a> is not considered a factor. Factors of a <a>Product</a>
--   are literally its prime factors:
--   
--   <pre>
--   factors (Product 12) == [Product 2, Product 2, Product 3]
--   </pre>
--   
--   Factors of a list are <i>not</i> its elements but all its single-item
--   sublists:
--   
--   <pre>
--   factors "abc" == ["a", "b", "c"]
--   </pre>
--   
--   The methods of this class satisfy the following laws in addition to
--   those of <a>Factorial</a>:
--   
--   <pre>
--   null == List.null . factors
--   factors == unfoldr splitPrimePrefix == List.reverse . unfoldr (fmap swap . splitPrimeSuffix)
--   reverse == mconcat . List.reverse . factors
--   primePrefix == maybe mempty fst . splitPrimePrefix
--   primeSuffix == maybe mempty snd . splitPrimeSuffix
--   inits == List.map mconcat . List.inits . factors
--   tails == List.map mconcat . List.tails . factors
--   span p m == (mconcat l, mconcat r) where (l, r) = List.span p (factors m)
--   List.all (List.all (not . pred) . factors) . split pred
--   mconcat . intersperse prime . split (== prime) == id
--   splitAt i m == (mconcat l, mconcat r) where (l, r) = List.splitAt i (factors m)
--   spanMaybe () (const $ bool Nothing (Maybe ()) . p) m == (takeWhile p m, dropWhile p m, ())
--   spanMaybe s0 (\s m-&gt; Just $ f s m) m0 == (m0, mempty, foldl f s0 m0)
--   let (prefix, suffix, s') = spanMaybe s f m
--       foldMaybe = foldl g (Just s)
--       g s m = s &gt;&gt;= flip f m
--   in all ((Nothing ==) . foldMaybe) (inits prefix)
--      &amp;&amp; prefix == last (filter (isJust . foldMaybe) $ inits m)
--      &amp;&amp; Just s' == foldMaybe prefix
--      &amp;&amp; m == prefix &lt;&gt; suffix
--   </pre>
--   
--   A minimal instance definition should implement <a>splitPrimePrefix</a>
--   for performance reasons, and other methods where beneficial.
class (Factorial m, MonoidNull m) => FactorialMonoid m

-- | Splits the argument into its prime prefix and the remaining suffix.
--   Returns <a>Nothing</a> for <a>mempty</a>.
splitPrimePrefix :: FactorialMonoid m => m -> Maybe (m, m)

-- | Splits the argument into its prime suffix and the remaining prefix.
--   Returns <a>Nothing</a> for <a>mempty</a>.
splitPrimeSuffix :: FactorialMonoid m => m -> Maybe (m, m)

-- | Returns the list of all prefixes of the argument, <a>mempty</a> first.
inits :: FactorialMonoid m => m -> [m]

-- | Returns the list of all suffixes of the argument, <a>mempty</a> last.
tails :: FactorialMonoid m => m -> [m]

-- | Like <a>span</a> from <a>Data.List</a> on the list of prime
--   <a>factors</a>.
span :: FactorialMonoid m => (m -> Bool) -> m -> (m, m)

-- | Equivalent to <a>break</a> from <a>Data.List</a>.
break :: FactorialMonoid m => (m -> Bool) -> m -> (m, m)

-- | Splits the monoid into components delimited by prime separators
--   satisfying the given predicate. The primes satisfying the predicate
--   are not a part of the result.
split :: FactorialMonoid m => (m -> Bool) -> m -> [m]

-- | Equivalent to <a>takeWhile</a> from <a>Data.List</a>.
takeWhile :: FactorialMonoid m => (m -> Bool) -> m -> m

-- | Equivalent to <a>dropWhile</a> from <a>Data.List</a>.
dropWhile :: FactorialMonoid m => (m -> Bool) -> m -> m

-- | A stateful variant of <a>span</a>, threading the result of the test
--   function as long as it returns <a>Just</a>.
spanMaybe :: FactorialMonoid m => s -> (s -> m -> Maybe s) -> m -> (m, m, s)

-- | Strict version of <a>spanMaybe</a>.
spanMaybe' :: FactorialMonoid m => s -> (s -> m -> Maybe s) -> m -> (m, m, s)

-- | Like <a>splitAt</a> from <a>Data.List</a> on the list of prime
--   <a>factors</a>.
splitAt :: FactorialMonoid m => Int -> m -> (m, m)

-- | Equivalent to <a>drop</a> from <a>Data.List</a>.
drop :: FactorialMonoid m => Int -> m -> m

-- | Equivalent to <a>take</a> from <a>Data.List</a>.
take :: FactorialMonoid m => Int -> m -> m

-- | <i>Deprecated: Use Data.Semigroup.Factorial.StableFactorial
--   instead.</i>
type StableFactorialMonoid m = (StableFactorial m, FactorialMonoid m, PositiveMonoid m)
instance Data.Monoid.Factorial.FactorialMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.Factorial.FactorialMonoid Data.ByteString.Internal.Type.ByteString
instance Data.Monoid.Factorial.FactorialMonoid a => Data.Monoid.Factorial.FactorialMonoid (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Monoid.Factorial.FactorialMonoid a => Data.Monoid.Factorial.FactorialMonoid (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Monoid.Factorial.FactorialMonoid a => Data.Monoid.Factorial.FactorialMonoid (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Monoid.Factorial.FactorialMonoid (Data.IntMap.Internal.IntMap a)
instance Data.Monoid.Factorial.FactorialMonoid Data.IntSet.Internal.IntSet
instance Data.Monoid.Factorial.FactorialMonoid [x]
instance GHC.Classes.Ord k => Data.Monoid.Factorial.FactorialMonoid (Data.Map.Internal.Map k v)
instance Data.Monoid.Factorial.FactorialMonoid a => Data.Monoid.Factorial.FactorialMonoid (GHC.Internal.Maybe.Maybe a)
instance GHC.Internal.Real.Integral a => Data.Monoid.Factorial.FactorialMonoid (GHC.Internal.Data.Semigroup.Internal.Product a)
instance Data.Monoid.Factorial.FactorialMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Ord a => Data.Monoid.Factorial.FactorialMonoid (Data.Set.Internal.Set a)
instance (GHC.Internal.Real.Integral a, GHC.Classes.Eq a) => Data.Monoid.Factorial.FactorialMonoid (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Monoid.Factorial.FactorialMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.Factorial.FactorialMonoid Data.Text.Internal.Text
instance (Data.Monoid.Factorial.FactorialMonoid a, Data.Monoid.Factorial.FactorialMonoid b) => Data.Monoid.Factorial.FactorialMonoid (a, b)
instance (Data.Monoid.Factorial.FactorialMonoid a, Data.Monoid.Factorial.FactorialMonoid b, Data.Monoid.Factorial.FactorialMonoid c) => Data.Monoid.Factorial.FactorialMonoid (a, b, c)
instance (Data.Monoid.Factorial.FactorialMonoid a, Data.Monoid.Factorial.FactorialMonoid b, Data.Monoid.Factorial.FactorialMonoid c, Data.Monoid.Factorial.FactorialMonoid d) => Data.Monoid.Factorial.FactorialMonoid (a, b, c, d)
instance Data.Monoid.Factorial.FactorialMonoid ()
instance Data.Monoid.Factorial.FactorialMonoid (Data.Vector.Vector a)


-- | This module defines the <a>TextualMonoid</a> class and several of its
--   instances.
module Data.Monoid.Textual

-- | The <a>TextualMonoid</a> class is an extension of
--   <a>FactorialMonoid</a> specialized for monoids that can contain
--   characters. Its methods are generally equivalent to their namesake
--   functions from <a>Data.List</a> and <a>Data.Text</a>, and they satisfy
--   the following laws:
--   
--   <pre>
--   unfoldr splitCharacterPrefix . fromString == id
--   splitCharacterPrefix . primePrefix == fmap (\(c, t)-&gt; (c, mempty)) . splitCharacterPrefix
--   
--   map f . fromString == fromString . List.map f
--   concatMap (fromString . f) . fromString == fromString . List.concatMap f
--   
--   foldl  ft fc a . fromString == List.foldl  fc a
--   foldr  ft fc a . fromString == List.foldr  fc a
--   foldl' ft fc a . fromString == List.foldl' fc a
--   
--   scanl f c . fromString == fromString . List.scanl f c
--   scanr f c . fromString == fromString . List.scanr f c
--   mapAccumL f a . fromString == fmap fromString . List.mapAccumL f a
--   mapAccumL f a . fromString == fmap fromString . List.mapAccumL f a
--   
--   takeWhile pt pc . fromString == fromString . takeWhile pc
--   dropWhile pt pc . fromString == fromString . dropWhile pc
--   
--   mconcat . intersperse (singleton c) . split (== c) == id
--   find p . fromString == List.find p
--   elem c . fromString == List.elem c
--   </pre>
--   
--   A <a>TextualMonoid</a> may contain non-character data insterspersed
--   between its characters. Every class method that returns a modified
--   <a>TextualMonoid</a> instance generally preserves this non-character
--   data. Methods like <a>foldr</a> can access both the non-character and
--   character data and expect two arguments for the two purposes. For each
--   of these methods there is also a simplified version with underscore in
--   name (like <a>foldr_</a>) that ignores the non-character data.
--   
--   All of the following expressions are identities:
--   
--   <pre>
--   map id
--   concatMap singleton
--   foldl  (&lt;&gt;) (\a c-&gt; a &lt;&gt; singleton c) mempty
--   foldr  (&lt;&gt;) ((&lt;&gt;) . singleton) mempty
--   foldl' (&lt;&gt;) (\a c-&gt; a &lt;&gt; singleton c) mempty
--   scanl1 (const id)
--   scanr1 const
--   uncurry (mapAccumL (,))
--   uncurry (mapAccumR (,))
--   takeWhile (const True) (const True)
--   dropWhile (const False) (const False)
--   toString undefined . fromString
--   toText undefined . fromText
--   </pre>
class (IsString t, LeftReductive t, LeftGCDMonoid t, FactorialMonoid t) => TextualMonoid t

-- | Contructs a new data type instance Like <a>fromString</a>, but from a
--   <a>Text</a> input instead of <a>String</a>.
--   
--   <pre>
--   fromText == fromString . Text.unpack
--   </pre>
fromText :: TextualMonoid t => Text -> t

-- | Creates a prime monoid containing a single character.
--   
--   <pre>
--   singleton c == fromString [c]
--   </pre>
singleton :: TextualMonoid t => Char -> t

-- | Specialized version of <a>splitPrimePrefix</a>. Every prime factor of
--   a textual monoid must consist of a single character or no character at
--   all.
splitCharacterPrefix :: TextualMonoid t => t -> Maybe (Char, t)

-- | Extracts a single character that prefixes the monoid, if the monoid
--   begins with a character. Otherwise returns <a>Nothing</a>.
--   
--   <pre>
--   characterPrefix == fmap fst . splitCharacterPrefix
--   </pre>
characterPrefix :: TextualMonoid t => t -> Maybe Char

-- | Equivalent to <a>map</a> from <a>Data.List</a> with a <tt>Char -&gt;
--   Char</tt> function. Preserves all non-character data.
--   
--   <pre>
--   map f == concatMap (singleton . f)
--   </pre>
map :: TextualMonoid t => (Char -> Char) -> t -> t

-- | Equivalent to <a>concatMap</a> from <a>Data.List</a> with a <tt>Char
--   -&gt; String</tt> function. Preserves all non-character data.
concatMap :: TextualMonoid t => (Char -> t) -> t -> t

-- | Returns the list of characters the monoid contains, once the argument
--   function converts all its non-character factors into characters.
toString :: TextualMonoid t => (t -> String) -> t -> String

-- | Converts the monoid into <a>Text</a>, given a function to convert the
--   non-character factors into chunks of <a>Text</a>.
toText :: TextualMonoid t => (t -> Text) -> t -> Text

-- | Equivalent to <a>any</a> from <a>Data.List</a>. Ignores all
--   non-character data.
any :: TextualMonoid t => (Char -> Bool) -> t -> Bool

-- | Equivalent to <a>all</a> from <a>Data.List</a>. Ignores all
--   non-character data.
all :: TextualMonoid t => (Char -> Bool) -> t -> Bool

-- | The first argument folds over the non-character prime factors, the
--   second over characters. Otherwise equivalent to <a>foldl</a> from
--   <a>Data.List</a>.
foldl :: TextualMonoid t => (a -> t -> a) -> (a -> Char -> a) -> a -> t -> a

-- | Strict version of <a>foldl</a>.
foldl' :: TextualMonoid t => (a -> t -> a) -> (a -> Char -> a) -> a -> t -> a

-- | The first argument folds over the non-character prime factors, the
--   second over characters. Otherwise equivalent to 'List.foldl'' from
--   <a>Data.List</a>.
foldr :: TextualMonoid t => (t -> a -> a) -> (Char -> a -> a) -> a -> t -> a

-- | Equivalent to <a>scanl</a> from <a>Data.List</a> when applied to a
--   <a>String</a>, but preserves all non-character data.
scanl :: TextualMonoid t => (Char -> Char -> Char) -> Char -> t -> t

-- | Equivalent to <a>scanl1</a> from <a>Data.List</a> when applied to a
--   <a>String</a>, but preserves all non-character data.
--   
--   <pre>
--   scanl f c == scanl1 f . (singleton c &lt;&gt;)
--   </pre>
scanl1 :: TextualMonoid t => (Char -> Char -> Char) -> t -> t

-- | Equivalent to <a>scanr</a> from <a>Data.List</a> when applied to a
--   <a>String</a>, but preserves all non-character data.
scanr :: TextualMonoid t => (Char -> Char -> Char) -> Char -> t -> t

-- | Equivalent to <a>scanr1</a> from <a>Data.List</a> when applied to a
--   <a>String</a>, but preserves all non-character data.
--   
--   <pre>
--   scanr f c == scanr1 f . (&lt;&gt; singleton c)
--   </pre>
scanr1 :: TextualMonoid t => (Char -> Char -> Char) -> t -> t

-- | Equivalent to <a>mapAccumL</a> from <a>Data.List</a> when applied to a
--   <a>String</a>, but preserves all non-character data.
mapAccumL :: TextualMonoid t => (a -> Char -> (a, Char)) -> a -> t -> (a, t)

-- | Equivalent to <a>mapAccumR</a> from <a>Data.List</a> when applied to a
--   <a>String</a>, but preserves all non-character data.
mapAccumR :: TextualMonoid t => (a -> Char -> (a, Char)) -> a -> t -> (a, t)

-- | The first predicate tests the non-character data, the second one the
--   characters. Otherwise equivalent to <a>takeWhile</a> from
--   <a>Data.List</a> when applied to a <a>String</a>.
takeWhile :: TextualMonoid t => (t -> Bool) -> (Char -> Bool) -> t -> t

-- | The first predicate tests the non-character data, the second one the
--   characters. Otherwise equivalent to <a>dropWhile</a> from
--   <a>Data.List</a> when applied to a <a>String</a>.
dropWhile :: TextualMonoid t => (t -> Bool) -> (Char -> Bool) -> t -> t

-- | 'break pt pc' is equivalent to <tt>span (not . pt) (not . pc)</tt>.
break :: TextualMonoid t => (t -> Bool) -> (Char -> Bool) -> t -> (t, t)

-- | 'span pt pc t' is equivalent to <tt>(takeWhile pt pc t, dropWhile pt
--   pc t)</tt>.
span :: TextualMonoid t => (t -> Bool) -> (Char -> Bool) -> t -> (t, t)

-- | A stateful variant of <a>span</a>, threading the result of the test
--   function as long as it returns <a>Just</a>.
spanMaybe :: TextualMonoid t => s -> (s -> t -> Maybe s) -> (s -> Char -> Maybe s) -> t -> (t, t, s)

-- | Strict version of <a>spanMaybe</a>.
spanMaybe' :: TextualMonoid t => s -> (s -> t -> Maybe s) -> (s -> Char -> Maybe s) -> t -> (t, t, s)

-- | Splits the monoid into components delimited by character separators
--   satisfying the given predicate. The characters satisfying the
--   predicate are not a part of the result.
--   
--   <pre>
--   split p == Factorial.split (maybe False p . characterPrefix)
--   </pre>
split :: TextualMonoid t => (Char -> Bool) -> t -> [t]

-- | Like <a>find</a> from <a>Data.List</a> when applied to a
--   <a>String</a>. Ignores non-character data.
find :: TextualMonoid t => (Char -> Bool) -> t -> Maybe Char

-- | Like <a>elem</a> from <a>Data.List</a> when applied to a
--   <a>String</a>. Ignores non-character data.
elem :: TextualMonoid t => Char -> t -> Bool

-- | <pre>
--   foldl_ = foldl const
--   </pre>
foldl_ :: TextualMonoid t => (a -> Char -> a) -> a -> t -> a
foldl_' :: TextualMonoid t => (a -> Char -> a) -> a -> t -> a
foldr_ :: TextualMonoid t => (Char -> a -> a) -> a -> t -> a

-- | <pre>
--   takeWhile_ = takeWhile . const
--   </pre>
takeWhile_ :: TextualMonoid t => Bool -> (Char -> Bool) -> t -> t

-- | <pre>
--   dropWhile_ = dropWhile . const
--   </pre>
dropWhile_ :: TextualMonoid t => Bool -> (Char -> Bool) -> t -> t

-- | <pre>
--   break_ = break . const
--   </pre>
break_ :: TextualMonoid t => Bool -> (Char -> Bool) -> t -> (t, t)

-- | <pre>
--   span_ = span . const
--   </pre>
span_ :: TextualMonoid t => Bool -> (Char -> Bool) -> t -> (t, t)

-- | <pre>
--   spanMaybe_ s = spanMaybe s (const . Just)
--   </pre>
spanMaybe_ :: TextualMonoid t => s -> (s -> Char -> Maybe s) -> t -> (t, t, s)
spanMaybe_' :: TextualMonoid t => s -> (s -> Char -> Maybe s) -> t -> (t, t, s)
instance Data.Monoid.Textual.TextualMonoid GHC.Internal.Base.String
instance Data.Monoid.Textual.TextualMonoid (Data.Sequence.Internal.Seq GHC.Types.Char)
instance Data.Monoid.Textual.TextualMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.Textual.TextualMonoid Data.Text.Internal.Text


-- | This module contains orphan <a>IsString</a> and <a>TextualMonoid</a>
--   instances of <tt>Vector Char</tt>.
module Data.Monoid.Instances.CharVector
instance GHC.Internal.Data.String.IsString (Data.Vector.Vector GHC.Types.Char)
instance Data.Monoid.Textual.TextualMonoid (Data.Vector.Vector GHC.Types.Char)


-- | This module defines the monoid transformer data type <a>Stateful</a>.
--   
--   <pre>
--   &gt; let s = setState [4] $ pure "data" :: Stateful [Int] String
--   &gt; s
--   Stateful ("data",[4])
--   &gt; factors s
--   [Stateful ("d",[]),Stateful ("a",[]),Stateful ("t",[]),Stateful ("a",[]),Stateful ("",[4])]
--   </pre>
module Data.Monoid.Instances.Stateful

-- | <tt><a>Stateful</a> a b</tt> is a wrapper around the <a>Monoid</a>
--   <tt>b</tt> that carries the state <tt>a</tt> along. The state type
--   <tt>a</tt> must be a monoid as well if <a>Stateful</a> is to be of any
--   use. In the <a>FactorialMonoid</a> and <a>TextualMonoid</a> class
--   instances, the monoid <tt>b</tt> has the priority and the state
--   <tt>a</tt> is left for the end.
newtype Stateful a b
Stateful :: (b, a) -> Stateful a b
extract :: Stateful a b -> b
state :: Stateful a b -> a
setState :: a -> Stateful a b -> Stateful a b
instance GHC.Internal.Base.Monoid a => GHC.Internal.Base.Applicative (Data.Monoid.Instances.Stateful.Stateful a)
instance (GHC.Internal.Data.Data.Data a, GHC.Internal.Data.Data.Data b) => GHC.Internal.Data.Data.Data (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Classes.Eq b, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Monoid.Factorial.FactorialMonoid a, Data.Monoid.Factorial.FactorialMonoid b) => Data.Monoid.Factorial.FactorialMonoid (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Monoid.Factorial.FactorialMonoid a, Data.Monoid.Factorial.FactorialMonoid b) => Data.Semigroup.Factorial.Factorial (Data.Monoid.Instances.Stateful.Stateful a b)
instance GHC.Internal.Base.Functor (Data.Monoid.Instances.Stateful.Stateful a)
instance (GHC.Internal.Base.Monoid a, GHC.Internal.Data.String.IsString b) => GHC.Internal.Data.String.IsString (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Monoid.GCD.LeftGCDMonoid a, Data.Monoid.GCD.LeftGCDMonoid b) => Data.Monoid.GCD.LeftGCDMonoid (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Semigroup.Cancellative.LeftReductive a, Data.Semigroup.Cancellative.LeftReductive b) => Data.Semigroup.Cancellative.LeftReductive (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Internal.Base.Semigroup a, GHC.Internal.Base.Semigroup b, Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b) => Data.Monoid.Null.MonoidNull (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Internal.Base.Semigroup a, GHC.Internal.Base.Semigroup b, GHC.Internal.Base.Monoid a, GHC.Internal.Base.Monoid b) => GHC.Internal.Base.Monoid (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Classes.Ord b, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Internal.Base.Semigroup a, GHC.Internal.Base.Semigroup b, Data.Monoid.Null.PositiveMonoid a, Data.Monoid.Null.PositiveMonoid b) => Data.Monoid.Null.PositiveMonoid (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Monoid.GCD.RightGCDMonoid a, Data.Monoid.GCD.RightGCDMonoid b) => Data.Monoid.GCD.RightGCDMonoid (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Semigroup.Cancellative.RightReductive a, Data.Semigroup.Cancellative.RightReductive b) => Data.Semigroup.Cancellative.RightReductive (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Internal.Base.Semigroup a, GHC.Internal.Base.Semigroup b) => GHC.Internal.Base.Semigroup (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Internal.Show.Show b, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Monoid.Factorial.FactorialMonoid a, Data.Monoid.Factorial.FactorialMonoid b, Data.Semigroup.Factorial.StableFactorial a, Data.Semigroup.Factorial.StableFactorial b) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Monoid.GCD.LeftGCDMonoid a, Data.Monoid.Factorial.FactorialMonoid a, Data.Monoid.Textual.TextualMonoid b) => Data.Monoid.Textual.TextualMonoid (Data.Monoid.Instances.Stateful.Stateful a b)


-- | This module defines the monoid transformer data type <a>Shadowed</a>.
module Data.Monoid.Instances.PrefixMemory

-- | Monoid transformer that keeps track of the former <a>prefix</a> of its
--   <a>content</a>. All functions that return a suffix of their argument,
--   such as <a>stripPrefix</a> or <a>commonSuffix</a>, preserve the
--   discarded <a>prefix</a>.
data Shadowed m

-- | The constructor of a <a>Shadowed</a> monoid, with the initial
--   <tt>prefix = null</tt>
shadowed :: Monoid m => m -> Shadowed m

-- | the present value
content :: Shadowed m -> m

-- | used to precede the <a>content</a> but has been consumed
prefix :: Shadowed m -> m
instance GHC.Internal.Data.Data.Data m => GHC.Internal.Data.Data.Data (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance GHC.Classes.Eq m => GHC.Classes.Eq (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m) => Data.Monoid.Factorial.FactorialMonoid (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Monoid.Factorial.FactorialMonoid m, Data.Semigroup.Factorial.StableFactorial m) => Data.Semigroup.Factorial.Factorial (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (GHC.Internal.Base.Monoid m, GHC.Internal.Data.String.IsString m) => GHC.Internal.Data.String.IsString (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (GHC.Classes.Eq m, Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m, Data.Monoid.GCD.LeftGCDMonoid m) => Data.Monoid.GCD.LeftGCDMonoid (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Monoid.Null.MonoidNull m, Data.Semigroup.Factorial.StableFactorial m, Data.Semigroup.Cancellative.LeftReductive m) => Data.Semigroup.Cancellative.LeftReductive (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Monoid.Null.MonoidNull m, Data.Semigroup.Factorial.StableFactorial m) => Data.Monoid.Null.MonoidNull (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Monoid.Null.MonoidNull m, Data.Semigroup.Factorial.StableFactorial m) => GHC.Internal.Base.Monoid (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance GHC.Classes.Ord m => GHC.Classes.Ord (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Monoid.Null.PositiveMonoid m, Data.Semigroup.Factorial.StableFactorial m) => Data.Monoid.Null.PositiveMonoid (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m, Data.Monoid.GCD.RightGCDMonoid m) => Data.Monoid.GCD.RightGCDMonoid (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m, Data.Semigroup.Cancellative.RightReductive m) => Data.Semigroup.Cancellative.RightReductive (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Monoid.Null.MonoidNull m, Data.Semigroup.Factorial.StableFactorial m) => GHC.Internal.Base.Semigroup (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Monoid.Null.MonoidNull m, GHC.Internal.Show.Show m) => GHC.Internal.Show.Show (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.PrefixMemory.Shadowed m)
instance (GHC.Classes.Eq m, Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => Data.Monoid.Textual.TextualMonoid (Data.Monoid.Instances.PrefixMemory.Shadowed m)


-- | This module defines two monoid transformer data types,
--   <a>OffsetPositioned</a> and <a>LinePositioned</a>. Both data types add
--   a notion of the current position to their base monoid. In case of
--   <a>OffsetPositioned</a>, the current position is a simple integer
--   offset from the beginning of the monoid, and it can be applied to any
--   <a>StableFactorial</a>. The base monoid of <a>LinePositioned</a> must
--   be a <a>TextualMonoid</a>, but for the price it will keep track of the
--   current line and column numbers as well.
--   
--   Line number is zero-based, column one-based:
--   
--   <pre>
--   &gt; let p = pure "abcd\nefgh\nijkl\nmnop\n" :: LinePositioned String
--   &gt; p
--   "abcd\nefgh\nijkl\nmnop\n"
--   &gt; Data.Monoid.Factorial.drop 13 p
--   Line 2, column 4: "l\nmnop\n"
--   </pre>
module Data.Monoid.Instances.Positioned
data OffsetPositioned m
data LinePositioned m
extract :: Positioned p => p a -> a
position :: Positioned p => p a -> Int

-- | the current line
line :: LinePositioned m -> Int

-- | the current column
column :: LinePositioned m -> Int
instance GHC.Internal.Base.Applicative Data.Monoid.Instances.Positioned.LinePositioned
instance GHC.Internal.Base.Applicative Data.Monoid.Instances.Positioned.OffsetPositioned
instance GHC.Internal.Data.Data.Data m => GHC.Internal.Data.Data.Data (Data.Monoid.Instances.Positioned.LinePositioned m)
instance GHC.Internal.Data.Data.Data m => GHC.Internal.Data.Data.Data (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance GHC.Classes.Eq m => GHC.Classes.Eq (Data.Monoid.Instances.Positioned.LinePositioned m)
instance GHC.Classes.Eq m => GHC.Classes.Eq (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => Data.Monoid.Factorial.FactorialMonoid (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m) => Data.Monoid.Factorial.FactorialMonoid (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => Data.Semigroup.Factorial.Factorial (Data.Monoid.Instances.Positioned.LinePositioned m)
instance Data.Semigroup.Factorial.StableFactorial m => Data.Semigroup.Factorial.Factorial (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance GHC.Internal.Base.Functor Data.Monoid.Instances.Positioned.LinePositioned
instance GHC.Internal.Base.Functor Data.Monoid.Instances.Positioned.OffsetPositioned
instance GHC.Internal.Data.String.IsString m => GHC.Internal.Data.String.IsString (Data.Monoid.Instances.Positioned.LinePositioned m)
instance GHC.Internal.Data.String.IsString m => GHC.Internal.Data.String.IsString (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m, Data.Monoid.GCD.LeftGCDMonoid m) => Data.Monoid.GCD.LeftGCDMonoid (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m, Data.Monoid.GCD.LeftGCDMonoid m) => Data.Monoid.GCD.LeftGCDMonoid (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => Data.Semigroup.Cancellative.LeftReductive (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Semigroup.Cancellative.LeftReductive m) => Data.Semigroup.Cancellative.LeftReductive (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m, Data.Monoid.Null.MonoidNull m) => Data.Monoid.Null.MonoidNull (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m) => Data.Monoid.Null.MonoidNull (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => GHC.Internal.Base.Monoid (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Monoid.Factorial.FactorialMonoid m, Data.Semigroup.Factorial.StableFactorial m) => GHC.Internal.Base.Monoid (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance GHC.Classes.Ord m => GHC.Classes.Ord (Data.Monoid.Instances.Positioned.LinePositioned m)
instance GHC.Classes.Ord m => GHC.Classes.Ord (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance Data.Monoid.Instances.Positioned.Positioned Data.Monoid.Instances.Positioned.LinePositioned
instance Data.Monoid.Instances.Positioned.Positioned Data.Monoid.Instances.Positioned.OffsetPositioned
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => Data.Monoid.Null.PositiveMonoid (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m) => Data.Monoid.Null.PositiveMonoid (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m, Data.Monoid.GCD.RightGCDMonoid m) => Data.Monoid.GCD.RightGCDMonoid (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m, Data.Monoid.GCD.RightGCDMonoid m) => Data.Monoid.GCD.RightGCDMonoid (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m, Data.Semigroup.Cancellative.RightReductive m) => Data.Semigroup.Cancellative.RightReductive (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Factorial.FactorialMonoid m, Data.Semigroup.Cancellative.RightReductive m) => Data.Semigroup.Cancellative.RightReductive (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => GHC.Internal.Base.Semigroup (Data.Monoid.Instances.Positioned.LinePositioned m)
instance Data.Semigroup.Factorial.StableFactorial m => GHC.Internal.Base.Semigroup (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance GHC.Internal.Show.Show m => GHC.Internal.Show.Show (Data.Monoid.Instances.Positioned.LinePositioned m)
instance GHC.Internal.Show.Show m => GHC.Internal.Show.Show (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Positioned.LinePositioned m)
instance Data.Semigroup.Factorial.StableFactorial m => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => Data.Monoid.Textual.TextualMonoid (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => Data.Monoid.Textual.TextualMonoid (Data.Monoid.Instances.Positioned.OffsetPositioned m)


-- | This module defines the monoid transformer data type <a>Measured</a>.
module Data.Monoid.Instances.Measured

-- | <tt><a>Measured</a> a</tt> is a wrapper around the
--   <a>FactorialMonoid</a> <tt>a</tt> that memoizes the monoid's
--   <a>length</a> so it becomes a constant-time operation. The parameter
--   is restricted to the <a>StableFactorial</a> class, which guarantees
--   that <tt><a>length</a> (a &lt;&gt; b) == <a>length</a> a +
--   <a>length</a> b</tt>.
data Measured a

-- | Create a new <a>Measured</a> value.
measure :: Factorial a => a -> Measured a
extract :: Measured a -> a
instance GHC.Internal.Data.Data.Data a => GHC.Internal.Data.Data.Data (Data.Monoid.Instances.Measured.Measured a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Null.MonoidNull a) => Data.Semigroup.Factorial.Factorial (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Factorial.FactorialMonoid a) => Data.Monoid.Factorial.FactorialMonoid (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Monoid.Factorial.FactorialMonoid a, GHC.Internal.Data.String.IsString a) => GHC.Internal.Data.String.IsString (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Monoid.GCD.LeftGCDMonoid a, Data.Semigroup.Factorial.StableFactorial a) => Data.Monoid.GCD.LeftGCDMonoid (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Cancellative.LeftReductive a, Data.Semigroup.Factorial.StableFactorial a) => Data.Semigroup.Cancellative.LeftReductive (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, GHC.Internal.Base.Monoid a) => GHC.Internal.Base.Monoid (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, GHC.Internal.Base.Monoid a) => Data.Monoid.Null.MonoidNull (Data.Monoid.Instances.Measured.Measured a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, GHC.Internal.Base.Monoid a) => Data.Monoid.Null.PositiveMonoid (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Monoid.GCD.RightGCDMonoid a, Data.Semigroup.Factorial.StableFactorial a) => Data.Monoid.GCD.RightGCDMonoid (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Cancellative.RightReductive a, Data.Semigroup.Factorial.StableFactorial a) => Data.Semigroup.Cancellative.RightReductive (Data.Monoid.Instances.Measured.Measured a)
instance Data.Semigroup.Factorial.StableFactorial a => GHC.Internal.Base.Semigroup (Data.Monoid.Instances.Measured.Measured a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Null.MonoidNull a) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Measured.Measured a)
instance (GHC.Classes.Eq a, Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Textual.TextualMonoid a) => Data.Monoid.Textual.TextualMonoid (Data.Monoid.Instances.Measured.Measured a)


-- | This module defines the monoid transformer data type <a>Concat</a>.
module Data.Monoid.Instances.Concat

-- | <tt><a>Concat</a></tt> is a transparent monoid transformer. The
--   behaviour of the <tt><a>Concat</a> a</tt> instances of monoid
--   subclasses is identical to the behaviour of their <tt>a</tt>
--   instances, up to the <a>pure</a> isomorphism.
--   
--   The only purpose of <a>Concat</a> then is to change the performance
--   characteristics of various operations. Most importantly, injecting a
--   monoid into <a>Concat</a> has the effect of making <a>mappend</a> a
--   constant-time operation. The <a>splitPrimePrefix</a> and
--   <a>splitPrimeSuffix</a> operations are amortized to constant time,
--   provided that only one or the other is used. Using both operations
--   alternately will trigger the worst-case behaviour of O(n).
data Concat a

-- | <i>Deprecated: Concat is not wrapping Seq any more, don't use
--   concatenate nor extract.</i>
concatenate :: PositiveMonoid a => Seq a -> Concat a

-- | <i>Deprecated: Concat is not wrapping Seq any more, don't use
--   concatenate nor extract.</i>
extract :: Concat a -> Seq a
force :: Semigroup a => Concat a -> a
instance GHC.Internal.Base.Applicative Data.Monoid.Instances.Concat.Concat
instance GHC.Internal.Data.Data.Data a => GHC.Internal.Data.Data.Data (Data.Monoid.Instances.Concat.Concat a)
instance (GHC.Classes.Eq a, GHC.Internal.Base.Semigroup a) => GHC.Classes.Eq (Data.Monoid.Instances.Concat.Concat a)
instance (Data.Semigroup.Factorial.Factorial a, Data.Monoid.Null.PositiveMonoid a) => Data.Semigroup.Factorial.Factorial (Data.Monoid.Instances.Concat.Concat a)
instance (Data.Monoid.Factorial.FactorialMonoid a, Data.Monoid.Null.PositiveMonoid a) => Data.Monoid.Factorial.FactorialMonoid (Data.Monoid.Instances.Concat.Concat a)
instance GHC.Internal.Data.Foldable.Foldable Data.Monoid.Instances.Concat.Concat
instance GHC.Internal.Base.Functor Data.Monoid.Instances.Concat.Concat
instance GHC.Internal.Data.String.IsString a => GHC.Internal.Data.String.IsString (Data.Monoid.Instances.Concat.Concat a)
instance (Data.Monoid.GCD.LeftGCDMonoid a, Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Null.PositiveMonoid a) => Data.Monoid.GCD.LeftGCDMonoid (Data.Monoid.Instances.Concat.Concat a)
instance (Data.Semigroup.Cancellative.LeftReductive a, Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Null.PositiveMonoid a) => Data.Semigroup.Cancellative.LeftReductive (Data.Monoid.Instances.Concat.Concat a)
instance Data.Monoid.Null.PositiveMonoid a => GHC.Internal.Base.Monoid (Data.Monoid.Instances.Concat.Concat a)
instance Data.Monoid.Null.PositiveMonoid a => Data.Monoid.Null.MonoidNull (Data.Monoid.Instances.Concat.Concat a)
instance (GHC.Classes.Ord a, GHC.Internal.Base.Semigroup a) => GHC.Classes.Ord (Data.Monoid.Instances.Concat.Concat a)
instance Data.Monoid.Null.PositiveMonoid a => Data.Monoid.Null.PositiveMonoid (Data.Monoid.Instances.Concat.Concat a)
instance (Data.Monoid.GCD.RightGCDMonoid a, Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Null.PositiveMonoid a) => Data.Monoid.GCD.RightGCDMonoid (Data.Monoid.Instances.Concat.Concat a)
instance (Data.Semigroup.Cancellative.RightReductive a, Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Null.PositiveMonoid a) => Data.Semigroup.Cancellative.RightReductive (Data.Monoid.Instances.Concat.Concat a)
instance Data.Monoid.Null.PositiveMonoid a => GHC.Internal.Base.Semigroup (Data.Monoid.Instances.Concat.Concat a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Monoid.Instances.Concat.Concat a)
instance (Data.Semigroup.Factorial.Factorial a, Data.Monoid.Null.PositiveMonoid a) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Concat.Concat a)
instance (GHC.Classes.Eq a, Data.Monoid.Textual.TextualMonoid a, Data.Semigroup.Factorial.StableFactorial a, Data.Monoid.Null.PositiveMonoid a) => Data.Monoid.Textual.TextualMonoid (Data.Monoid.Instances.Concat.Concat a)


-- | This module defines the <a>ByteStringUTF8</a> newtype wrapper around
--   <a>ByteString</a>, together with its <a>TextualMonoid</a> instance.
--   The <a>FactorialMonoid</a> instance of a wrapped <a>ByteStringUTF8</a>
--   value differs from the original <a>ByteString</a>: the prime
--   <a>factors</a> of the original value are its bytes, and for the
--   wrapped value the prime <a>factors</a> are its valid UTF8 byte
--   sequences. The following example session demonstrates the
--   relationship:
--   
--   <pre>
--   &gt; let utf8@(ByteStringUTF8 bs) = fromString "E=mc\xb2"
--   &gt; bs
--   "E=mc\194\178"
--   &gt; factors bs
--   ["E","=","m","c","\194","\178"]
--   &gt; utf8
--   "E=mc²"
--   &gt; factors utf8
--   ["E","=","m","c","²"]
--   </pre>
--   
--   The <a>TextualMonoid</a> instance follows the same logic, but it also
--   decodes all valid UTF8 sequences into characters. Any invalid UTF8
--   byte sequence from the original <a>ByteString</a> is preserved as a
--   single prime factor:
--   
--   <pre>
--   &gt; let utf8'@(ByteStringUTF8 bs') = ByteStringUTF8 (Data.ByteString.map pred bs)
--   &gt; bs'
--   "D&lt;lb\193\177"
--   &gt; factors bs'
--   ["D","&lt;","l","b","\193","\177"]
--   &gt; utf8'
--   "D&lt;lb\[193,177]"
--   &gt; factors utf8'
--   ["D","&lt;","l","b","\[193,177]"]
--   </pre>
module Data.Monoid.Instances.ByteString.UTF8
newtype ByteStringUTF8
ByteStringUTF8 :: ByteString -> ByteStringUTF8

-- | Takes a raw <a>ByteString</a> chunk and returns a pair of
--   <a>ByteStringUTF8</a> decoding the prefix of the chunk and the
--   remaining suffix that is either null or contains the incomplete last
--   character of the chunk.
decode :: ByteString -> (ByteStringUTF8, ByteString)
instance GHC.Internal.Data.Data.Data Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Classes.Eq Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Semigroup.Factorial.Factorial Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Monoid.Factorial.FactorialMonoid Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Internal.Data.String.IsString Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Semigroup.Cancellative.LeftCancellative Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Monoid.GCD.LeftGCDMonoid Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Semigroup.Cancellative.LeftReductive Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Internal.Base.Monoid Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Monoid.Null.MonoidNull Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Classes.Ord Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Monoid.Null.PositiveMonoid Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Internal.Base.Semigroup Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Internal.Show.Show Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Monoid.Textual.TextualMonoid Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
