-- 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


-- | 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

-- | 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.PositiveMonoid ()
instance Data.Monoid.Null.PositiveMonoid GHC.Types.Ordering
instance Data.Monoid.Null.PositiveMonoid Data.Semigroup.Internal.All
instance Data.Monoid.Null.PositiveMonoid Data.Semigroup.Internal.Any
instance Data.Monoid.Null.PositiveMonoid Data.ByteString.Internal.ByteString
instance Data.Monoid.Null.PositiveMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.Null.PositiveMonoid Data.Text.Internal.Text
instance Data.Monoid.Null.PositiveMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.Null.PositiveMonoid (Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance Data.Monoid.Null.PositiveMonoid (Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance GHC.Base.Monoid a => Data.Monoid.Null.PositiveMonoid (GHC.Maybe.Maybe a)
instance Data.Monoid.Null.PositiveMonoid (Data.Monoid.First a)
instance Data.Monoid.Null.PositiveMonoid (Data.Monoid.Last a)
instance Data.Monoid.Null.PositiveMonoid a => Data.Monoid.Null.PositiveMonoid (Data.Semigroup.Internal.Dual a)
instance Data.Monoid.Null.PositiveMonoid [x]
instance GHC.Classes.Ord k => Data.Monoid.Null.PositiveMonoid (Data.Map.Internal.Map k v)
instance Data.Monoid.Null.PositiveMonoid (Data.IntMap.Internal.IntMap v)
instance Data.Monoid.Null.PositiveMonoid Data.IntSet.Internal.IntSet
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 (Data.Vector.Vector a)
instance Data.Monoid.Null.MonoidNull ()
instance Data.Monoid.Null.MonoidNull GHC.Types.Ordering
instance Data.Monoid.Null.MonoidNull Data.Semigroup.Internal.All
instance Data.Monoid.Null.MonoidNull Data.Semigroup.Internal.Any
instance Data.Monoid.Null.MonoidNull (Data.Monoid.First a)
instance Data.Monoid.Null.MonoidNull (Data.Monoid.Last a)
instance Data.Monoid.Null.MonoidNull a => Data.Monoid.Null.MonoidNull (Data.Semigroup.Internal.Dual a)
instance (GHC.Num.Num a, GHC.Classes.Eq a) => Data.Monoid.Null.MonoidNull (Data.Semigroup.Internal.Sum a)
instance (GHC.Num.Num a, GHC.Classes.Eq a) => Data.Monoid.Null.MonoidNull (Data.Semigroup.Internal.Product a)
instance GHC.Base.Monoid a => Data.Monoid.Null.MonoidNull (GHC.Maybe.Maybe a)
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 [x]
instance Data.Monoid.Null.MonoidNull Data.ByteString.Internal.ByteString
instance Data.Monoid.Null.MonoidNull Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.Null.MonoidNull Data.Text.Internal.Text
instance Data.Monoid.Null.MonoidNull Data.Text.Internal.Lazy.Text
instance GHC.Classes.Ord k => Data.Monoid.Null.MonoidNull (Data.Map.Internal.Map k v)
instance Data.Monoid.Null.MonoidNull (Data.IntMap.Internal.IntMap v)
instance Data.Monoid.Null.MonoidNull Data.IntSet.Internal.IntSet
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 Data.Monoid.Null.MonoidNull (Data.Vector.Vector 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

-- | An <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.SumCancellative GHC.Types.Int
instance Data.Semigroup.Cancellative.SumCancellative GHC.Num.Integer.Integer
instance Data.Semigroup.Cancellative.SumCancellative GHC.Real.Rational
instance Data.Semigroup.Cancellative.SumCancellative GHC.Num.Natural.Natural
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.Reductive (Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.LeftReductive (Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.RightReductive (Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.Cancellative (Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.LeftCancellative (Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.SumCancellative a => Data.Semigroup.Cancellative.RightCancellative (Data.Semigroup.Internal.Sum a)
instance Data.Semigroup.Cancellative.Cancellative ()
instance Data.Semigroup.Cancellative.Cancellative a => Data.Semigroup.Cancellative.Cancellative (Data.Semigroup.Internal.Dual 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.RightCancellative ()
instance Data.Semigroup.Cancellative.LeftCancellative a => Data.Semigroup.Cancellative.RightCancellative (Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Cancellative.RightCancellative a => Data.Semigroup.Cancellative.LeftCancellative (Data.Semigroup.Internal.Dual a)
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 GHC.Classes.Eq x => Data.Semigroup.Cancellative.RightCancellative [x]
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightCancellative (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightCancellative (Data.Vector.Vector a)
instance Data.Semigroup.Cancellative.RightCancellative Data.ByteString.Internal.ByteString
instance Data.Semigroup.Cancellative.RightCancellative Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Cancellative.RightCancellative Data.Text.Internal.Text
instance Data.Semigroup.Cancellative.RightCancellative Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Cancellative.LeftCancellative ()
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 GHC.Classes.Eq x => Data.Semigroup.Cancellative.LeftCancellative [x]
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftCancellative (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftCancellative (Data.Vector.Vector a)
instance Data.Semigroup.Cancellative.LeftCancellative Data.ByteString.Internal.ByteString
instance Data.Semigroup.Cancellative.LeftCancellative Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Cancellative.LeftCancellative Data.Text.Internal.Text
instance Data.Semigroup.Cancellative.LeftCancellative Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Cancellative.Reductive ()
instance Data.Semigroup.Cancellative.Reductive a => Data.Semigroup.Cancellative.Reductive (Data.Semigroup.Internal.Dual a)
instance (Numeric.Product.Commutative.CommutativeProduct a, GHC.Real.Integral a) => Data.Semigroup.Cancellative.Reductive (Data.Semigroup.Internal.Product a)
instance (Numeric.Product.Commutative.CommutativeProduct a, GHC.Real.Integral a) => Data.Semigroup.Cancellative.LeftReductive (Data.Semigroup.Internal.Product a)
instance (Numeric.Product.Commutative.CommutativeProduct a, GHC.Real.Integral a) => Data.Semigroup.Cancellative.RightReductive (Data.Semigroup.Internal.Product 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 x => Data.Semigroup.Cancellative.Reductive (GHC.Maybe.Maybe x)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.LeftReductive (Data.Set.Internal.Set a)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.RightReductive (Data.Set.Internal.Set a)
instance GHC.Classes.Ord a => Data.Semigroup.Cancellative.Reductive (Data.Set.Internal.Set a)
instance Data.Semigroup.Cancellative.LeftReductive Data.IntSet.Internal.IntSet
instance Data.Semigroup.Cancellative.RightReductive Data.IntSet.Internal.IntSet
instance Data.Semigroup.Cancellative.Reductive Data.IntSet.Internal.IntSet
instance Data.Semigroup.Cancellative.RightReductive ()
instance Data.Semigroup.Cancellative.LeftReductive a => Data.Semigroup.Cancellative.RightReductive (Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Cancellative.RightReductive a => Data.Semigroup.Cancellative.LeftReductive (Data.Semigroup.Internal.Dual a)
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 x => Data.Semigroup.Cancellative.RightReductive (GHC.Maybe.Maybe x)
instance (GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Semigroup.Cancellative.RightReductive (Data.Map.Internal.Map k a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightReductive (Data.IntMap.Internal.IntMap a)
instance GHC.Classes.Eq x => Data.Semigroup.Cancellative.RightReductive [x]
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightReductive (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.RightReductive (Data.Vector.Vector a)
instance Data.Semigroup.Cancellative.RightReductive Data.ByteString.Internal.ByteString
instance Data.Semigroup.Cancellative.RightReductive Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Cancellative.RightReductive Data.Text.Internal.Text
instance Data.Semigroup.Cancellative.RightReductive Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Cancellative.LeftReductive ()
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 x => Data.Semigroup.Cancellative.LeftReductive (GHC.Maybe.Maybe x)
instance (GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Semigroup.Cancellative.LeftReductive (Data.Map.Internal.Map k a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftReductive (Data.IntMap.Internal.IntMap a)
instance GHC.Classes.Eq x => Data.Semigroup.Cancellative.LeftReductive [x]
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftReductive (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Eq a => Data.Semigroup.Cancellative.LeftReductive (Data.Vector.Vector a)
instance Data.Semigroup.Cancellative.LeftReductive Data.ByteString.Internal.ByteString
instance Data.Semigroup.Cancellative.LeftReductive Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Cancellative.LeftReductive Data.Text.Internal.Text
instance Data.Semigroup.Cancellative.LeftReductive Data.Text.Internal.Lazy.Text


-- | 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>
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>
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 ()
instance Data.Monoid.Monus.Monus a => Data.Monoid.Monus.Monus (Data.Semigroup.Internal.Dual a)
instance Data.Monoid.Monus.Monus (Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.Monus.OverlappingGCDMonoid (Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.Monus.Monus (Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance Data.Monoid.Monus.OverlappingGCDMonoid (Data.Semigroup.Internal.Product 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 a, Data.Monoid.Null.MonoidNull a) => Data.Monoid.Monus.Monus (GHC.Maybe.Maybe a)
instance GHC.Classes.Ord a => Data.Monoid.Monus.Monus (Data.Set.Internal.Set a)
instance GHC.Classes.Ord a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.Monus.Monus Data.IntSet.Internal.IntSet
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.IntSet.Internal.IntSet
instance Data.Monoid.Monus.OverlappingGCDMonoid ()
instance Data.Monoid.Monus.OverlappingGCDMonoid a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Semigroup.Internal.Dual a)
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 a, Data.Monoid.Null.MonoidNull a) => Data.Monoid.Monus.OverlappingGCDMonoid (GHC.Maybe.Maybe a)
instance (GHC.Classes.Ord k, GHC.Classes.Eq v) => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Map.Internal.Map k v)
instance GHC.Classes.Eq a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.IntMap.Internal.IntMap a)
instance GHC.Classes.Eq a => Data.Monoid.Monus.OverlappingGCDMonoid [a]
instance GHC.Classes.Eq a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Eq a => Data.Monoid.Monus.OverlappingGCDMonoid (Data.Vector.Vector a)
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.ByteString.Internal.ByteString
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.Text.Internal.Text
instance Data.Monoid.Monus.OverlappingGCDMonoid Data.Text.Internal.Lazy.Text


-- | 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. Since most practical monoids in Haskell
--   are not Abelian, there are also its three symmetric superclasses:
--   
--   <ul>
--   <li><a>LeftGCDMonoid</a></li>
--   <li><a>RightGCDMonoid</a></li>
--   <li><a>OverlappingGCDMonoid</a></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>
--   
--   If a <a>GCDMonoid</a> happens to also be <a>Cancellative</a>, it
--   should additionally satisfy the following laws:
--   
--   <pre>
--   gcd (a &lt;&gt; b) (a &lt;&gt; c) == a &lt;&gt; gcd b c
--   gcd (a &lt;&gt; c) (b &lt;&gt; c) == gcd a b &lt;&gt; 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>
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>
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>
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.GCD.GCDMonoid ()
instance Data.Monoid.GCD.GCDMonoid a => Data.Monoid.GCD.GCDMonoid (Data.Semigroup.Internal.Dual a)
instance Data.Monoid.GCD.GCDMonoid (Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.LeftGCDMonoid (Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.RightGCDMonoid (Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.GCDMonoid (Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.LeftGCDMonoid (Data.Semigroup.Internal.Product GHC.Num.Natural.Natural)
instance Data.Monoid.GCD.RightGCDMonoid (Data.Semigroup.Internal.Product 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 GHC.Classes.Ord a => Data.Monoid.GCD.GCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.GCDMonoid Data.IntSet.Internal.IntSet
instance Data.Monoid.GCD.RightGCDMonoid ()
instance Data.Monoid.GCD.LeftGCDMonoid a => Data.Monoid.GCD.RightGCDMonoid (Data.Semigroup.Internal.Dual a)
instance Data.Monoid.GCD.RightGCDMonoid a => Data.Monoid.GCD.LeftGCDMonoid (Data.Semigroup.Internal.Dual a)
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 x => Data.Monoid.GCD.RightGCDMonoid (GHC.Maybe.Maybe x)
instance GHC.Classes.Ord a => Data.Monoid.GCD.RightGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.RightGCDMonoid Data.IntSet.Internal.IntSet
instance GHC.Classes.Eq x => Data.Monoid.GCD.RightGCDMonoid [x]
instance GHC.Classes.Eq a => Data.Monoid.GCD.RightGCDMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Eq a => Data.Monoid.GCD.RightGCDMonoid (Data.Vector.Vector a)
instance Data.Monoid.GCD.RightGCDMonoid Data.ByteString.Internal.ByteString
instance Data.Monoid.GCD.RightGCDMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.GCD.RightGCDMonoid Data.Text.Internal.Text
instance Data.Monoid.GCD.RightGCDMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.GCD.LeftGCDMonoid ()
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 x => Data.Monoid.GCD.LeftGCDMonoid (GHC.Maybe.Maybe x)
instance GHC.Classes.Ord a => Data.Monoid.GCD.LeftGCDMonoid (Data.Set.Internal.Set a)
instance Data.Monoid.GCD.LeftGCDMonoid Data.IntSet.Internal.IntSet
instance (GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Monoid.GCD.LeftGCDMonoid (Data.Map.Internal.Map k a)
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftGCDMonoid (Data.IntMap.Internal.IntMap a)
instance GHC.Classes.Eq x => Data.Monoid.GCD.LeftGCDMonoid [x]
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftGCDMonoid (Data.Sequence.Internal.Seq a)
instance GHC.Classes.Eq a => Data.Monoid.GCD.LeftGCDMonoid (Data.Vector.Vector a)
instance Data.Monoid.GCD.LeftGCDMonoid Data.ByteString.Internal.ByteString
instance Data.Monoid.GCD.LeftGCDMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.GCD.LeftGCDMonoid Data.Text.Internal.Text
instance Data.Monoid.GCD.LeftGCDMonoid Data.Text.Internal.Lazy.Text


-- | 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.StableFactorial ()
instance Data.Semigroup.Factorial.StableFactorial a => Data.Semigroup.Factorial.StableFactorial (Data.Semigroup.Internal.Dual a)
instance Data.Semigroup.Factorial.StableFactorial [x]
instance Data.Semigroup.Factorial.StableFactorial Data.ByteString.Internal.ByteString
instance Data.Semigroup.Factorial.StableFactorial Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Factorial.StableFactorial Data.Text.Internal.Text
instance Data.Semigroup.Factorial.StableFactorial Data.Text.Internal.Lazy.Text
instance Data.Semigroup.Factorial.StableFactorial (Data.Sequence.Internal.Seq a)
instance Data.Semigroup.Factorial.StableFactorial (Data.Vector.Vector a)
instance Data.Semigroup.Factorial.StableFactorial (Data.Semigroup.Internal.Sum GHC.Num.Natural.Natural)
instance Data.Semigroup.Factorial.Factorial ()
instance Data.Semigroup.Factorial.Factorial a => Data.Semigroup.Factorial.Factorial (Data.Semigroup.Internal.Dual a)
instance (GHC.Real.Integral a, GHC.Classes.Eq a) => Data.Semigroup.Factorial.Factorial (Data.Semigroup.Internal.Sum a)
instance GHC.Real.Integral a => Data.Semigroup.Factorial.Factorial (Data.Semigroup.Internal.Product a)
instance Data.Semigroup.Factorial.Factorial a => Data.Semigroup.Factorial.Factorial (GHC.Maybe.Maybe a)
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 [x]
instance Data.Semigroup.Factorial.Factorial Data.ByteString.Internal.ByteString
instance Data.Semigroup.Factorial.Factorial Data.ByteString.Lazy.Internal.ByteString
instance Data.Semigroup.Factorial.Factorial Data.Text.Internal.Text
instance Data.Semigroup.Factorial.Factorial Data.Text.Internal.Lazy.Text
instance GHC.Classes.Ord k => Data.Semigroup.Factorial.Factorial (Data.Map.Internal.Map k v)
instance Data.Semigroup.Factorial.Factorial (Data.IntMap.Internal.IntMap a)
instance Data.Semigroup.Factorial.Factorial Data.IntSet.Internal.IntSet
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 Data.Semigroup.Factorial.Factorial (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 ()
instance Data.Monoid.Factorial.FactorialMonoid a => Data.Monoid.Factorial.FactorialMonoid (Data.Semigroup.Internal.Dual a)
instance (GHC.Real.Integral a, GHC.Classes.Eq a) => Data.Monoid.Factorial.FactorialMonoid (Data.Semigroup.Internal.Sum a)
instance GHC.Real.Integral a => Data.Monoid.Factorial.FactorialMonoid (Data.Semigroup.Internal.Product a)
instance Data.Monoid.Factorial.FactorialMonoid a => Data.Monoid.Factorial.FactorialMonoid (GHC.Maybe.Maybe a)
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 [x]
instance Data.Monoid.Factorial.FactorialMonoid Data.ByteString.Internal.ByteString
instance Data.Monoid.Factorial.FactorialMonoid Data.ByteString.Lazy.Internal.ByteString
instance Data.Monoid.Factorial.FactorialMonoid Data.Text.Internal.Text
instance Data.Monoid.Factorial.FactorialMonoid Data.Text.Internal.Lazy.Text
instance GHC.Classes.Ord k => Data.Monoid.Factorial.FactorialMonoid (Data.Map.Internal.Map k v)
instance Data.Monoid.Factorial.FactorialMonoid (Data.IntMap.Internal.IntMap a)
instance Data.Monoid.Factorial.FactorialMonoid Data.IntSet.Internal.IntSet
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 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.Base.String
instance Data.Monoid.Textual.TextualMonoid Data.Text.Internal.Text
instance Data.Monoid.Textual.TextualMonoid Data.Text.Internal.Lazy.Text
instance Data.Monoid.Textual.TextualMonoid (Data.Sequence.Internal.Seq GHC.Types.Char)


-- | This module contains orphan <a>IsString</a> and <a>TextualMonoid</a>
--   instances of <tt>Vector Char</tt>.
module Data.Monoid.Instances.CharVector
instance 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.Show.Show b, GHC.Show.Show a) => GHC.Show.Show (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.Classes.Eq b, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Data.Data a, Data.Data.Data b) => Data.Data.Data (Data.Monoid.Instances.Stateful.Stateful a b)
instance GHC.Base.Functor (Data.Monoid.Instances.Stateful.Stateful a)
instance GHC.Base.Monoid a => GHC.Base.Applicative (Data.Monoid.Instances.Stateful.Stateful a)
instance (GHC.Base.Semigroup a, GHC.Base.Semigroup b) => GHC.Base.Semigroup (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Base.Semigroup a, GHC.Base.Semigroup b, GHC.Base.Monoid a, GHC.Base.Monoid b) => GHC.Base.Monoid (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Monoid.Null.MonoidNull a, Data.Monoid.Null.MonoidNull b) => Data.Monoid.Null.MonoidNull (Data.Monoid.Instances.Stateful.Stateful a b)
instance (Data.Monoid.Null.PositiveMonoid a, Data.Monoid.Null.PositiveMonoid b) => Data.Monoid.Null.PositiveMonoid (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 (Data.Semigroup.Cancellative.RightReductive a, Data.Semigroup.Cancellative.RightReductive b) => Data.Semigroup.Cancellative.RightReductive (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.Monoid.GCD.RightGCDMonoid a, Data.Monoid.GCD.RightGCDMonoid b) => Data.Monoid.GCD.RightGCDMonoid (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 (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.StableFactorial a, Data.Semigroup.Factorial.StableFactorial b) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Stateful.Stateful a b)
instance (GHC.Base.Monoid a, Data.String.IsString b) => Data.String.IsString (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 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 Data.Data.Data m => Data.Data.Data (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance Data.Data.Data m => Data.Data.Data (Data.Monoid.Instances.Positioned.LinePositioned m)
instance GHC.Base.Functor Data.Monoid.Instances.Positioned.LinePositioned
instance GHC.Base.Applicative Data.Monoid.Instances.Positioned.LinePositioned
instance Data.Monoid.Instances.Positioned.Positioned Data.Monoid.Instances.Positioned.LinePositioned
instance GHC.Classes.Eq m => GHC.Classes.Eq (Data.Monoid.Instances.Positioned.LinePositioned m)
instance GHC.Classes.Ord m => GHC.Classes.Ord (Data.Monoid.Instances.Positioned.LinePositioned m)
instance GHC.Show.Show m => GHC.Show.Show (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => GHC.Base.Semigroup (Data.Monoid.Instances.Positioned.LinePositioned m)
instance (Data.Semigroup.Factorial.StableFactorial m, Data.Monoid.Textual.TextualMonoid m) => GHC.Base.Monoid (Data.Monoid.Instances.Positioned.LinePositioned 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.Textual.TextualMonoid m) => Data.Monoid.Null.PositiveMonoid (Data.Monoid.Instances.Positioned.LinePositioned 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.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.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.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.Textual.TextualMonoid m) => Data.Semigroup.Factorial.Factorial (Data.Monoid.Instances.Positioned.LinePositioned 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.Textual.TextualMonoid m) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Positioned.LinePositioned m)
instance Data.String.IsString m => Data.String.IsString (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.LinePositioned m)
instance GHC.Base.Functor Data.Monoid.Instances.Positioned.OffsetPositioned
instance GHC.Base.Applicative Data.Monoid.Instances.Positioned.OffsetPositioned
instance Data.Monoid.Instances.Positioned.Positioned Data.Monoid.Instances.Positioned.OffsetPositioned
instance GHC.Classes.Eq m => GHC.Classes.Eq (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance GHC.Classes.Ord m => GHC.Classes.Ord (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance GHC.Show.Show m => GHC.Show.Show (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance Data.Semigroup.Factorial.StableFactorial m => GHC.Base.Semigroup (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance (Data.Monoid.Factorial.FactorialMonoid m, Data.Semigroup.Factorial.StableFactorial m) => GHC.Base.Monoid (Data.Monoid.Instances.Positioned.OffsetPositioned 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.Factorial.FactorialMonoid m) => Data.Monoid.Null.PositiveMonoid (Data.Monoid.Instances.Positioned.OffsetPositioned 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.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.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.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.Semigroup.Factorial.Factorial (Data.Monoid.Instances.Positioned.OffsetPositioned 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.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Positioned.OffsetPositioned m)
instance Data.String.IsString m => Data.String.IsString (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.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.Show.Show a => GHC.Show.Show (Data.Monoid.Instances.Measured.Measured a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Monoid.Instances.Measured.Measured a)
instance Data.Data.Data a => Data.Data.Data (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.Base.Semigroup (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, GHC.Base.Monoid a) => GHC.Base.Monoid (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, GHC.Base.Monoid a) => Data.Monoid.Null.MonoidNull (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Semigroup.Factorial.StableFactorial a, GHC.Base.Monoid a) => Data.Monoid.Null.PositiveMonoid (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.Cancellative.RightReductive a, Data.Semigroup.Factorial.StableFactorial a) => Data.Semigroup.Cancellative.RightReductive (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.Monoid.GCD.RightGCDMonoid a, Data.Semigroup.Factorial.StableFactorial a) => Data.Monoid.GCD.RightGCDMonoid (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.Semigroup.Factorial.StableFactorial a, Data.Monoid.Null.MonoidNull a) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Measured.Measured a)
instance (Data.Monoid.Factorial.FactorialMonoid a, Data.String.IsString a) => Data.String.IsString (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.Show.Show a => GHC.Show.Show (Data.Monoid.Instances.Concat.Concat a)
instance Data.Data.Data a => Data.Data.Data (Data.Monoid.Instances.Concat.Concat a)
instance (GHC.Classes.Eq a, GHC.Base.Semigroup a) => GHC.Classes.Eq (Data.Monoid.Instances.Concat.Concat a)
instance (GHC.Classes.Ord a, GHC.Base.Semigroup a) => GHC.Classes.Ord (Data.Monoid.Instances.Concat.Concat a)
instance GHC.Base.Functor Data.Monoid.Instances.Concat.Concat
instance GHC.Base.Applicative Data.Monoid.Instances.Concat.Concat
instance Data.Foldable.Foldable Data.Monoid.Instances.Concat.Concat
instance Data.Monoid.Null.PositiveMonoid a => GHC.Base.Semigroup (Data.Monoid.Instances.Concat.Concat a)
instance Data.Monoid.Null.PositiveMonoid a => GHC.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 Data.Monoid.Null.PositiveMonoid a => Data.Monoid.Null.PositiveMonoid (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.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.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.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.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 (Data.Semigroup.Factorial.Factorial a, Data.Monoid.Null.PositiveMonoid a) => Data.Semigroup.Factorial.StableFactorial (Data.Monoid.Instances.Concat.Concat a)
instance Data.String.IsString a => Data.String.IsString (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.Classes.Ord Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Classes.Eq Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Data.Data Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Base.Semigroup Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance GHC.Base.Monoid Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Monoid.Null.MonoidNull Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Semigroup.Cancellative.LeftReductive 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 GHC.Show.Show Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.String.IsString Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8
instance Data.Monoid.Null.PositiveMonoid 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 Data.Monoid.Textual.TextualMonoid Data.Monoid.Instances.ByteString.UTF8.ByteStringUTF8