-- 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 0.4.0.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 PositiveMonoid (Vector a)
instance Ord a => PositiveMonoid (Set a)
instance PositiveMonoid (Seq a)
instance PositiveMonoid IntSet
instance PositiveMonoid (IntMap v)
instance Ord k => PositiveMonoid (Map k v)
instance PositiveMonoid [x]
instance PositiveMonoid a => PositiveMonoid (Dual a)
instance PositiveMonoid (Last a)
instance PositiveMonoid (First a)
instance Monoid a => PositiveMonoid (Maybe a)
instance PositiveMonoid Text
instance PositiveMonoid Text
instance PositiveMonoid ByteString
instance PositiveMonoid ByteString
instance PositiveMonoid Any
instance PositiveMonoid All
instance PositiveMonoid Ordering
instance PositiveMonoid ()
instance MonoidNull (Vector a)
instance Ord a => MonoidNull (Set a)
instance MonoidNull (Seq a)
instance MonoidNull IntSet
instance MonoidNull (IntMap v)
instance Ord k => MonoidNull (Map k v)
instance MonoidNull Text
instance MonoidNull Text
instance MonoidNull ByteString
instance MonoidNull ByteString
instance MonoidNull [x]
instance (MonoidNull a, MonoidNull b) => MonoidNull (a, b)
instance Monoid a => MonoidNull (Maybe a)
instance (Num a, Eq a) => MonoidNull (Product a)
instance (Num a, Eq a) => MonoidNull (Sum a)
instance MonoidNull a => MonoidNull (Dual a)
instance MonoidNull (Last a)
instance MonoidNull (First a)
instance MonoidNull Any
instance MonoidNull All
instance MonoidNull Ordering
instance MonoidNull ()


-- | 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. 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>
--   mconcat . factors == id
--   null == List.null . factors
--   List.all (\prime-&gt; factors prime == [prime]) . 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.tails . factors
--   tails == List.map mconcat . List.tails . factors
--   foldl f a == List.foldl f a . factors
--   foldl' f a == List.foldl' f a . factors
--   foldr f a == List.foldr f a . 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 must implement <a>factors</a> or
--   <a>splitPrimePrefix</a>. Other methods are provided and should be
--   implemented only for performance reasons.
class MonoidNull m => FactorialMonoid m where factors = unfoldr splitPrimePrefix primePrefix = maybe mempty fst . splitPrimePrefix primeSuffix = maybe mempty snd . splitPrimeSuffix splitPrimePrefix x = case factors x of { [] -> Nothing prefix : rest -> Just (prefix, mconcat rest) } splitPrimeSuffix x = case factors x of { [] -> Nothing fs -> Just (mconcat (init fs), last fs) } inits = foldr (\ m l -> mempty : map (mappend m) l) [mempty] tails m = m : maybe [] (tails . snd) (splitPrimePrefix m) foldl f f0 = foldl f f0 . factors foldl' f f0 = foldl' f f0 . factors foldr f f0 = foldr f f0 . factors length = length . factors foldMap f = foldr (mappend . f) mempty span p m = spanAfter id m where spanAfter f m = case splitPrimePrefix m of { Just (prime, rest) | p prime -> spanAfter (f . mappend prime) rest _ -> (f mempty, m) } break = span . (not .) spanMaybe s0 f m0 = spanAfter id s0 m0 where spanAfter g s m = case splitPrimePrefix m of { Just (prime, rest) | Just s' <- f s prime -> spanAfter (g . mappend prime) s' rest | otherwise -> (g mempty, m, s) Nothing -> (m0, m, s) } spanMaybe' s0 f m0 = spanAfter id s0 m0 where spanAfter g s m = seq s $ case splitPrimePrefix m of { Just (prime, rest) | Just s' <- f s prime -> spanAfter (g . mappend prime) s' rest | otherwise -> (g mempty, m, s) Nothing -> (m0, m, s) } split p m = prefix : splitRest where (prefix, rest) = break p m splitRest = case splitPrimePrefix rest of { Nothing -> [] Just (_, tail) -> split p tail } takeWhile p = fst . span p dropWhile p = snd . span p splitAt n m | n <= 0 = (mempty, m) | otherwise = split n id m where split 0 f m = (f mempty, m) split n f m = case splitPrimePrefix m of { Nothing -> (f mempty, m) Just (prime, rest) -> split (pred n) (f . mappend prime) rest } drop n p = snd (splitAt n p) take n p = fst (splitAt n p) reverse = mconcat . reverse . factors
factors :: FactorialMonoid m => m -> [m]
primePrefix :: FactorialMonoid m => m -> m
primeSuffix :: FactorialMonoid m => m -> m
splitPrimePrefix :: FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix :: FactorialMonoid m => m -> Maybe (m, m)
inits :: FactorialMonoid m => m -> [m]
tails :: FactorialMonoid m => m -> [m]
foldl :: FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' :: FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldr :: FactorialMonoid m => (m -> a -> a) -> a -> m -> a
length :: FactorialMonoid m => m -> Int
foldMap :: (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
span :: FactorialMonoid m => (m -> Bool) -> m -> (m, m)
break :: FactorialMonoid m => (m -> Bool) -> m -> (m, m)
split :: FactorialMonoid m => (m -> Bool) -> m -> [m]
takeWhile :: FactorialMonoid m => (m -> Bool) -> m -> m
dropWhile :: FactorialMonoid m => (m -> Bool) -> m -> m
spanMaybe :: FactorialMonoid m => s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' :: FactorialMonoid m => s -> (s -> m -> Maybe s) -> m -> (m, m, s)
splitAt :: FactorialMonoid m => Int -> m -> (m, m)
drop :: FactorialMonoid m => Int -> m -> m
take :: FactorialMonoid m => Int -> m -> m
reverse :: FactorialMonoid m => m -> m

-- | A subclass of <a>FactorialMonoid</a> whose instances satisfy this
--   additional law:
--   
--   <pre>
--   factors (a &lt;&gt; b) == factors a &lt;&gt; factors b
--   </pre>
class (FactorialMonoid m, PositiveMonoid m) => StableFactorialMonoid m

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

-- | A <a>mapM_</a> equivalent.
mapM_ :: (FactorialMonoid a, Monad m) => (a -> m b) -> a -> m ()
instance StableFactorialMonoid (Vector a)
instance StableFactorialMonoid (Seq a)
instance StableFactorialMonoid Text
instance StableFactorialMonoid Text
instance StableFactorialMonoid ByteString
instance StableFactorialMonoid ByteString
instance StableFactorialMonoid [x]
instance StableFactorialMonoid a => StableFactorialMonoid (Dual a)
instance StableFactorialMonoid ()
instance FactorialMonoid (Vector a)
instance Ord a => FactorialMonoid (Set a)
instance FactorialMonoid (Seq a)
instance FactorialMonoid IntSet
instance FactorialMonoid (IntMap a)
instance Ord k => FactorialMonoid (Map k v)
instance FactorialMonoid Text
instance FactorialMonoid Text
instance FactorialMonoid ByteString
instance FactorialMonoid ByteString
instance FactorialMonoid [x]
instance (FactorialMonoid a, FactorialMonoid b) => FactorialMonoid (a, b)
instance FactorialMonoid a => FactorialMonoid (Maybe a)
instance Integral a => FactorialMonoid (Product a)
instance (Integral a, Eq a) => FactorialMonoid (Sum a)
instance FactorialMonoid a => FactorialMonoid (Dual a)
instance FactorialMonoid ()


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

-- | Class of all Abelian ({i.e.}, commutative) monoids that satisfy the
--   commutativity property:
--   
--   <pre>
--   a &lt;&gt; b == b &lt;&gt; a
--   </pre>
class Monoid m => CommutativeMonoid m

-- | Class of Abelian monoids with a partial inverse for the Monoid
--   <tt>&lt;&gt;</tt> 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>
class (CommutativeMonoid m, LeftReductiveMonoid m, RightReductiveMonoid m) => ReductiveMonoid m
(</>) :: ReductiveMonoid m => m -> m -> Maybe m

-- | Subclass of <a>ReductiveMonoid</a> where <a>&lt;/&gt;</a> is a
--   complete inverse of the Monoid <tt>&lt;&gt;</tt> 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 (LeftCancellativeMonoid m, RightCancellativeMonoid m, ReductiveMonoid m) => CancellativeMonoid m

-- | Class of Abelian monoids that allow the greatest common denominator 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 <a>CancellativeMonoid</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 (ReductiveMonoid m, LeftGCDMonoid m, RightGCDMonoid m) => GCDMonoid m
gcd :: GCDMonoid m => m -> m -> m

-- | Class of monoids with a left inverse of <a>mappend</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. Its complexity should be no worse than
--   linear in the length of the prefix argument.
class Monoid m => LeftReductiveMonoid m where isPrefixOf a b = isJust (stripPrefix a b)
isPrefixOf :: LeftReductiveMonoid m => m -> m -> Bool
stripPrefix :: LeftReductiveMonoid m => m -> m -> Maybe m

-- | Class of monoids with a right inverse of <a>mappend</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. Its complexity should be no worse than
--   linear in the length of the suffix argument.
class Monoid m => RightReductiveMonoid m where isSuffixOf a b = isJust (stripSuffix a b)
isSuffixOf :: RightReductiveMonoid m => m -> m -> Bool
stripSuffix :: RightReductiveMonoid m => m -> m -> Maybe m

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

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

-- | Class of monoids capable of finding the equivalent of greatest common
--   divisor on the left side of two monoidal values. The methods'
--   complexity should be no worse than linear in the length of the common
--   prefix. 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>
class LeftReductiveMonoid m => LeftGCDMonoid m where commonPrefix x y = p where (p, _, _) = stripCommonPrefix x y stripCommonPrefix x y = (p, x', y') where p = commonPrefix x y Just x' = stripPrefix p x Just y' = stripPrefix p y
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 methods'
--   complexity must be no worse than linear in the length of the common
--   suffix. 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>
class RightReductiveMonoid m => RightGCDMonoid m where commonSuffix x y = s where (_, _, s) = stripCommonSuffix x y stripCommonSuffix x y = (x', y', s) where s = commonSuffix x y Just x' = stripSuffix s x Just y' = stripSuffix s y
commonSuffix :: RightGCDMonoid m => m -> m -> m
stripCommonSuffix :: RightGCDMonoid m => m -> m -> (m, m, m)
instance LeftGCDMonoid Text
instance RightCancellativeMonoid Text
instance LeftCancellativeMonoid Text
instance RightReductiveMonoid Text
instance LeftReductiveMonoid Text
instance LeftGCDMonoid Text
instance RightCancellativeMonoid Text
instance LeftCancellativeMonoid Text
instance RightReductiveMonoid Text
instance LeftReductiveMonoid Text
instance RightGCDMonoid ByteString
instance LeftGCDMonoid ByteString
instance RightCancellativeMonoid ByteString
instance LeftCancellativeMonoid ByteString
instance RightReductiveMonoid ByteString
instance LeftReductiveMonoid ByteString
instance RightGCDMonoid ByteString
instance LeftGCDMonoid ByteString
instance RightCancellativeMonoid ByteString
instance LeftCancellativeMonoid ByteString
instance RightReductiveMonoid ByteString
instance LeftReductiveMonoid ByteString
instance Eq a => RightGCDMonoid (Vector a)
instance Eq a => LeftGCDMonoid (Vector a)
instance Eq a => RightCancellativeMonoid (Vector a)
instance Eq a => LeftCancellativeMonoid (Vector a)
instance Eq a => RightReductiveMonoid (Vector a)
instance Eq a => LeftReductiveMonoid (Vector a)
instance Eq a => RightGCDMonoid (Seq a)
instance Eq a => LeftGCDMonoid (Seq a)
instance Eq a => RightCancellativeMonoid (Seq a)
instance Eq a => LeftCancellativeMonoid (Seq a)
instance Eq a => RightReductiveMonoid (Seq a)
instance Eq a => LeftReductiveMonoid (Seq a)
instance Eq x => LeftGCDMonoid [x]
instance Eq x => LeftCancellativeMonoid [x]
instance Eq x => LeftReductiveMonoid [x]
instance Eq a => LeftGCDMonoid (IntMap a)
instance LeftReductiveMonoid (IntMap a)
instance (Ord k, Eq a) => LeftGCDMonoid (Map k a)
instance Ord k => LeftReductiveMonoid (Map k a)
instance GCDMonoid IntSet
instance RightGCDMonoid IntSet
instance LeftGCDMonoid IntSet
instance ReductiveMonoid IntSet
instance RightReductiveMonoid IntSet
instance LeftReductiveMonoid IntSet
instance CommutativeMonoid IntSet
instance Ord a => GCDMonoid (Set a)
instance Ord a => RightGCDMonoid (Set a)
instance Ord a => LeftGCDMonoid (Set a)
instance Ord a => ReductiveMonoid (Set a)
instance Ord a => RightReductiveMonoid (Set a)
instance Ord a => LeftReductiveMonoid (Set a)
instance Ord a => CommutativeMonoid (Set a)
instance RightGCDMonoid x => RightGCDMonoid (Maybe x)
instance RightReductiveMonoid x => RightReductiveMonoid (Maybe x)
instance LeftGCDMonoid x => LeftGCDMonoid (Maybe x)
instance LeftReductiveMonoid x => LeftReductiveMonoid (Maybe x)
instance (RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (a, b)
instance (LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (a, b)
instance (RightCancellativeMonoid a, RightCancellativeMonoid b) => RightCancellativeMonoid (a, b)
instance (LeftCancellativeMonoid a, LeftCancellativeMonoid b) => LeftCancellativeMonoid (a, b)
instance (RightReductiveMonoid a, RightReductiveMonoid b) => RightReductiveMonoid (a, b)
instance (LeftReductiveMonoid a, LeftReductiveMonoid b) => LeftReductiveMonoid (a, b)
instance (GCDMonoid a, GCDMonoid b) => GCDMonoid (a, b)
instance (CancellativeMonoid a, CancellativeMonoid b) => CancellativeMonoid (a, b)
instance (ReductiveMonoid a, ReductiveMonoid b) => ReductiveMonoid (a, b)
instance (CommutativeMonoid a, CommutativeMonoid b) => CommutativeMonoid (a, b)
instance Integral a => RightGCDMonoid (Product a)
instance Integral a => LeftGCDMonoid (Product a)
instance Integral a => RightReductiveMonoid (Product a)
instance Integral a => LeftReductiveMonoid (Product a)
instance Integral a => GCDMonoid (Product a)
instance Integral a => ReductiveMonoid (Product a)
instance Num a => CommutativeMonoid (Product a)
instance (Integral a, Ord a) => RightGCDMonoid (Sum a)
instance (Integral a, Ord a) => LeftGCDMonoid (Sum a)
instance Integral a => RightCancellativeMonoid (Sum a)
instance Integral a => LeftCancellativeMonoid (Sum a)
instance Integral a => RightReductiveMonoid (Sum a)
instance Integral a => LeftReductiveMonoid (Sum a)
instance (Integral a, Ord a) => GCDMonoid (Sum a)
instance Integral a => CancellativeMonoid (Sum a)
instance Integral a => ReductiveMonoid (Sum a)
instance Num a => CommutativeMonoid (Sum a)
instance RightGCDMonoid a => LeftGCDMonoid (Dual a)
instance LeftGCDMonoid a => RightGCDMonoid (Dual a)
instance RightCancellativeMonoid a => LeftCancellativeMonoid (Dual a)
instance LeftCancellativeMonoid a => RightCancellativeMonoid (Dual a)
instance RightReductiveMonoid a => LeftReductiveMonoid (Dual a)
instance LeftReductiveMonoid a => RightReductiveMonoid (Dual a)
instance GCDMonoid a => GCDMonoid (Dual a)
instance CancellativeMonoid a => CancellativeMonoid (Dual a)
instance ReductiveMonoid a => ReductiveMonoid (Dual a)
instance CommutativeMonoid a => CommutativeMonoid (Dual a)
instance RightGCDMonoid ()
instance LeftGCDMonoid ()
instance RightCancellativeMonoid ()
instance LeftCancellativeMonoid ()
instance RightReductiveMonoid ()
instance LeftReductiveMonoid ()
instance GCDMonoid ()
instance CancellativeMonoid ()
instance ReductiveMonoid ()
instance CommutativeMonoid ()


-- | 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)
--   </pre>
--   
--   A minimal instance definition must implement
--   <a>splitCharacterPrefix</a>.
class (IsString t, LeftReductiveMonoid t, LeftGCDMonoid t, FactorialMonoid t) => TextualMonoid t where fromText = fromString . unpack singleton = fromString . (: []) characterPrefix = fmap fst . splitCharacterPrefix map f = concatMap (singleton . f) concatMap f = foldr mappend (mappend . f) mempty all p = foldr (const id) ((&&) . p) True any p = foldr (const id) ((||) . p) False foldl ft fc = foldl (\ a prime -> maybe (ft a prime) (fc a) (characterPrefix prime)) foldr ft fc = foldr (\ prime -> maybe (ft prime) fc (characterPrefix prime)) foldl' ft fc = foldl' (\ a prime -> maybe (ft a prime) (fc a) (characterPrefix prime)) foldl_ = foldl const foldr_ = foldr (const id) foldl_' = foldl' const scanl f c = mappend (singleton c) . fst . foldl foldlOther (foldlChars f) (mempty, c) scanl1 f t = case (splitPrimePrefix t, splitCharacterPrefix t) of { (Nothing, _) -> t (Just (prefix, suffix), Nothing) -> mappend prefix (scanl1 f suffix) (Just _, Just (c, suffix)) -> scanl f c suffix } scanr f c = fst . foldr foldrOther (foldrChars f) (singleton c, c) scanr1 f = fst . foldr foldrOther fc (mempty, Nothing) where fc c (t, Nothing) = (mappend (singleton c) t, Just c) fc c1 (t, Just c2) = (mappend (singleton c') t, Just c') where c' = f c1 c2 mapAccumL f a0 = foldl ft fc (a0, mempty) where ft (a, t1) t2 = (a, mappend t1 t2) fc (a, t) c = (a', mappend t (singleton c')) where (a', c') = f a c mapAccumR f a0 = foldr ft fc (a0, mempty) where ft t1 (a, t2) = (a, mappend t1 t2) fc c (a, t) = (a', mappend (singleton c') t) where (a', c') = f a c takeWhile pt pc = fst . span pt pc dropWhile pt pc = snd . span pt pc span pt pc = span (\ prime -> maybe (pt prime) pc (characterPrefix prime)) break pt pc = break (\ prime -> maybe (pt prime) pc (characterPrefix prime)) spanMaybe s0 ft fc t0 = spanAfter id s0 t0 where spanAfter g s t = case splitPrimePrefix t of { Just (prime, rest) | Just s' <- maybe (ft s prime) (fc s) (characterPrefix prime) -> spanAfter (g . mappend prime) s' rest | otherwise -> (g mempty, t, s) Nothing -> (t0, t, s) } spanMaybe' s0 ft fc t0 = spanAfter id s0 t0 where spanAfter g s t = seq s $ case splitPrimePrefix t of { Just (prime, rest) | Just s' <- maybe (ft s prime) (fc s) (characterPrefix prime) -> spanAfter (g . mappend prime) s' rest | otherwise -> (g mempty, t, s) Nothing -> (t0, t, s) } takeWhile_ = takeWhile . const dropWhile_ = dropWhile . const break_ = break . const span_ = span . const spanMaybe_ s = spanMaybe s (const . Just) spanMaybe_' s = spanMaybe' s (const . Just) split p m = prefix : splitRest where (prefix, rest) = break (const False) p m splitRest = case splitCharacterPrefix rest of { Nothing -> [] Just (_, tail) -> split p tail } find p = foldr (const id) (\ c r -> if p c then Just c else r) Nothing elem c = any (== c)
fromText :: TextualMonoid t => Text -> t
singleton :: TextualMonoid t => Char -> t
splitCharacterPrefix :: TextualMonoid t => t -> Maybe (Char, t)
characterPrefix :: TextualMonoid t => t -> Maybe Char
map :: TextualMonoid t => (Char -> Char) -> t -> t
concatMap :: TextualMonoid t => (Char -> t) -> t -> t
any :: TextualMonoid t => (Char -> Bool) -> t -> Bool
all :: TextualMonoid t => (Char -> Bool) -> t -> Bool
foldl :: TextualMonoid t => (a -> t -> a) -> (a -> Char -> a) -> a -> t -> a
foldl' :: TextualMonoid t => (a -> t -> a) -> (a -> Char -> a) -> a -> t -> a
foldr :: TextualMonoid t => (t -> a -> a) -> (Char -> a -> a) -> a -> t -> a
scanl :: TextualMonoid t => (Char -> Char -> Char) -> Char -> t -> t
scanl1 :: TextualMonoid t => (Char -> Char -> Char) -> t -> t
scanr :: TextualMonoid t => (Char -> Char -> Char) -> Char -> t -> t
scanr1 :: TextualMonoid t => (Char -> Char -> Char) -> t -> t
mapAccumL :: TextualMonoid t => (a -> Char -> (a, Char)) -> a -> t -> (a, t)
mapAccumR :: TextualMonoid t => (a -> Char -> (a, Char)) -> a -> t -> (a, t)
takeWhile :: TextualMonoid t => (t -> Bool) -> (Char -> Bool) -> t -> t
dropWhile :: TextualMonoid t => (t -> Bool) -> (Char -> Bool) -> t -> t
break :: TextualMonoid t => (t -> Bool) -> (Char -> Bool) -> t -> (t, t)
span :: TextualMonoid t => (t -> Bool) -> (Char -> Bool) -> t -> (t, t)
spanMaybe :: TextualMonoid t => s -> (s -> t -> Maybe s) -> (s -> Char -> Maybe s) -> t -> (t, t, s)
spanMaybe' :: TextualMonoid t => s -> (s -> t -> Maybe s) -> (s -> Char -> Maybe s) -> t -> (t, t, s)
split :: TextualMonoid t => (Char -> Bool) -> t -> [t]
find :: TextualMonoid t => (Char -> Bool) -> t -> Maybe Char
elem :: TextualMonoid t => Char -> t -> Bool
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
takeWhile_ :: TextualMonoid t => Bool -> (Char -> Bool) -> t -> t
dropWhile_ :: TextualMonoid t => Bool -> (Char -> Bool) -> t -> t
break_ :: TextualMonoid t => Bool -> (Char -> Bool) -> t -> (t, t)
span_ :: TextualMonoid t => Bool -> (Char -> Bool) -> t -> (t, t)
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 TextualMonoid (Vector Char)
instance IsString (Vector Char)
instance TextualMonoid (Seq Char)
instance IsString (Seq Char)
instance TextualMonoid Text
instance TextualMonoid Text
instance TextualMonoid String


-- | 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 Eq ByteStringUTF8
instance Ord ByteStringUTF8
instance TextualMonoid ByteStringUTF8
instance FactorialMonoid ByteStringUTF8
instance PositiveMonoid ByteStringUTF8
instance IsString ByteStringUTF8
instance Show ByteStringUTF8
instance LeftGCDMonoid ByteStringUTF8
instance LeftCancellativeMonoid ByteStringUTF8
instance LeftReductiveMonoid ByteStringUTF8
instance MonoidNull ByteStringUTF8
instance Monoid ByteStringUTF8


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

-- | <tt><a>Concat</a> a</tt> is a <tt>newtype</tt> wrapper around
--   <tt><a>Seq</a> a</tt>. 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 <a>Concat</a> has the effect of making <a>mappend</a> a
--   constant-time operation.
data Concat a
concatenate :: (MonoidNull a, PositiveMonoid a) => Seq a -> Concat a
extract :: Concat a -> Seq a
instance Show a => Show (Concat a)
instance (Eq a, TextualMonoid a, StableFactorialMonoid a) => TextualMonoid (Concat a)
instance IsString a => IsString (Concat a)
instance FactorialMonoid a => FactorialMonoid (Concat a)
instance (Eq a, RightGCDMonoid a, MonoidNull a, StableFactorialMonoid a) => RightGCDMonoid (Concat a)
instance (Eq a, LeftGCDMonoid a, MonoidNull a, StableFactorialMonoid a) => LeftGCDMonoid (Concat a)
instance (MonoidNull a, RightReductiveMonoid a, StableFactorialMonoid a) => RightReductiveMonoid (Concat a)
instance (LeftReductiveMonoid a, MonoidNull a, StableFactorialMonoid a) => LeftReductiveMonoid (Concat a)
instance PositiveMonoid (Concat a)
instance MonoidNull (Concat a)
instance Monoid (Concat a)
instance Applicative Concat
instance Functor Concat
instance (Ord a, Monoid a) => Ord (Concat a)
instance (Eq a, Monoid a) => Eq (Concat a)


-- | 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>StableFactorialMonoid</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 :: FactorialMonoid a => a -> Measured a
extract :: Measured a -> a
instance Eq a => Eq (Measured a)
instance Show a => Show (Measured a)
instance (Eq a, TextualMonoid a, StableFactorialMonoid a) => TextualMonoid (Measured a)
instance (FactorialMonoid a, IsString a) => IsString (Measured a)
instance StableFactorialMonoid a => StableFactorialMonoid (Measured a)
instance StableFactorialMonoid a => FactorialMonoid (Measured a)
instance (RightGCDMonoid a, StableFactorialMonoid a) => RightGCDMonoid (Measured a)
instance (LeftGCDMonoid a, StableFactorialMonoid a) => LeftGCDMonoid (Measured a)
instance (RightReductiveMonoid a, StableFactorialMonoid a) => RightReductiveMonoid (Measured a)
instance (LeftReductiveMonoid a, StableFactorialMonoid a) => LeftReductiveMonoid (Measured a)
instance StableFactorialMonoid a => PositiveMonoid (Measured a)
instance StableFactorialMonoid a => MonoidNull (Measured a)
instance StableFactorialMonoid a => Monoid (Measured a)
instance Ord a => Ord (Measured a)


-- | 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>StableFactorialMonoid</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.
--   
--   All positions are zero-based:
--   
--   <pre>
--   &gt; let p = pure "abcd\nefgh\nijkl\nmnop\n" :: LinePositioned String
--   &gt; p
--   Line 0, column 0: "abcd\nefgh\nijkl\nmnop\n"
--   &gt; Data.Monoid.Factorial.drop 13 p
--   Line 2, column 3: "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 (StableFactorialMonoid m, TextualMonoid m) => TextualMonoid (LinePositioned m)
instance (StableFactorialMonoid m, TextualMonoid m) => TextualMonoid (OffsetPositioned m)
instance IsString m => IsString (LinePositioned m)
instance IsString m => IsString (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m) => StableFactorialMonoid (LinePositioned m)
instance StableFactorialMonoid m => StableFactorialMonoid (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m) => FactorialMonoid (LinePositioned m)
instance StableFactorialMonoid m => FactorialMonoid (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m, RightGCDMonoid m) => RightGCDMonoid (LinePositioned m)
instance (StableFactorialMonoid m, RightGCDMonoid m) => RightGCDMonoid (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m, RightReductiveMonoid m) => RightReductiveMonoid (LinePositioned m)
instance (StableFactorialMonoid m, RightReductiveMonoid m) => RightReductiveMonoid (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (LinePositioned m)
instance (StableFactorialMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m, LeftReductiveMonoid m) => LeftReductiveMonoid (LinePositioned m)
instance (StableFactorialMonoid m, LeftReductiveMonoid m) => LeftReductiveMonoid (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m, PositiveMonoid m) => PositiveMonoid (LinePositioned m)
instance (StableFactorialMonoid m, PositiveMonoid m) => PositiveMonoid (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m, MonoidNull m) => MonoidNull (LinePositioned m)
instance (StableFactorialMonoid m, MonoidNull m) => MonoidNull (OffsetPositioned m)
instance (StableFactorialMonoid m, TextualMonoid m) => Monoid (LinePositioned m)
instance StableFactorialMonoid m => Monoid (OffsetPositioned m)
instance Show m => Show (LinePositioned m)
instance Show m => Show (OffsetPositioned m)
instance Ord m => Ord (LinePositioned m)
instance Ord m => Ord (OffsetPositioned m)
instance Eq m => Eq (LinePositioned m)
instance Eq m => Eq (OffsetPositioned m)
instance Positioned LinePositioned
instance Positioned OffsetPositioned
instance Applicative LinePositioned
instance Applicative OffsetPositioned
instance Functor LinePositioned
instance Functor OffsetPositioned


-- | 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 (Eq a, Eq b) => Eq (Stateful a b)
instance (Ord a, Ord b) => Ord (Stateful a b)
instance (Show a, Show b) => Show (Stateful a b)
instance (LeftGCDMonoid a, FactorialMonoid a, TextualMonoid b) => TextualMonoid (Stateful a b)
instance (Monoid a, IsString b) => IsString (Stateful a b)
instance (StableFactorialMonoid a, StableFactorialMonoid b) => StableFactorialMonoid (Stateful a b)
instance (FactorialMonoid a, FactorialMonoid b) => FactorialMonoid (Stateful a b)
instance (RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (Stateful a b)
instance (LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (Stateful a b)
instance (RightReductiveMonoid a, RightReductiveMonoid b) => RightReductiveMonoid (Stateful a b)
instance (LeftReductiveMonoid a, LeftReductiveMonoid b) => LeftReductiveMonoid (Stateful a b)
instance (PositiveMonoid a, PositiveMonoid b) => PositiveMonoid (Stateful a b)
instance (MonoidNull a, MonoidNull b) => MonoidNull (Stateful a b)
instance (Monoid a, Monoid b) => Monoid (Stateful a b)
instance Monoid a => Applicative (Stateful a)
instance Functor (Stateful a)