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


-- | two monoids as one, in holy haskimony
--   
--   Haskellers are usually familiar with monoids and semigroups. A monoid
--   has an appending operation <a>&lt;&gt;</a> (or <a>mappend</a>), and an
--   identity element, <a>mempty</a>. A semigroup has an appending
--   <a>&lt;&gt;</a> operation, but does not require a <a>mempty</a>
--   element.
--   
--   A Semiring has two appending operations, <a>plus</a> and <a>times</a>,
--   and two respective identity elements, <a>zero</a> and <a>one</a>.
--   
--   More formally, a Semiring R is a set equipped with two binary
--   relations <a>+</a> and <a>*</a>, such that:
--   
--   (R,+) is a commutative monoid with identity element 0,
--   
--   (R,*) is a monoid with identity element 1,
--   
--   (*) left and right distributes over addition, and
--   
--   multiplication by '0' annihilates R.
@package semirings
@version 0.7


-- | A class for semirings (types with two binary operations, one
--   commutative and one associative, and two respective identities), with
--   various general-purpose instances.
module Data.Semiring

-- | The class of semirings (types with two binary operations and two
--   respective identities). One can think of a semiring as two monoids of
--   the same underlying type, with the first being commutative. In the
--   documentation, you will often see the first monoid being referred to
--   as <tt>additive</tt>, and the second monoid being referred to as
--   <tt>multiplicative</tt>, a typical convention when talking about
--   semirings.
--   
--   For any type R with a <a>Num</a> instance, the additive monoid is (R,
--   <a>+</a>, 0) and the multiplicative monoid is (R, <a>*</a>, 1).
--   
--   For <a>Bool</a>, the additive monoid is (<a>Bool</a>, <a>||</a>,
--   <a>False</a>) and the multiplicative monoid is (<a>Bool</a>,
--   <a>&amp;&amp;</a>, <a>True</a>).
--   
--   Instances should satisfy the following laws:
--   
--   <ul>
--   <li><i><i>additive left identity</i></i> <tt><a>zero</a> <a>+</a> x =
--   x</tt></li>
--   <li><i><i>additive right identity</i></i> <tt>x <a>+</a> <a>zero</a> =
--   x</tt></li>
--   <li><i><i>additive associativity</i></i> <tt>x <a>+</a> (y <a>+</a> z)
--   = (x <a>+</a> y) <a>+</a> z</tt></li>
--   <li><i><i>additive commutativity</i></i> <tt>x <a>+</a> y = y <a>+</a>
--   x</tt></li>
--   <li><i><i>multiplicative left identity</i></i> <tt><a>one</a> <a>*</a>
--   x = x</tt></li>
--   <li><i><i>multiplicative right identity</i></i> <tt>x <a>*</a>
--   <a>one</a> = x</tt></li>
--   <li><i><i>multiplicative associativity</i></i> <tt>x <a>*</a> (y
--   <a>*</a> z) = (x <a>*</a> y) <a>*</a> z</tt></li>
--   <li><i><i>left-distributivity of <a>*</a> over <a>+</a></i></i> <tt>x
--   <a>*</a> (y <a>+</a> z) = (x <a>*</a> y) <a>+</a> (x <a>*</a>
--   z)</tt></li>
--   <li><i><i>right-distributivity of <a>*</a> over <a>+</a></i></i>
--   <tt>(x <a>+</a> y) <a>*</a> z = (x <a>*</a> z) <a>+</a> (y <a>*</a>
--   z)</tt></li>
--   <li><i><i>annihilation</i></i> <tt><a>zero</a> <a>*</a> x = x <a>*</a>
--   <a>zero</a> = <a>zero</a></tt></li>
--   </ul>
class Semiring a
plus :: Semiring a => a -> a -> a
zero :: Semiring a => a
times :: Semiring a => a -> a -> a
one :: Semiring a => a
fromNatural :: Semiring a => Natural -> a
infixl 6 `plus`
infixl 7 `times`

-- | Infix shorthand for <a>plus</a>.
(+) :: Semiring a => a -> a -> a
infixl 6 +

-- | Infix shorthand for <a>times</a>.
(*) :: Semiring a => a -> a -> a
infixl 7 *

-- | Raise a number to a non-negative integral power. If the power is
--   negative, this will call <a>error</a>.
(^) :: (Semiring a, Integral b) => a -> b -> a
infixr 8 ^

-- | Map each element of the structure to a semiring, and combine the
--   results using <a>plus</a>.
foldMapP :: (Foldable t, Semiring s) => (a -> s) -> t a -> s

-- | Map each element of the structure to a semiring, and combine the
--   results using <a>times</a>.
foldMapT :: (Foldable t, Semiring s) => (a -> s) -> t a -> s

-- | The <a>sum</a> function computes the additive sum of the elements in a
--   structure. This function is lazy. For a strict version, see
--   <a>sum'</a>.
sum :: (Foldable t, Semiring a) => t a -> a

-- | The <a>product</a> function computes the product of the elements in a
--   structure. This function is lazy. for a strict version, see
--   <a>product'</a>.
product :: (Foldable t, Semiring a) => t a -> a

-- | The <a>sum'</a> function computes the additive sum of the elements in
--   a structure. This function is strict. For a lazy version, see
--   <a>sum</a>.
sum' :: (Foldable t, Semiring a) => t a -> a

-- | The <a>product'</a> function computes the additive sum of the elements
--   in a structure. This function is strict. For a lazy version, see
--   <a>product</a>.
product' :: (Foldable t, Semiring a) => t a -> a

-- | Is the value <a>zero</a>?
isZero :: (Eq a, Semiring a) => a -> Bool

-- | Is the value <a>one</a>?
isOne :: (Eq a, Semiring a) => a -> Bool

-- | Monoid under <a>plus</a>. Analogous to <a>Sum</a>, but uses the
--   <a>Semiring</a> constraint rather than <a>Num</a>.
newtype Add a
Add :: a -> Add a
[getAdd] :: Add a -> a

-- | Monoid under <a>times</a>. Analogous to <a>Product</a>, but uses the
--   <a>Semiring</a> constraint rather than <a>Num</a>.
newtype Mul a
Mul :: a -> Mul a
[getMul] :: Mul a -> a

-- | Provide Semiring and Ring for an arbitrary <a>Num</a>. It is useful
--   with GHC 8.6+'s DerivingVia extension.
newtype WrappedNum a
WrapNum :: a -> WrappedNum a
[unwrapNum] :: WrappedNum a -> a

-- | <a>Mod2</a> represents the integers mod 2.
--   
--   It is useful in the computing of <a>Zhegalkin polynomials</a>.
newtype Mod2
Mod2 :: Bool -> Mod2
[getMod2] :: Mod2 -> Bool

-- | Wrapper to mimic <a>Set</a> (<a>Sum</a> <a>Int</a>), <a>Set</a>
--   (<a>Product</a> <a>Int</a>), etc., while having a more efficient
--   underlying representation.
newtype IntSetOf a
IntSetOf :: IntSet -> IntSetOf a
[getIntSet] :: IntSetOf a -> IntSet

-- | Wrapper to mimic <a>Map</a> (<a>Sum</a> <a>Int</a>) v, <a>Map</a>
--   (<a>Product</a> <a>Int</a>) v, etc., while having a more efficient
--   underlying representation.
newtype IntMapOf k v
IntMapOf :: IntMap v -> IntMapOf k v
[getIntMap] :: IntMapOf k v -> IntMap v

-- | The class of semirings with an additive inverse.
--   
--   <pre>
--   <a>negate</a> a <a>+</a> a = <a>zero</a>
--   </pre>
class Semiring a => Ring a
negate :: Ring a => a -> a

-- | Convert from integer to ring.
--   
--   When <tt>{-#</tt> <tt>LANGUAGE RebindableSyntax #-}</tt> is enabled,
--   this function is used for desugaring integer literals. This may be
--   used to facilitate transition from <a>Num</a> to <a>Ring</a>: no need
--   to replace 0 and 1 with <a>one</a> and <a>zero</a> or to cast numeric
--   literals.
fromInteger :: Ring a => Integer -> a

-- | Convert from integral to ring.
fromIntegral :: (Integral a, Ring b) => a -> b

-- | Subtract two <a>Ring</a> values. For any type <tt>R</tt> with a
--   <a>Num</a> instance, this is the same as <a>(-)</a>.
--   
--   <pre>
--   x <a>minus</a> y = x <a>+</a> <a>negate</a> y
--   </pre>
minus :: Ring a => a -> a -> a
infixl 6 `minus`

-- | Infix shorthand for <a>minus</a>.
(-) :: Ring a => a -> a -> a
infixl 6 -
instance GHC.Internal.Bits.Bits a => GHC.Internal.Bits.Bits (Data.Semiring.WrappedNum a)
instance GHC.Internal.Enum.Bounded a => GHC.Internal.Enum.Bounded (Data.Semiring.Add a)
instance GHC.Internal.Enum.Bounded Data.Semiring.Mod2
instance GHC.Internal.Enum.Bounded a => GHC.Internal.Enum.Bounded (Data.Semiring.Mul a)
instance GHC.Internal.Enum.Bounded a => GHC.Internal.Enum.Bounded (Data.Semiring.WrappedNum a)
instance GHC.Internal.Enum.Enum a => GHC.Internal.Enum.Enum (Data.Semiring.Add a)
instance GHC.Internal.Enum.Enum Data.Semiring.Mod2
instance GHC.Internal.Enum.Enum a => GHC.Internal.Enum.Enum (Data.Semiring.Mul a)
instance GHC.Internal.Enum.Enum a => GHC.Internal.Enum.Enum (Data.Semiring.WrappedNum a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.Add a)
instance GHC.Classes.Eq v => GHC.Classes.Eq (Data.Semiring.IntMapOf k v)
instance GHC.Classes.Eq (Data.Semiring.IntSetOf a)
instance GHC.Classes.Eq Data.Semiring.Mod2
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.Mul a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.WrappedNum a)
instance GHC.Internal.Data.Foldable.Foldable Data.Semiring.Add
instance GHC.Internal.Data.Foldable.Foldable Data.Semiring.Mul
instance GHC.Internal.Data.Foldable.Foldable Data.Semiring.WrappedNum
instance GHC.Internal.Real.Fractional a => GHC.Internal.Real.Fractional (Data.Semiring.Add a)
instance GHC.Internal.Real.Fractional a => GHC.Internal.Real.Fractional (Data.Semiring.Mul a)
instance GHC.Internal.Real.Fractional a => GHC.Internal.Real.Fractional (Data.Semiring.WrappedNum a)
instance GHC.Internal.Base.Functor Data.Semiring.Add
instance GHC.Internal.Base.Functor Data.Semiring.Mul
instance GHC.Internal.Base.Functor Data.Semiring.WrappedNum
instance GHC.Internal.Generics.Generic1 Data.Semiring.Add
instance GHC.Internal.Generics.Generic1 (Data.Semiring.IntMapOf k)
instance GHC.Internal.Generics.Generic1 Data.Semiring.IntSetOf
instance GHC.Internal.Generics.Generic1 Data.Semiring.Mul
instance GHC.Internal.Generics.Generic1 Data.Semiring.WrappedNum
instance GHC.Internal.Generics.Generic (Data.Semiring.Add a)
instance GHC.Internal.Generics.Generic (Data.Semiring.IntMapOf k v)
instance GHC.Internal.Generics.Generic (Data.Semiring.IntSetOf a)
instance GHC.Internal.Generics.Generic Data.Semiring.Mod2
instance GHC.Internal.Generics.Generic (Data.Semiring.Mul a)
instance GHC.Internal.Generics.Generic (Data.Semiring.WrappedNum a)
instance Data.Semiring.Semiring a => GHC.Internal.Base.Monoid (Data.Semiring.Add a)
instance GHC.Internal.Base.Monoid (Data.Semiring.IntMapOf k v)
instance GHC.Internal.Base.Monoid (Data.Semiring.IntSetOf a)
instance Data.Semiring.Semiring a => GHC.Internal.Base.Monoid (Data.Semiring.Mul a)
instance GHC.Internal.Num.Num a => GHC.Internal.Num.Num (Data.Semiring.Add a)
instance GHC.Internal.Num.Num a => GHC.Internal.Num.Num (Data.Semiring.Mul a)
instance GHC.Internal.Num.Num a => GHC.Internal.Num.Num (Data.Semiring.WrappedNum a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Semiring.Add a)
instance GHC.Classes.Ord v => GHC.Classes.Ord (Data.Semiring.IntMapOf k v)
instance GHC.Classes.Ord (Data.Semiring.IntSetOf a)
instance GHC.Classes.Ord Data.Semiring.Mod2
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Semiring.Mul a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Semiring.WrappedNum a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Semiring.Add a)
instance GHC.Internal.Read.Read v => GHC.Internal.Read.Read (Data.Semiring.IntMapOf k v)
instance GHC.Internal.Read.Read (Data.Semiring.IntSetOf a)
instance GHC.Internal.Read.Read Data.Semiring.Mod2
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Semiring.Mul a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Semiring.WrappedNum a)
instance GHC.Internal.Real.RealFrac a => GHC.Internal.Real.RealFrac (Data.Semiring.Add a)
instance GHC.Internal.Real.RealFrac a => GHC.Internal.Real.RealFrac (Data.Semiring.Mul a)
instance GHC.Internal.Real.RealFrac a => GHC.Internal.Real.RealFrac (Data.Semiring.WrappedNum a)
instance GHC.Internal.Real.Real a => GHC.Internal.Real.Real (Data.Semiring.Add a)
instance GHC.Internal.Real.Real a => GHC.Internal.Real.Real (Data.Semiring.Mul a)
instance GHC.Internal.Real.Real a => GHC.Internal.Real.Real (Data.Semiring.WrappedNum a)
instance (Data.Semiring.Ring a, GHC.Internal.Base.Applicative f) => Data.Semiring.Ring (GHC.Internal.Data.Monoid.Ap f a)
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CCc
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CChar
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CClock
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CDev
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CDouble
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CFloat
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CGid
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CIno
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CInt
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CIntMax
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CIntPtr
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CLLong
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CLong
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CMode
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CNlink
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.COff
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CPid
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CPtrdiff
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CRLim
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CSChar
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CSUSeconds
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CShort
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CSigAtomic
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CSize
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CSpeed
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CSsize
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CTcflag
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CTime
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CUChar
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CUInt
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CUIntMax
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CUIntPtr
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CULLong
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CULong
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CUSeconds
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CUShort
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.CUid
instance Data.Semiring.Ring GHC.Internal.Foreign.C.Types.CWchar
instance Data.Semiring.Ring a => Data.Semiring.Ring (Data.Complex.Complex a)
instance Data.Semiring.Ring a => Data.Semiring.Ring (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Semiring.Ring GHC.Types.Double
instance Data.Semiring.Ring a => Data.Semiring.Ring (GHC.Internal.Data.Ord.Down a)
instance Data.Semiring.Ring a => Data.Semiring.Ring (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semiring.Ring b => Data.Semiring.Ring (a -> b)
instance Data.Semiring.Ring GHC.Internal.System.Posix.Types.Fd
instance Data.Fixed.HasResolution a => Data.Semiring.Ring (Data.Fixed.Fixed a)
instance Data.Semiring.Ring GHC.Types.Float
instance Data.Semiring.Ring a => Data.Semiring.Ring (GHC.Types.IO a)
instance Data.Semiring.Ring a => Data.Semiring.Ring (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Semiring.Ring GHC.Types.Int
instance Data.Semiring.Ring GHC.Internal.Int.Int16
instance Data.Semiring.Ring GHC.Internal.Int.Int32
instance Data.Semiring.Ring GHC.Internal.Int.Int64
instance Data.Semiring.Ring GHC.Internal.Int.Int8
instance Data.Semiring.Ring GHC.Internal.Foreign.Ptr.IntPtr
instance Data.Semiring.Ring GHC.Num.Integer.Integer
instance Data.Semiring.Ring Data.Semiring.Mod2
instance Data.Semiring.Ring a => Data.Semiring.Ring (Data.Functor.Contravariant.Op a b)
instance GHC.Internal.Real.Integral a => Data.Semiring.Ring (GHC.Internal.Real.Ratio a)
instance (Data.Semiring.Ring a, Data.Semiring.Ring b) => Data.Semiring.Ring (a, b)
instance (Data.Semiring.Ring a, Data.Semiring.Ring b, Data.Semiring.Ring c) => Data.Semiring.Ring (a, b, c)
instance (Data.Semiring.Ring a, Data.Semiring.Ring b, Data.Semiring.Ring c, Data.Semiring.Ring d) => Data.Semiring.Ring (a, b, c, d)
instance (Data.Semiring.Ring a, Data.Semiring.Ring b, Data.Semiring.Ring c, Data.Semiring.Ring d, Data.Semiring.Ring e) => Data.Semiring.Ring (a, b, c, d, e)
instance (Data.Semiring.Ring a, Data.Semiring.Ring b, Data.Semiring.Ring c, Data.Semiring.Ring d, Data.Semiring.Ring e, Data.Semiring.Ring f) => Data.Semiring.Ring (a, b, c, d, e, f)
instance (Data.Semiring.Ring a, Data.Semiring.Ring b, Data.Semiring.Ring c, Data.Semiring.Ring d, Data.Semiring.Ring e, Data.Semiring.Ring f, Data.Semiring.Ring g) => Data.Semiring.Ring (a, b, c, d, e, f, g)
instance Data.Semiring.Ring ()
instance Data.Semiring.Ring GHC.Types.Word
instance Data.Semiring.Ring GHC.Internal.Word.Word16
instance Data.Semiring.Ring GHC.Internal.Word.Word32
instance Data.Semiring.Ring GHC.Internal.Word.Word64
instance Data.Semiring.Ring GHC.Internal.Word.Word8
instance Data.Semiring.Ring GHC.Internal.Foreign.Ptr.WordPtr
instance GHC.Internal.Num.Num a => Data.Semiring.Ring (Data.Semiring.WrappedNum a)
instance Data.Semiring.Semiring a => GHC.Internal.Base.Semigroup (Data.Semiring.Add a)
instance Data.Semiring.Semiring a => GHC.Internal.Base.Semigroup (Data.Semiring.Add' a)
instance GHC.Internal.Base.Semigroup (Data.Semiring.IntMapOf k v)
instance GHC.Internal.Base.Semigroup (Data.Semiring.IntSetOf a)
instance Data.Semiring.Semiring a => GHC.Internal.Base.Semigroup (Data.Semiring.Mul a)
instance (Data.Semiring.Semiring a, GHC.Internal.Base.Applicative f) => Data.Semiring.Semiring (GHC.Internal.Data.Monoid.Ap f a)
instance Data.Semiring.Semiring GHC.Types.Bool
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CCc
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CChar
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CClock
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CDev
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CDouble
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CFloat
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CGid
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CIno
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CInt
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CIntMax
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CIntPtr
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CLLong
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CLong
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CMode
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CNlink
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.COff
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CPid
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CPtrdiff
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CRLim
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CSChar
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CSUSeconds
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CShort
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CSigAtomic
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CSize
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CSpeed
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CSsize
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CTcflag
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CTime
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CUChar
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CUInt
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CUIntMax
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CUIntPtr
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CULLong
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CULong
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CUSeconds
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CUShort
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.CUid
instance Data.Semiring.Semiring GHC.Internal.Foreign.C.Types.CWchar
instance Data.Semiring.Ring a => Data.Semiring.Semiring (Data.Complex.Complex a)
instance Data.Semiring.Semiring a => Data.Semiring.Semiring (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Semiring.Semiring GHC.Types.Double
instance Data.Semiring.Semiring a => Data.Semiring.Semiring (GHC.Internal.Data.Ord.Down a)
instance Data.Semiring.Semiring a => Data.Semiring.Semiring (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Semiring.Semiring a => Data.Semiring.Semiring (Data.Functor.Contravariant.Equivalence a)
instance Data.Semiring.Semiring b => Data.Semiring.Semiring (a -> b)
instance Data.Semiring.Semiring GHC.Internal.System.Posix.Types.Fd
instance Data.Fixed.HasResolution a => Data.Semiring.Semiring (Data.Fixed.Fixed a)
instance Data.Semiring.Semiring GHC.Types.Float
instance (GHC.Classes.Eq k, Data.Hashable.Class.Hashable k, GHC.Internal.Base.Monoid k, Data.Semiring.Semiring v) => Data.Semiring.Semiring (Data.HashMap.Internal.HashMap k v)
instance (GHC.Classes.Eq a, Data.Hashable.Class.Hashable a, GHC.Internal.Base.Monoid a) => Data.Semiring.Semiring (Data.HashSet.Internal.HashSet a)
instance Data.Semiring.Semiring a => Data.Semiring.Semiring (GHC.Types.IO a)
instance Data.Semiring.Semiring a => Data.Semiring.Semiring (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Semiring.Semiring GHC.Types.Int
instance Data.Semiring.Semiring GHC.Internal.Int.Int16
instance Data.Semiring.Semiring GHC.Internal.Int.Int32
instance Data.Semiring.Semiring GHC.Internal.Int.Int64
instance Data.Semiring.Semiring GHC.Internal.Int.Int8
instance (GHC.Types.Coercible GHC.Types.Int k, GHC.Internal.Base.Monoid k, Data.Semiring.Semiring v) => Data.Semiring.Semiring (Data.Semiring.IntMapOf k v)
instance Data.Semiring.Semiring GHC.Internal.Foreign.Ptr.IntPtr
instance (GHC.Types.Coercible GHC.Types.Int a, GHC.Internal.Base.Monoid a) => Data.Semiring.Semiring (Data.Semiring.IntSetOf a)
instance Data.Semiring.Semiring GHC.Num.Integer.Integer
instance (GHC.Classes.Ord k, GHC.Internal.Base.Monoid k, Data.Semiring.Semiring v) => Data.Semiring.Semiring (Data.Map.Internal.Map k v)
instance Data.Semiring.Semiring a => Data.Semiring.Semiring (GHC.Internal.Maybe.Maybe a)
instance Data.Semiring.Semiring Data.Semiring.Mod2
instance Data.Semiring.Semiring GHC.Num.Natural.Natural
instance Data.Semiring.Semiring a => Data.Semiring.Semiring (Data.Functor.Contravariant.Op a b)
instance Data.Semiring.Semiring (Data.Functor.Contravariant.Predicate a)
instance Data.Semiring.Semiring (GHC.Internal.Data.Proxy.Proxy a)
instance GHC.Internal.Real.Integral a => Data.Semiring.Semiring (GHC.Internal.Real.Ratio a)
instance (GHC.Classes.Ord a, GHC.Internal.Base.Monoid a) => Data.Semiring.Semiring (Data.Set.Internal.Set a)
instance (Data.Semiring.Semiring a, Data.Semiring.Semiring b) => Data.Semiring.Semiring (a, b)
instance (Data.Semiring.Semiring a, Data.Semiring.Semiring b, Data.Semiring.Semiring c) => Data.Semiring.Semiring (a, b, c)
instance (Data.Semiring.Semiring a, Data.Semiring.Semiring b, Data.Semiring.Semiring c, Data.Semiring.Semiring d) => Data.Semiring.Semiring (a, b, c, d)
instance (Data.Semiring.Semiring a, Data.Semiring.Semiring b, Data.Semiring.Semiring c, Data.Semiring.Semiring d, Data.Semiring.Semiring e) => Data.Semiring.Semiring (a, b, c, d, e)
instance (Data.Semiring.Semiring a, Data.Semiring.Semiring b, Data.Semiring.Semiring c, Data.Semiring.Semiring d, Data.Semiring.Semiring e, Data.Semiring.Semiring f) => Data.Semiring.Semiring (a, b, c, d, e, f)
instance (Data.Semiring.Semiring a, Data.Semiring.Semiring b, Data.Semiring.Semiring c, Data.Semiring.Semiring d, Data.Semiring.Semiring e, Data.Semiring.Semiring f, Data.Semiring.Semiring g) => Data.Semiring.Semiring (a, b, c, d, e, f, g)
instance Data.Semiring.Semiring ()
instance Data.Semiring.Semiring GHC.Types.Word
instance Data.Semiring.Semiring GHC.Internal.Word.Word16
instance Data.Semiring.Semiring GHC.Internal.Word.Word32
instance Data.Semiring.Semiring GHC.Internal.Word.Word64
instance Data.Semiring.Semiring GHC.Internal.Word.Word8
instance Data.Semiring.Semiring GHC.Internal.Foreign.Ptr.WordPtr
instance GHC.Internal.Num.Num a => Data.Semiring.Semiring (Data.Semiring.WrappedNum a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Semiring.Add a)
instance GHC.Internal.Show.Show v => GHC.Internal.Show.Show (Data.Semiring.IntMapOf k v)
instance GHC.Internal.Show.Show (Data.Semiring.IntSetOf a)
instance GHC.Internal.Show.Show Data.Semiring.Mod2
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Semiring.Mul a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Semiring.WrappedNum a)
instance GHC.Internal.Foreign.Storable.Storable a => GHC.Internal.Foreign.Storable.Storable (Data.Semiring.Add a)
instance GHC.Internal.Foreign.Storable.Storable a => GHC.Internal.Foreign.Storable.Storable (Data.Semiring.Mul a)
instance GHC.Internal.Foreign.Storable.Storable a => GHC.Internal.Foreign.Storable.Storable (Data.Semiring.WrappedNum a)
instance GHC.Internal.Data.Traversable.Traversable Data.Semiring.Add
instance GHC.Internal.Data.Traversable.Traversable Data.Semiring.Mul
instance GHC.Internal.Data.Traversable.Traversable Data.Semiring.WrappedNum


-- | An 'ordered ring' is a ring with a total order.
--   
--   <h1>Mathematical pedantry note</h1>
--   
--   Many (if not most) of the instances of the <a>OrderedRing</a> type
--   class are not truly ordered rings in the mathematical sense, as the
--   <a>axioms</a> imply that the underlying set is either a singleton or
--   infinite. Thus, the <a>additional properties</a> of ordered rings do
--   not, in general, hold.
--   
--   We indicate those instances that <i>are</i> 'truly' or
--   'mathematically' ordered rings in their documentation.
module Data.Ring.Ordered

-- | A wrapper to indicate the type is being treated as a <a>modular
--   arithmetic system</a> whose modulus is the type's cardinality.
--   
--   While we cannot guarantee that infinite types won't be wrapped by
--   this, we only provide instances of the relevant type classes for those
--   types we are certain are finite.
newtype Modular a
Modular :: a -> Modular a
[getModular] :: Modular a -> a

-- | The class of rings which also have a total order.
--   
--   Instance should satisfy the following laws:
--   
--   <ul>
--   <li><pre><a>abs</a> <a>zero</a> = <a>zero</a></pre></li>
--   <li><pre><a>abs</a> x = <a>abs</a> (<tt>negate</tt> x)</pre></li>
--   <li><pre>x <a>-</a> <a>abs</a> x = <a>zero</a></pre></li>
--   <li><pre><a>signum</a> <a>zero</a> = <a>zero</a></pre></li>
--   <li>If <tt>x <a>&gt;</a> <a>zero</a></tt>, then <tt><a>signum</a> x =
--   <tt>one</tt></tt></li>
--   <li>If <tt>x <a>&lt;</a> <a>zero</a></tt>, then <tt><a>signum</a> x =
--   <tt>negate</tt> <tt>one</tt></tt></li>
--   </ul>
class (Ring a, Ord a) => OrderedRing a

-- | Compute the absolute value.
abs :: OrderedRing a => a -> a

-- | Determine the 'sign' of a value.
signum :: OrderedRing a => a -> a
instance GHC.Internal.Enum.Bounded a => GHC.Internal.Enum.Bounded (Data.Ring.Ordered.Modular a)
instance GHC.Internal.Data.Data.Data a => GHC.Internal.Data.Data.Data (Data.Ring.Ordered.Modular a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Ring.Ordered.Modular a)
instance GHC.Internal.Generics.Generic (Data.Ring.Ordered.Modular a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Ring.Ordered.Modular a)
instance Data.Ring.Ordered.OrderedRing a => Data.Ring.Ordered.OrderedRing (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Ring.Ordered.OrderedRing a => Data.Ring.Ordered.OrderedRing (GHC.Internal.Data.Ord.Down a)
instance Data.Ring.Ordered.OrderedRing a => Data.Ring.Ordered.OrderedRing (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance Data.Fixed.HasResolution a => Data.Ring.Ordered.OrderedRing (Data.Fixed.Fixed a)
instance Data.Ring.Ordered.OrderedRing a => Data.Ring.Ordered.OrderedRing (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Ring.Ordered.OrderedRing GHC.Types.Int
instance Data.Ring.Ordered.OrderedRing GHC.Internal.Int.Int16
instance Data.Ring.Ordered.OrderedRing GHC.Internal.Int.Int32
instance Data.Ring.Ordered.OrderedRing GHC.Internal.Int.Int64
instance Data.Ring.Ordered.OrderedRing GHC.Internal.Int.Int8
instance Data.Ring.Ordered.OrderedRing GHC.Num.Integer.Integer
instance Data.Ring.Ordered.OrderedRing (Data.Ring.Ordered.Modular GHC.Internal.Word.Word8)
instance Data.Ring.Ordered.OrderedRing (Data.Ring.Ordered.Modular GHC.Internal.Word.Word16)
instance Data.Ring.Ordered.OrderedRing (Data.Ring.Ordered.Modular GHC.Internal.Word.Word32)
instance Data.Ring.Ordered.OrderedRing (Data.Ring.Ordered.Modular GHC.Internal.Word.Word64)
instance Data.Ring.Ordered.OrderedRing (Data.Ring.Ordered.Modular GHC.Types.Word)
instance GHC.Internal.Real.Integral a => Data.Ring.Ordered.OrderedRing (GHC.Internal.Real.Ratio a)
instance Data.Ring.Ordered.OrderedRing ()
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Ring.Ordered.Modular a)
instance Data.Semiring.Ring (Data.Ring.Ordered.Modular GHC.Internal.Word.Word8)
instance Data.Semiring.Ring (Data.Ring.Ordered.Modular GHC.Internal.Word.Word16)
instance Data.Semiring.Ring (Data.Ring.Ordered.Modular GHC.Internal.Word.Word32)
instance Data.Semiring.Ring (Data.Ring.Ordered.Modular GHC.Internal.Word.Word64)
instance Data.Semiring.Ring (Data.Ring.Ordered.Modular GHC.Types.Word)
instance Data.Semiring.Semiring (Data.Ring.Ordered.Modular GHC.Internal.Word.Word8)
instance Data.Semiring.Semiring (Data.Ring.Ordered.Modular GHC.Internal.Word.Word16)
instance Data.Semiring.Semiring (Data.Ring.Ordered.Modular GHC.Internal.Word.Word32)
instance Data.Semiring.Semiring (Data.Ring.Ordered.Modular GHC.Internal.Word.Word64)
instance Data.Semiring.Semiring (Data.Ring.Ordered.Modular GHC.Types.Word)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Ring.Ordered.Modular a)


module Data.Euclidean

-- | Informally speaking, <a>Euclidean</a> is a superclass of
--   <a>Integral</a>, lacking <a>toInteger</a>, which allows to define
--   division with remainder for a wider range of types, e. g., complex
--   integers and polynomials with rational coefficients.
--   
--   <a>Euclidean</a> represents a <a>Euclidean domain</a> endowed by a
--   given Euclidean function <a>degree</a>.
--   
--   No particular rounding behaviour is expected of <a>quotRem</a>. E. g.,
--   it is not guaranteed to truncate towards zero or towards negative
--   infinity (cf. <a>divMod</a>), and remainders are not guaranteed to be
--   non-negative. For a faithful representation of residue classes one can
--   use <a>mod</a> package instead.
class GcdDomain a => Euclidean a

-- | Division with remainder.
--   
--   <pre>
--   \x y -&gt; y == 0 || let (q, r) = x `quotRem` y in x == q * y + r
--   </pre>
quotRem :: Euclidean a => a -> a -> (a, a)

-- | Division. Must match its default definition:
--   
--   <pre>
--   \x y -&gt; quot x y == fst (quotRem x y)
--   </pre>
quot :: Euclidean a => a -> a -> a

-- | Remainder. Must match its default definition:
--   
--   <pre>
--   \x y -&gt; rem x y == snd (quotRem x y)
--   </pre>
rem :: Euclidean a => a -> a -> a

-- | Euclidean (aka degree, valuation, gauge, norm) function on <tt>a</tt>.
--   Usually <tt><a>fromIntegral</a> <a>.</a> <a>abs</a></tt>.
--   
--   <a>degree</a> is rarely used by itself. Its purpose is to provide an
--   evidence of soundness of <a>quotRem</a> by testing the following
--   property:
--   
--   <pre>
--   \x y -&gt; y == 0 || let (q, r) = x `quotRem` y in (r == 0 || degree r &lt; degree y)
--   </pre>
degree :: Euclidean a => a -> Natural
infixl 7 `quot`
infixl 7 `rem`

-- | <a>Field</a> represents a <a>field</a>, a ring with a multiplicative
--   inverse for any non-zero element.
class (Euclidean a, Ring a) => Field a

-- | <a>GcdDomain</a> represents a <a>GCD domain</a>. This is a domain,
--   where GCD can be defined, but which does not necessarily allow a
--   well-behaved division with remainder (as in <a>Euclidean</a> domains).
--   
--   For example, there is no way to define <a>rem</a> over polynomials
--   with integer coefficients such that remainder is always "smaller" than
--   divisor. However, <a>gcd</a> is still definable, just not by means of
--   Euclidean algorithm.
--   
--   All methods of <a>GcdDomain</a> have default implementations in terms
--   of <a>Euclidean</a>. So most of the time it is enough to write:
--   
--   <pre>
--   instance GcdDomain Foo
--   instance Euclidean Foo where
--     quotRem = ...
--     degree  = ...
--   </pre>
class Semiring a => GcdDomain a

-- | Division without remainder.
--   
--   <pre>
--   \x y -&gt; (x * y) `divide` y == Just x
--   </pre>
--   
--   <pre>
--   \x y -&gt; maybe True (\z -&gt; x == z * y) (x `divide` y)
--   </pre>
divide :: GcdDomain a => a -> a -> Maybe a
($dmdivide) :: (GcdDomain a, Eq a, Euclidean a) => a -> a -> Maybe a

-- | Greatest common divisor. Must satisfy
--   
--   <pre>
--   \x y -&gt; isJust (x `divide` gcd x y) &amp;&amp; isJust (y `divide` gcd x y)
--   </pre>
--   
--   <pre>
--   \x y z -&gt; isJust (gcd (x * z) (y * z) `divide` z)
--   </pre>
gcd :: GcdDomain a => a -> a -> a
($dmgcd) :: (GcdDomain a, Eq a, Euclidean a) => a -> a -> a

-- | Lowest common multiple. Must satisfy
--   
--   <pre>
--   \x y -&gt; isJust (lcm x y `divide` x) &amp;&amp; isJust (lcm x y `divide` y)
--   </pre>
--   
--   <pre>
--   \x y z -&gt; isNothing (z `divide` x) || isNothing (z `divide` y) || isJust (z `divide` lcm x y)
--   </pre>
lcm :: GcdDomain a => a -> a -> a
($dmlcm) :: (GcdDomain a, Eq a) => a -> a -> a

-- | Test whether two arguments are <a>coprime</a>. Must match its default
--   definition:
--   
--   <pre>
--   \x y -&gt; coprime x y == isJust (1 `divide` gcd x y)
--   </pre>
coprime :: GcdDomain a => a -> a -> Bool
($dmcoprime) :: GcdDomain a => a -> a -> Bool
infixl 7 `divide`

-- | Wrapper around <a>Integral</a> with <a>GcdDomain</a> and
--   <a>Euclidean</a> instances.
newtype WrappedIntegral a
WrapIntegral :: a -> WrappedIntegral a
[unwrapIntegral] :: WrappedIntegral a -> a

-- | Wrapper around <a>Fractional</a> with trivial <a>GcdDomain</a> and
--   <a>Euclidean</a> instances.
newtype WrappedFractional a
WrapFractional :: a -> WrappedFractional a
[unwrapFractional] :: WrappedFractional a -> a

-- | Execute the extended Euclidean algorithm. For elements <tt>a</tt> and
--   <tt>b</tt>, compute their greatest common divisor <tt>g</tt> and the
--   coefficient <tt>s</tt> satisfying <tt>as + bt = g</tt> for some
--   <tt>t</tt>.
gcdExt :: (Eq a, Euclidean a, Ring a) => a -> a -> (a, a)
instance GHC.Internal.Bits.Bits a => GHC.Internal.Bits.Bits (Data.Euclidean.WrappedIntegral a)
instance GHC.Internal.Enum.Enum a => GHC.Internal.Enum.Enum (Data.Euclidean.WrappedIntegral a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Euclidean.WrappedFractional a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Euclidean.WrappedIntegral a)
instance Data.Euclidean.Euclidean GHC.Internal.Foreign.C.Types.CDouble
instance Data.Euclidean.Euclidean GHC.Internal.Foreign.C.Types.CFloat
instance Data.Euclidean.Field a => Data.Euclidean.Euclidean (Data.Complex.Complex a)
instance Data.Euclidean.Euclidean GHC.Types.Double
instance Data.Euclidean.Euclidean GHC.Types.Float
instance Data.Euclidean.Euclidean GHC.Types.Int
instance Data.Euclidean.Euclidean GHC.Internal.Int.Int16
instance Data.Euclidean.Euclidean GHC.Internal.Int.Int32
instance Data.Euclidean.Euclidean GHC.Internal.Int.Int64
instance Data.Euclidean.Euclidean GHC.Internal.Int.Int8
instance Data.Euclidean.Euclidean GHC.Num.Integer.Integer
instance Data.Euclidean.Euclidean Data.Semiring.Mod2
instance Data.Euclidean.Euclidean GHC.Num.Natural.Natural
instance GHC.Internal.Real.Integral a => Data.Euclidean.Euclidean (GHC.Internal.Real.Ratio a)
instance Data.Euclidean.Euclidean ()
instance Data.Euclidean.Euclidean GHC.Types.Word
instance Data.Euclidean.Euclidean GHC.Internal.Word.Word16
instance Data.Euclidean.Euclidean GHC.Internal.Word.Word32
instance Data.Euclidean.Euclidean GHC.Internal.Word.Word64
instance Data.Euclidean.Euclidean GHC.Internal.Word.Word8
instance GHC.Internal.Real.Fractional a => Data.Euclidean.Euclidean (Data.Euclidean.WrappedFractional a)
instance GHC.Internal.Real.Integral a => Data.Euclidean.Euclidean (Data.Euclidean.WrappedIntegral a)
instance Data.Euclidean.Field GHC.Internal.Foreign.C.Types.CDouble
instance Data.Euclidean.Field GHC.Internal.Foreign.C.Types.CFloat
instance Data.Euclidean.Field a => Data.Euclidean.Field (Data.Complex.Complex a)
instance Data.Euclidean.Field GHC.Types.Double
instance Data.Euclidean.Field GHC.Types.Float
instance Data.Euclidean.Field Data.Semiring.Mod2
instance GHC.Internal.Real.Integral a => Data.Euclidean.Field (GHC.Internal.Real.Ratio a)
instance Data.Euclidean.Field ()
instance GHC.Internal.Real.Fractional a => Data.Euclidean.Field (Data.Euclidean.WrappedFractional a)
instance GHC.Internal.Real.Fractional a => GHC.Internal.Real.Fractional (Data.Euclidean.WrappedFractional a)
instance Data.Euclidean.GcdDomain GHC.Internal.Foreign.C.Types.CDouble
instance Data.Euclidean.GcdDomain GHC.Internal.Foreign.C.Types.CFloat
instance Data.Euclidean.Field a => Data.Euclidean.GcdDomain (Data.Complex.Complex a)
instance Data.Euclidean.GcdDomain GHC.Types.Double
instance Data.Euclidean.GcdDomain GHC.Types.Float
instance Data.Euclidean.GcdDomain GHC.Types.Int
instance Data.Euclidean.GcdDomain GHC.Internal.Int.Int16
instance Data.Euclidean.GcdDomain GHC.Internal.Int.Int32
instance Data.Euclidean.GcdDomain GHC.Internal.Int.Int64
instance Data.Euclidean.GcdDomain GHC.Internal.Int.Int8
instance Data.Euclidean.GcdDomain GHC.Num.Integer.Integer
instance Data.Euclidean.GcdDomain Data.Semiring.Mod2
instance Data.Euclidean.GcdDomain GHC.Num.Natural.Natural
instance GHC.Internal.Real.Integral a => Data.Euclidean.GcdDomain (GHC.Internal.Real.Ratio a)
instance Data.Euclidean.GcdDomain ()
instance Data.Euclidean.GcdDomain GHC.Types.Word
instance Data.Euclidean.GcdDomain GHC.Internal.Word.Word16
instance Data.Euclidean.GcdDomain GHC.Internal.Word.Word32
instance Data.Euclidean.GcdDomain GHC.Internal.Word.Word64
instance Data.Euclidean.GcdDomain GHC.Internal.Word.Word8
instance GHC.Internal.Real.Fractional a => Data.Euclidean.GcdDomain (Data.Euclidean.WrappedFractional a)
instance GHC.Internal.Real.Integral a => Data.Euclidean.GcdDomain (Data.Euclidean.WrappedIntegral a)
instance GHC.Internal.Real.Integral a => GHC.Internal.Real.Integral (Data.Euclidean.WrappedIntegral a)
instance GHC.Internal.Num.Num a => GHC.Internal.Num.Num (Data.Euclidean.WrappedFractional a)
instance GHC.Internal.Num.Num a => GHC.Internal.Num.Num (Data.Euclidean.WrappedIntegral a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Euclidean.WrappedFractional a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Euclidean.WrappedIntegral a)
instance GHC.Internal.Real.Real a => GHC.Internal.Real.Real (Data.Euclidean.WrappedIntegral a)
instance GHC.Internal.Num.Num a => Data.Semiring.Ring (Data.Euclidean.WrappedFractional a)
instance GHC.Internal.Num.Num a => Data.Semiring.Ring (Data.Euclidean.WrappedIntegral a)
instance GHC.Internal.Num.Num a => Data.Semiring.Semiring (Data.Euclidean.WrappedFractional a)
instance GHC.Internal.Num.Num a => Data.Semiring.Semiring (Data.Euclidean.WrappedIntegral a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Euclidean.WrappedFractional a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Euclidean.WrappedIntegral a)


-- | A <a>Field</a> is a <a>Ring</a> in which all nonzero elements have a
--   multiplicative inverse.
module Data.Field

-- | <a>Field</a> represents a <a>field</a>, a ring with a multiplicative
--   inverse for any non-zero element.
class (Euclidean a, Ring a) => Field a

-- | Divide two elements of a <a>Field</a>. For any <a>Fractional</a> type,
--   this is the same as <a>(/)</a>.
--   
--   <pre>
--   x <a>divide</a> y = x <a>times</a> <a>recip</a> y
--   </pre>
divide :: Field a => a -> a -> a
infixl 7 `divide`

-- | Convert from rational to field.
--   
--   When <tt>{-#</tt> <tt>LANGUAGE RebindableSyntax #-}</tt> is enabled,
--   this function is used for desugaring rational literals (like,
--   <tt>2.37</tt>). This may be used to facilitate transition from
--   <a>Fractional</a> to <a>Field</a>, because less casts are now
--   required.
fromRational :: Field a => Rational -> a

-- | Invert an element of a <a>Field</a>. For any <a>Fractional</a> type,
--   this is the same as <a>recip</a>.
--   
--   <pre>
--   <a>recip</a> x <a>times</a> x = <a>one</a>
--   </pre>
recip :: Field a => a -> a

-- | Infix shorthand for <a>divide</a>.
(/) :: Field a => a -> a -> a
infixl 7 /


-- | A "directed semiring" refers to the semiring composed of the union of
--   upwards directed sets as multiplication, and intersection of downwards
--   directed sets as addition.
module Data.Semiring.Directed

-- | Wrapper for the semiring of upwards and downwards directed sets.
--   
--   For the individual join/meet monoids associated with either algebra,
--   see <tt><a>Max</a> <a>Ordering</a>, and </tt><a>Min</a>
--   <a>Ordering</a>@.
newtype Directed
Directed :: Ordering -> Directed

[getDirected] :: Directed -> Ordering
instance GHC.Internal.Enum.Bounded Data.Semiring.Directed.Directed
instance GHC.Internal.Data.Data.Data Data.Semiring.Directed.Directed
instance GHC.Internal.Enum.Enum Data.Semiring.Directed.Directed
instance GHC.Classes.Eq Data.Semiring.Directed.Directed
instance GHC.Internal.Generics.Generic Data.Semiring.Directed.Directed
instance GHC.Internal.Read.Read Data.Semiring.Directed.Directed
instance Data.Semiring.Semiring Data.Semiring.Directed.Directed
instance GHC.Internal.Show.Show Data.Semiring.Directed.Directed


-- | This module provides generic deriving tools for semirings and rings
--   for product-like structures.
module Data.Semiring.Generic

-- | Generic <a>Semiring</a> class, used to implement <a>plus</a>,
--   <a>times</a>, <a>zero</a>, and <a>one</a> for product-like types
--   implementing <a>Generic</a>.
class GSemiring (f :: Type -> Type)
gzero' :: GSemiring f => f a
gone' :: GSemiring f => f a
gplus' :: GSemiring f => f a -> f a -> f a
gtimes' :: GSemiring f => f a -> f a -> f a
gfromNatural' :: GSemiring f => Natural -> f a

-- | Generically generate a <a>Semiring</a> <a>zero</a> for any
--   product-like type implementing <a>Generic</a>.
--   
--   It is only defined for product types.
--   
--   <pre>
--   <a>gplus</a> <a>gzero</a> a = a = <a>gplus</a> a <a>gzero</a>
--   </pre>
gzero :: (Generic a, GSemiring (Rep a)) => a

-- | Generically generate a <a>Semiring</a> <a>one</a> for any product-like
--   type implementing <a>Generic</a>.
--   
--   It is only defined for product types.
--   
--   <pre>
--   <a>gtimes</a> <a>gone</a> a = a = <a>gtimes</a> a <a>gone</a>
--   </pre>
gone :: (Generic a, GSemiring (Rep a)) => a

-- | Generically generate a <a>Semiring</a> <a>plus</a> operation for any
--   type implementing <a>Generic</a>. It is only defined for product
--   types.
--   
--   <pre>
--   <a>gplus</a> a b = <a>gplus</a> b a
--   </pre>
gplus :: (Generic a, GSemiring (Rep a)) => a -> a -> a

-- | Generically generate a <a>Semiring</a> <a>times</a> operation for any
--   type implementing <a>Generic</a>. It is only defined for product
--   types.
--   
--   <pre>
--   <a>gtimes</a> a (<a>gtimes</a> b c) = <a>gtimes</a> (<a>gtimes</a> a b) c
--   <a>gtimes</a> a <a>gzero</a> = <a>gzero</a> = <a>gtimes</a> <a>gzero</a> a
--   </pre>
gtimes :: (Generic a, GSemiring (Rep a)) => a -> a -> a

-- | Generically generate a <a>Semiring</a> <a>fromNatural</a> for any
--   product-like type implementing <a>Generic</a>.
--   
--   It is only defined for product types.
gfromNatural :: (Generic a, GSemiring (Rep a)) => Natural -> a

-- | Generic <a>Ring</a> class, used to implement <a>negate</a> for
--   product-like types implementing <a>Generic</a>.
class GRing (f :: Type -> Type)
gnegate' :: GRing f => f a -> f a

-- | Generically generate a <a>Ring</a> <a>negate</a> operation for any
--   type implementing <a>Generic</a>. It is only defined for product
--   types.
--   
--   <pre>
--   <a>gplus</a> a (<a>gnegate</a> a) = <a>zero</a>
--   </pre>
gnegate :: (Generic a, GRing (Rep a)) => a -> a

-- | An Identity-style wrapper with a <a>Generic</a> interface to be used
--   with '-XDerivingVia'.
newtype GenericSemiring a
GenericSemiring :: a -> GenericSemiring a
instance (Data.Semiring.Generic.GRing a, Data.Semiring.Generic.GRing b) => Data.Semiring.Generic.GRing (a GHC.Internal.Generics.:*: b)
instance Data.Semiring.Ring a => Data.Semiring.Generic.GRing (GHC.Internal.Generics.K1 i a)
instance Data.Semiring.Generic.GRing a => Data.Semiring.Generic.GRing (GHC.Internal.Generics.M1 i c a)
instance Data.Semiring.Generic.GRing GHC.Internal.Generics.U1
instance (Data.Semiring.Generic.GSemiring a, Data.Semiring.Generic.GSemiring b) => Data.Semiring.Generic.GSemiring (a GHC.Internal.Generics.:*: b)
instance Data.Semiring.Semiring a => Data.Semiring.Generic.GSemiring (GHC.Internal.Generics.K1 i a)
instance Data.Semiring.Generic.GSemiring a => Data.Semiring.Generic.GSemiring (GHC.Internal.Generics.M1 i c a)
instance Data.Semiring.Generic.GSemiring GHC.Internal.Generics.U1
instance (GHC.Internal.Generics.Generic a, Data.Semiring.Generic.GSemiring (GHC.Internal.Generics.Rep a)) => Data.Semiring.Semiring (Data.Semiring.Generic.GenericSemiring a)


-- | A class for *-semirings (pron. "star-semirings").
module Data.Star

-- | A <a>Star semiring</a> adds one operation, <a>star</a> to a
--   <a>Semiring</a>, such that it follows the law:
--   
--   <pre>
--   <a>star</a> x = <a>one</a> <a>+</a> x <a>*</a> <a>star</a> x = <a>one</a> <a>+</a> <a>star</a> x <a>*</a> x
--   </pre>
--   
--   Another operation, <a>aplus</a>, can be defined in terms of
--   <a>star</a>:
--   
--   <pre>
--   <a>aplus</a> x = x <a>*</a> <a>star</a> x
--   </pre>
class Semiring a => Star a
star :: Star a => a -> a
aplus :: Star a => a -> a
instance Data.Star.Star GHC.Types.Bool
instance Data.Star.Star b => Data.Star.Star (a -> b)
instance Data.Star.Star Data.Semiring.Mod2
instance Data.Star.Star (GHC.Internal.Data.Proxy.Proxy a)
instance Data.Star.Star ()


-- | A tropical semiring is an extension of another totally ordered
--   semiring with the operations of minimum or maximum as addition. The
--   extended semiring is given positive or negative infinity as its
--   <a>zero</a> element, so that the following hold:
--   
--   <pre>
--   <a>plus</a> <a>Infinity</a> y = y
--   <a>plus</a> x <a>Infinity</a> = x
--   </pre>
--   
--   i.e., In the max-plus tropical semiring (where <a>plus</a> is
--   <a>max</a>), <a>Infinity</a> unifies with the typical interpretation
--   of negative infinity, and thus it is the identity for the maximum, and
--   in the min-plus tropical semiring (where <a>plus</a> is <a>min</a>),
--   <a>Infinity</a> unifies with the typical interpretation of positive
--   infinity, and thus it is the identity for the minimum.
module Data.Semiring.Tropical

-- | The tropical semiring.
--   
--   <tt><a>Tropical</a> '<a>Minima</a> a</tt> is equivalent to the
--   semiring &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;.
--   
--   <tt><a>Tropical</a> '<a>Maxima</a> a</tt> is equivalent to the
--   semiring &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;.
--   
--   In literature, the <a>Semiring</a> instance of the <a>Tropical</a>
--   semiring lifts the underlying semiring's additive structure. One might
--   ask why this lifting doesn't instead witness a <a>Monoid</a>, since we
--   only lift <a>zero</a> and <a>plus</a> - the reason is that usually the
--   additive structure of a semiring is monotonic, i.e. <tt>a <a>+</a>
--   (<a>min</a> b c) == <a>min</a> (a <a>+</a> b) (a <a>+</a> c)</tt>, but
--   in general this is not true. For example, lifting <a>Product</a>
--   <a>Word</a> into <a>Tropical</a> is lawful, but <a>Product</a>
--   <a>Int</a> is not, lacking distributivity: <tt>(-1) <a>*</a>
--   (<a>min</a> 0 1) <a>/=</a> <a>min</a> ((-1) <a>*</a> 0) ((-1) <a>*</a>
--   1)</tt>. So, we deviate from literature and instead witness the
--   lifting of a <a>Monoid</a>, so the user must take care to ensure that
--   their implementation of <a>mappend</a> is monotonic.
data Tropical (e :: Extrema) a
Infinity :: Tropical (e :: Extrema) a
Tropical :: a -> Tropical (e :: Extrema) a

-- | A datatype to be used at the kind-level. Its only purpose is to decide
--   the ordering for the tropical semiring in a type-safe way.
data Extrema
Minima :: Extrema
Maxima :: Extrema

-- | The <a>Extremum</a> typeclass exists for us to match on the kind-level
--   <a>Extrema</a>, so that we can recover which ordering to use in the
--   <a>Semiring</a> instance for <tt>Tropical</tt>.
class Extremum (e :: Extrema)
extremum :: Extremum e => EProxy e -> Extrema

-- | On older GHCs, <a>Proxy</a> is not polykinded, so we provide our own
--   proxy type for <a>Extrema</a>. This turns out not to be a problem,
--   since <a>Extremum</a> is a closed typeclass.
data EProxy (e :: Extrema)
EProxy :: EProxy (e :: Extrema)
instance (GHC.Internal.Data.Typeable.Internal.Typeable e, GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Data.Semiring.Tropical.Tropical e a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.Tropical.Tropical e a)
instance Data.Semiring.Tropical.Extremum 'Data.Semiring.Tropical.Maxima
instance Data.Semiring.Tropical.Extremum 'Data.Semiring.Tropical.Minima
instance (GHC.Classes.Ord a, Data.Semiring.Tropical.Extremum e) => GHC.Classes.Ord (Data.Semiring.Tropical.Tropical e a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Semiring.Tropical.Tropical e a)
instance (GHC.Classes.Ord a, GHC.Internal.Base.Monoid a, Data.Semiring.Tropical.Extremum e) => Data.Semiring.Semiring (Data.Semiring.Tropical.Tropical e a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Semiring.Tropical.Tropical e a)
instance (GHC.Classes.Ord a, GHC.Internal.Base.Monoid a, Data.Semiring.Tropical.Extremum e) => Data.Star.Star (Data.Semiring.Tropical.Tropical e a)
