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


-- | 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 7 `times`
infixl 6 `plus`

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


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

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

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

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

-- | 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
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 Data.Bits.Bits a => Data.Bits.Bits (Data.Euclidean.WrappedIntegral a)
instance GHC.Enum.Enum a => GHC.Enum.Enum (Data.Euclidean.WrappedIntegral a)
instance GHC.Real.Real a => GHC.Real.Real (Data.Euclidean.WrappedIntegral a)
instance GHC.Real.Integral a => GHC.Real.Integral (Data.Euclidean.WrappedIntegral a)
instance GHC.Num.Num a => GHC.Num.Num (Data.Euclidean.WrappedIntegral a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Euclidean.WrappedIntegral a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Euclidean.WrappedIntegral a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Euclidean.WrappedIntegral a)
instance GHC.Real.Fractional a => GHC.Real.Fractional (Data.Euclidean.WrappedFractional a)
instance GHC.Num.Num a => GHC.Num.Num (Data.Euclidean.WrappedFractional a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Euclidean.WrappedFractional a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Euclidean.WrappedFractional a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Euclidean.WrappedFractional a)
instance Data.Euclidean.GcdDomain GHC.Types.Int
instance Data.Euclidean.GcdDomain GHC.Int.Int8
instance Data.Euclidean.GcdDomain GHC.Int.Int16
instance Data.Euclidean.GcdDomain GHC.Int.Int32
instance Data.Euclidean.GcdDomain GHC.Int.Int64
instance Data.Euclidean.GcdDomain GHC.Num.Integer.Integer
instance Data.Euclidean.GcdDomain GHC.Types.Word
instance Data.Euclidean.GcdDomain GHC.Word.Word8
instance Data.Euclidean.GcdDomain GHC.Word.Word16
instance Data.Euclidean.GcdDomain GHC.Word.Word32
instance Data.Euclidean.GcdDomain GHC.Word.Word64
instance Data.Euclidean.GcdDomain GHC.Num.Natural.Natural
instance Data.Euclidean.Euclidean GHC.Types.Int
instance Data.Euclidean.Euclidean GHC.Int.Int8
instance Data.Euclidean.Euclidean GHC.Int.Int16
instance Data.Euclidean.Euclidean GHC.Int.Int32
instance Data.Euclidean.Euclidean GHC.Int.Int64
instance Data.Euclidean.Euclidean GHC.Num.Integer.Integer
instance Data.Euclidean.Euclidean GHC.Types.Word
instance Data.Euclidean.Euclidean GHC.Word.Word8
instance Data.Euclidean.Euclidean GHC.Word.Word16
instance Data.Euclidean.Euclidean GHC.Word.Word32
instance Data.Euclidean.Euclidean GHC.Word.Word64
instance Data.Euclidean.Euclidean GHC.Num.Natural.Natural
instance GHC.Num.Num a => Data.Semiring.Semiring (Data.Euclidean.WrappedFractional a)
instance GHC.Num.Num a => Data.Semiring.Ring (Data.Euclidean.WrappedFractional a)
instance GHC.Real.Fractional a => Data.Euclidean.GcdDomain (Data.Euclidean.WrappedFractional a)
instance GHC.Real.Fractional a => Data.Euclidean.Euclidean (Data.Euclidean.WrappedFractional a)
instance GHC.Real.Fractional a => Data.Euclidean.Field (Data.Euclidean.WrappedFractional a)
instance GHC.Num.Num a => Data.Semiring.Semiring (Data.Euclidean.WrappedIntegral a)
instance GHC.Num.Num a => Data.Semiring.Ring (Data.Euclidean.WrappedIntegral a)
instance GHC.Real.Integral a => Data.Euclidean.GcdDomain (Data.Euclidean.WrappedIntegral a)
instance GHC.Real.Integral a => Data.Euclidean.Euclidean (Data.Euclidean.WrappedIntegral a)
instance Data.Euclidean.Field ()
instance Data.Euclidean.Field Data.Semiring.Mod2
instance GHC.Real.Integral a => Data.Euclidean.Field (GHC.Real.Ratio a)
instance Data.Euclidean.Field GHC.Types.Float
instance Data.Euclidean.Field GHC.Types.Double
instance Data.Euclidean.Field Foreign.C.Types.CFloat
instance Data.Euclidean.Field Foreign.C.Types.CDouble
instance Data.Euclidean.Field a => Data.Euclidean.GcdDomain (Data.Complex.Complex a)
instance Data.Euclidean.Field a => Data.Euclidean.Euclidean (Data.Complex.Complex a)
instance Data.Euclidean.Field a => Data.Euclidean.Field (Data.Complex.Complex a)
instance Data.Euclidean.GcdDomain ()
instance Data.Euclidean.Euclidean ()
instance Data.Euclidean.GcdDomain Data.Semiring.Mod2
instance Data.Euclidean.Euclidean Data.Semiring.Mod2
instance GHC.Real.Integral a => Data.Euclidean.GcdDomain (GHC.Real.Ratio a)
instance GHC.Real.Integral a => Data.Euclidean.Euclidean (GHC.Real.Ratio a)
instance Data.Euclidean.GcdDomain GHC.Types.Float
instance Data.Euclidean.Euclidean GHC.Types.Float
instance Data.Euclidean.GcdDomain GHC.Types.Double
instance Data.Euclidean.Euclidean GHC.Types.Double
instance Data.Euclidean.GcdDomain Foreign.C.Types.CFloat
instance Data.Euclidean.Euclidean Foreign.C.Types.CFloat
instance Data.Euclidean.GcdDomain Foreign.C.Types.CDouble
instance Data.Euclidean.Euclidean Foreign.C.Types.CDouble


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


-- | 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
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
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 GHC.Generics.U1
instance (Data.Semiring.Generic.GRing a, Data.Semiring.Generic.GRing b) => Data.Semiring.Generic.GRing (a GHC.Generics.:*: b)
instance Data.Semiring.Generic.GRing a => Data.Semiring.Generic.GRing (GHC.Generics.M1 i c a)
instance Data.Semiring.Ring a => Data.Semiring.Generic.GRing (GHC.Generics.K1 i a)
instance (GHC.Generics.Generic a, Data.Semiring.Generic.GSemiring (GHC.Generics.Rep a)) => Data.Semiring.Semiring (Data.Semiring.Generic.GenericSemiring a)
instance Data.Semiring.Generic.GSemiring GHC.Generics.U1
instance (Data.Semiring.Generic.GSemiring a, Data.Semiring.Generic.GSemiring b) => Data.Semiring.Generic.GSemiring (a GHC.Generics.:*: b)
instance Data.Semiring.Generic.GSemiring a => Data.Semiring.Generic.GSemiring (GHC.Generics.M1 i c a)
instance Data.Semiring.Semiring a => Data.Semiring.Generic.GSemiring (GHC.Generics.K1 i 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.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)


-- | 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 b => Data.Star.Star (a -> b)
instance Data.Star.Star GHC.Types.Bool
instance Data.Star.Star ()
instance Data.Star.Star (Data.Proxy.Proxy a)
instance Data.Star.Star Data.Semiring.Mod2


-- | 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 <a>Tropical</a>.
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 (Data.Typeable.Internal.Typeable e, Data.Data.Data a) => Data.Data.Data (Data.Semiring.Tropical.Tropical e a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Semiring.Tropical.Tropical e a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Semiring.Tropical.Tropical e a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.Tropical.Tropical e a)
instance (GHC.Classes.Ord a, Data.Semiring.Tropical.Extremum e) => GHC.Classes.Ord (Data.Semiring.Tropical.Tropical e a)
instance (GHC.Classes.Ord a, GHC.Base.Monoid a, Data.Semiring.Tropical.Extremum e) => Data.Semiring.Semiring (Data.Semiring.Tropical.Tropical e a)
instance (GHC.Classes.Ord a, GHC.Base.Monoid a, Data.Semiring.Tropical.Extremum e) => Data.Star.Star (Data.Semiring.Tropical.Tropical e a)
instance Data.Semiring.Tropical.Extremum 'Data.Semiring.Tropical.Minima
instance Data.Semiring.Tropical.Extremum 'Data.Semiring.Tropical.Maxima
