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


-- | basic algebra
--   
--   Groups, rings, and semirings.
@package rings
@version 0.0.1

module Data.Group

-- | A <a>Group</a> is a <a>Monoid</a> plus a function, <a>negate</a>, such
--   that:
--   
--   <pre>
--   a &lt;&lt; negate a == mempty
--   </pre>
--   
--   <pre>
--   negate a &lt;&lt; a == mempty
--   </pre>
class Monoid a => Group a
negate :: Group a => a -> a
(<<) :: Group a => a -> a -> a
infixl 6 <<


-- | Orphan instances from base.
module Data.Semigroup.Orphan
instance GHC.Base.Semigroup GHC.Types.Word
instance GHC.Base.Monoid GHC.Types.Word
instance GHC.Base.Semigroup GHC.Types.Int
instance GHC.Base.Monoid GHC.Types.Int
instance GHC.Base.Semigroup GHC.Types.Bool
instance GHC.Base.Monoid GHC.Types.Bool
instance GHC.Base.Semigroup GHC.Types.Float
instance GHC.Base.Monoid GHC.Types.Float
instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Data.Complex.Complex a)
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Complex.Complex a)
instance GHC.Base.Semigroup GHC.Natural.Natural
instance GHC.Base.Monoid GHC.Natural.Natural

module Data.Semiring

-- | Right pre-semirings and (non-unital and unital) right semirings.
--   
--   A right pre-semiring (sometimes referred to as a bisemigroup) is a
--   type <i>R</i> endowed with two associative binary (i.e. semigroup)
--   operations: (&lt;&gt;) and (&gt;&lt;), along with a
--   right-distributivity property connecting them:
--   
--   <pre>
--   (a &lt;&gt; b) &gt;<a>= (a</a><a>&lt;</a> (b &gt;&lt; c)
--   </pre>
--   
--   A non-unital right semiring (sometimes referred to as a bimonoid) is a
--   pre-semiring with a <a>mempty</a> element that is neutral with respect
--   to both addition and multiplication.
--   
--   A unital right semiring is a pre-semiring with two distinct neutral
--   elements, <a>mempty</a> and <a>unit</a>, such that <a>mempty</a> is
--   right-neutral wrt addition, <a>unit</a> is right-neutral wrt
--   multiplication, and <a>mempty</a> is right-annihilative wrt
--   multiplication.
--   
--   Note that <a>unit</a> needn't be distinct from <a>mempty</a>.
--   
--   Instances also need not be commutative nor left-distributive.
--   
--   See the properties module for a detailed specification of the laws.
class Semigroup r => Semiring r
(><) :: Semiring r => r -> r -> r
fromBoolean :: (Semiring r, Monoid r) => Bool -> r
unit :: (Monoid r, Semiring r) => r
fromBooleanDef :: (Monoid r, Semiring r) => r -> Bool -> r

-- | Fold over a collection using the multiplicative operation of a
--   semiring.
--   
--   <pre>
--   <a>product</a> f ≡ <a>foldr'</a> ((&gt;&lt;) . f) <a>unit</a>
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; (foldMap . product) id [[1, 2], [3, (4 :: Int)]] -- 1 &gt;&lt; 2 &lt;&gt; 3 &gt;&lt; 4
--   14
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; (product . foldMap) id [[1, 2], [3, (4 :: Int)]] -- 1 &lt;&gt; 2 &gt;&lt; 3 &lt;&gt; 4
--   21
--   </pre>
--   
--   For semirings without a distinct multiplicative unit this is
--   equivalent to <tt>const mempty</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; product Just [1..(5 :: Int)]
--   Just 0
--   </pre>
--   
--   In this situation you most likely want to use <a>product1</a>.
product :: (Foldable t, Monoid r, Semiring r) => (a -> r) -> t a -> r

-- | Fold over a non-empty collection using the multiplicative operation of
--   a semiring.
--   
--   As the collection is non-empty this does not require a distinct
--   multiplicative unit:
--   
--   <pre>
--   &gt;&gt;&gt; product1 Just $ 1 :| [2..(5 :: Int)]
--   Just 120
--   </pre>
product1 :: (Foldable1 t, Semiring r) => (a -> r) -> t a -> r

-- | Cross-multiply two collections.
--   
--   <pre>
--   &gt;&gt;&gt; cross [1,2,3 ::Int] [1,2,3]
--   36
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; cross [1,2,3 ::Int] []
--   0
--   </pre>
cross :: (Foldable t, Applicative t, Monoid r, Semiring r) => t r -> t r -> r
cross1 :: (Foldable1 t, Apply t, Semiring r) => t r -> t r -> r

-- | Fold with no additive or multiplicative unit.
foldPresemiring :: Semiring r => (a -> r) -> NonEmpty (NonEmpty a) -> r

-- | Fold with no multiplicative unit.
foldNonunital :: (Monoid r, Semiring r) => (a -> r) -> [NonEmpty a] -> r

-- | Fold with additive &amp; multiplicative units.
--   
--   This function will zero out if there is no multiplicative unit.
foldUnital :: (Monoid r, Semiring r) => (a -> r) -> [[a]] -> r

-- | A generalization of <a>replicate</a> to an arbitrary <a>Monoid</a>.
--   
--   Adapted from
--   <a>http://augustss.blogspot.com/2008/07/lost-and-found-if-i-write-108-in.html</a>.
replicate :: Monoid r => Natural -> r -> r
replicate' :: (Monoid r, Semiring r) => Natural -> r -> r
(^) :: (Monoid r, Semiring r) => r -> Natural -> r
infixr 8 ^
powers :: (Monoid r, Semiring r) => Natural -> r -> r

-- | Monoid under <a>&gt;&lt;</a>. Analogous to <a>Product</a>, but uses
--   the <a>Semiring</a> constraint, rather than <a>Num</a>.
newtype Prod a
Prod :: a -> Prod a
[getProd] :: Prod a -> a
instance GHC.Base.Functor Data.Semiring.Prod
instance GHC.Generics.Generic1 Data.Semiring.Prod
instance GHC.Generics.Generic (Data.Semiring.Prod a)
instance GHC.Enum.Bounded a => GHC.Enum.Bounded (Data.Semiring.Prod a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Semiring.Prod a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Semiring.Prod a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.Prod a)
instance GHC.Base.Applicative Data.Semiring.Prod
instance Data.Semiring.Semiring a => GHC.Base.Semigroup (Data.Semiring.Prod a)
instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => GHC.Base.Monoid (Data.Semiring.Prod a)
instance GHC.Base.Semigroup a => Data.Semiring.Semiring (Data.Semigroup.First a)
instance GHC.Base.Semigroup a => Data.Semiring.Semiring (Data.Semigroup.Last a)
instance GHC.Classes.Ord a => Data.Semiring.Semiring (Data.Semigroup.Max a)
instance GHC.Classes.Ord a => Data.Semiring.Semiring (Data.Semigroup.Min a)
instance GHC.Base.Semigroup a => Data.Semiring.Semiring (Data.Either.Either e a)
instance GHC.Base.Semigroup a => Data.Semiring.Semiring (GHC.Base.NonEmpty a)
instance Data.Semiring.Semiring ()
instance Data.Semiring.Semiring GHC.Types.Ordering
instance Data.Semiring.Semiring GHC.Types.Bool
instance Data.Semiring.Semiring GHC.Natural.Natural
instance Data.Semiring.Semiring GHC.Types.Int
instance Data.Semiring.Semiring GHC.Types.Word
instance (GHC.Base.Monoid b, Data.Semiring.Semiring b) => Data.Semiring.Semiring (a -> b)
instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (Data.Functor.Contravariant.Op a b)
instance (GHC.Base.Monoid a, GHC.Base.Monoid b, Data.Semiring.Semiring a, Data.Semiring.Semiring b) => Data.Semiring.Semiring (a, b)
instance GHC.Base.Monoid a => Data.Semiring.Semiring [a]
instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (GHC.Maybe.Maybe a)
instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (Data.Semigroup.Internal.Dual a)
instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (Data.Functor.Const.Const a b)
instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (Data.Functor.Identity.Identity a)
instance Data.Semiring.Semiring Data.Semigroup.Internal.Any
instance Data.Semiring.Semiring Data.Semigroup.Internal.All
instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (GHC.Types.IO a)
instance Data.Semiring.Semiring (Data.Functor.Contravariant.Predicate a)
instance Data.Semiring.Semiring (Data.Functor.Contravariant.Equivalence a)
instance Data.Semiring.Semiring (Data.Functor.Contravariant.Comparison a)
instance GHC.Classes.Ord a => Data.Semiring.Semiring (Data.Set.Internal.Set a)
instance GHC.Base.Monoid a => Data.Semiring.Semiring (Data.Sequence.Internal.Seq a)
instance (GHC.Classes.Ord k, GHC.Base.Monoid k, GHC.Base.Monoid a) => Data.Semiring.Semiring (Data.Map.Internal.Map k a)
instance GHC.Base.Monoid a => Data.Semiring.Semiring (Data.IntMap.Internal.IntMap a)

module Data.Ring
class (Group a, Semiring a) => Ring a
abs :: Ring a => a -> a
signum :: Ring a => a -> a

module Data.Semiring.Property

-- | &lt;math&gt;
--   
--   A (pre-)semiring with a right-neutral additive unit must satisfy:
--   
--   <pre>
--   <tt>neutral_addition</tt> <a>mempty</a> ~~ const True
--   </pre>
--   
--   Or, equivalently:
--   
--   <pre>
--   <a>mempty</a> <a>&lt;&gt;</a> r ~~ r
--   </pre>
--   
--   This is a required property.
neutral_addition_on :: Semigroup r => Rel r -> r -> r -> Bool
neutral_addition_on' :: Monoid r => Rel r -> r -> Bool

-- | &lt;math&gt;
--   
--   A (pre-)semiring with a right-neutral multiplicative unit must
--   satisfy:
--   
--   <pre>
--   <tt>neutral_multiplication</tt> <a>unit</a> ~~ const True
--   </pre>
--   
--   Or, equivalently:
--   
--   <pre>
--   <a>unit</a> <a>&gt;&lt;</a> r ~~ r
--   </pre>
--   
--   This is a required property.
neutral_multiplication_on :: Semiring r => Rel r -> r -> r -> Bool
neutral_multiplication_on' :: (Monoid r, Semiring r) => Rel r -> r -> Bool

-- | &lt;math&gt;
--   
--   <i>R</i> must right-associate addition.
--   
--   This should be verified by the underlying <a>Semigroup</a> instance,
--   but is included here for completeness.
--   
--   This is a required property.
associative_addition_on :: Semigroup r => Rel r -> r -> r -> r -> Bool

-- | &lt;math&gt;
--   
--   <i>R</i> must right-associate multiplication.
--   
--   This is a required property.
associative_multiplication_on :: Semiring r => Rel r -> r -> r -> r -> Bool

-- | &lt;math&gt;
--   
--   <i>R</i> must right-distribute multiplication.
--   
--   When <i>R</i> is a functor and the semiring structure is derived from
--   <tt>Alternative</tt>, this translates to:
--   
--   <pre>
--   (a <tt>&lt;|&gt;</tt> b) <a>*&gt;</a> c = (a <a>*&gt;</a> c) <tt>&lt;|&gt;</tt> (b <a>*&gt;</a> c)
--   </pre>
--   
--   See
--   <a>https://en.wikibooks.org/wiki/Haskell/Alternative_and_MonadPlus</a>.
--   
--   This is a required property.
distributive_on :: Semiring r => Rel r -> r -> r -> r -> Bool

-- | &lt;math&gt;
--   
--   If <i>R</i> is non-unital (i.e. <i>unit</i> is not distinct from
--   <i>mempty</i>) then it will instead satisfy a right-absorbtion
--   property.
--   
--   This follows from right-neutrality and right-distributivity.
--   
--   Compare <tt>codistributive</tt> and <tt>closed_stable</tt>.
--   
--   When <i>R</i> is also left-distributive we get: &lt;math&gt;
--   
--   See also <a>Warning</a> and
--   <a>https://blogs.ncl.ac.uk/andreymokhov/united-monoids/#whatif</a>.
nonunital_on :: (Monoid r, Semiring r) => Rel r -> r -> r -> Bool

-- | &lt;math&gt;
--   
--   A <i>R</i> is unital then its addititive unit must be
--   right-annihilative, i.e.:
--   
--   <pre>
--   <a>mempty</a> <a>&gt;&lt;</a> a ~~ <a>mempty</a>
--   </pre>
--   
--   For <tt>Alternative</tt> instances this property translates to:
--   
--   <pre>
--   <tt>empty</tt> <a>*&gt;</a> a ~~ <tt>empty</tt>
--   </pre>
--   
--   All right semirings must have a right-absorbative addititive unit,
--   however note that depending on the <tt>Prd</tt> instance this does not
--   preclude IEEE754-mandated behavior such as:
--   
--   <pre>
--   <a>mempty</a> <a>&gt;&lt;</a> NaN ~~ NaN
--   </pre>
--   
--   This is a required property.
annihilative_multiplication_on :: (Monoid r, Semiring r) => Rel r -> r -> Bool

-- | <a>fromBoolean</a> must be a semiring homomorphism into <i>R</i>.
--   
--   This is a required property.
homomorphism_boolean :: forall r. (Eq r, Monoid r, Semiring r) => Bool -> Bool -> Bool

-- | &lt;math&gt;
--   
--   If <i>R</i> is right-cancellative wrt addition then for all <i>a</i>
--   the section <i>(a &lt;&gt;)</i> is injective.
cancellative_addition_on :: Semigroup r => Rel r -> r -> r -> r -> Bool

-- | &lt;math&gt;
--   
--   If <i>R</i> is right-cancellative wrt multiplication then for all
--   <i>a</i> the section <i>(a &gt;&lt;)</i> is injective.
cancellative_multiplication_on :: Semiring r => Rel r -> r -> r -> r -> Bool

-- | &lt;math&gt;
commutative_addition_on :: Semigroup r => Rel r -> r -> r -> Bool

-- | &lt;math&gt;
commutative_multiplication_on :: Semiring r => Rel r -> r -> r -> Bool

-- | &lt;math&gt;
--   
--   <i>R</i> must right-distribute multiplication between finite sums.
--   
--   For types with exact arithmetic this follows from
--   <tt>distributive</tt> &amp; <tt>neutral_multiplication</tt>.
distributive_finite_on :: (Monoid r, Semiring r) => Rel r -> [r] -> r -> Bool

-- | &lt;math&gt;
--   
--   <i>R</i> must right-distribute multiplication over finite (non-empty)
--   sums.
--   
--   For types with exact arithmetic this follows from
--   <tt>distributive</tt> and the universality of <a>fold1</a>.
distributive_finite1_on :: Semiring r => Rel r -> NonEmpty r -> r -> Bool

-- | &lt;math&gt;
--   
--   If <i>R</i> is also left-distributive then it supports
--   cross-multiplication.
distributive_cross_on :: (Monoid r, Semiring r) => Rel r -> [r] -> [r] -> Bool

-- | &lt;math&gt;
--   
--   If <i>R</i> is also left-distributive then it supports (non-empty)
--   cross-multiplication.
distributive_cross1_on :: Semiring r => Rel r -> NonEmpty r -> NonEmpty r -> Bool