-- 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 <> (or mappend), and an
--   identity element, mempty. A semigroup has an appending
--   <> operation, but does not require a mempty
--   element.
--   
--   A Semiring has two appending operations, plus and times,
--   and two respective identity elements, zero and one.
--   
--   More formally, a Semiring R is a set equipped with two binary
--   relations + and *, 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 additive, and the second monoid being referred to as
--   multiplicative, a typical convention when talking about
--   semirings.
--   
--   For any type R with a Num instance, the additive monoid is (R,
--   +, 0) and the multiplicative monoid is (R, *, 1).
--   
--   For Bool, the additive monoid is (Bool, ||,
--   False) and the multiplicative monoid is (Bool,
--   &&, True).
--   
--   Instances should satisfy the following laws:
--   
--   
--   
- additive left identity zero + x =
--   x
--   
- additive right identity x + zero =
--   x
--   
- additive associativity x + (y + z)
--   = (x + y) + z
--   
- additive commutativity x + y = y +
--   x
--   
- multiplicative left identity one *
--   x = x
--   
- multiplicative right identity x *
--   one = x
--   
- multiplicative associativity x * (y
--   * z) = (x * y) * z
--   
- left-distributivity of * over + x
--   * (y + z) = (x * y) + (x *
--   z)
--   
- right-distributivity of * over +
--   (x + y) * z = (x * z) + (y *
--   z)
--   
- annihilation zero * x = x *
--   zero = zero
--   
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 plus.
(+) :: Semiring a => a -> a -> a
infixl 6 +

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- | Wrapper to mimic Map (Sum Int) v, Map
--   (Product Int) 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.
--   
--   
--   negate a + a = zero
--   
class Semiring a => Ring a
negate :: Ring a => a -> a

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

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

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

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

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

-- | Division. Must match its default definition:
--   
--   
--   \x y -> quot x y == fst (quotRem x y)
--   
quot :: Euclidean a => a -> a -> a

-- | Remainder. Must match its default definition:
--   
--   
--   \x y -> rem x y == snd (quotRem x y)
--   
rem :: Euclidean a => a -> a -> a

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

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

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

-- | Division without remainder.
--   
--   
--   \x y -> (x * y) `divide` y == Just x
--   
--   
--   
--   \x y -> maybe True (\z -> x == z * y) (x `divide` y)
--   
divide :: GcdDomain a => a -> a -> Maybe a

-- | Division without remainder.
--   
--   
--   \x y -> (x * y) `divide` y == Just x
--   
--   
--   
--   \x y -> maybe True (\z -> x == z * y) (x `divide` y)
--   
divide :: (GcdDomain a, Eq a, Euclidean a) => a -> a -> Maybe a

-- | Greatest common divisor. Must satisfy
--   
--   
--   \x y -> isJust (x `divide` gcd x y) && isJust (y `divide` gcd x y)
--   
--   
--   
--   \x y z -> isJust (gcd (x * z) (y * z) `divide` z)
--   
gcd :: GcdDomain a => a -> a -> a

-- | Greatest common divisor. Must satisfy
--   
--   
--   \x y -> isJust (x `divide` gcd x y) && isJust (y `divide` gcd x y)
--   
--   
--   
--   \x y z -> isJust (gcd (x * z) (y * z) `divide` z)
--   
gcd :: (GcdDomain a, Eq a, Euclidean a) => a -> a -> a

-- | Lowest common multiple. Must satisfy
--   
--   
--   \x y -> isJust (lcm x y `divide` x) && isJust (lcm x y `divide` y)
--   
--   
--   
--   \x y z -> isNothing (z `divide` x) || isNothing (z `divide` y) || isJust (z `divide` lcm x y)
--   
lcm :: GcdDomain a => a -> a -> a

-- | Lowest common multiple. Must satisfy
--   
--   
--   \x y -> isJust (lcm x y `divide` x) && isJust (lcm x y `divide` y)
--   
--   
--   
--   \x y z -> isNothing (z `divide` x) || isNothing (z `divide` y) || isJust (z `divide` lcm x y)
--   
lcm :: (GcdDomain a, Eq a) => a -> a -> a

-- | Test whether two arguments are coprime. Must match its default
--   definition:
--   
--   
--   \x y -> coprime x y == isJust (1 `divide` gcd x y)
--   
coprime :: GcdDomain a => a -> a -> Bool

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

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

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

-- | Execute the extended Euclidean algorithm. For elements a and
--   b, compute their greatest common divisor g and the
--   coefficient s satisfying as + bt = g for some
--   t.
gcdExt :: (Eq a, Euclidean a, Ring a) => a -> a -> (a, a)
instance GHC.Bits.Bits a => GHC.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 Field is a Ring in which all nonzero elements have a
--   multiplicative inverse.
module Data.Field

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

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

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

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

-- | Infix shorthand for divide.
(/) :: 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 Semiring class, used to implement plus,
--   times, zero, and one for product-like types
--   implementing Generic.
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 Semiring zero for any
--   product-like type implementing Generic.
--   
--   It is only defined for product types.
--   
--   
--   gplus gzero a = a = gplus a gzero
--   
gzero :: (Generic a, GSemiring (Rep a)) => a

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

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

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

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

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

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

-- | An Identity-style wrapper with a Generic 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 Star semiring adds one operation, star to a
--   Semiring, such that it follows the law:
--   
--   
--   star x = one + x * star x = one + star x * x
--   
--   
--   Another operation, aplus, can be defined in terms of
--   star:
--   
--   
--   aplus x = x * star x
--   
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
--   zero element, so that the following hold:
--   
--   
--   plus Infinity y = y
--   plus x Infinity = x
--   
--   
--   i.e., In the max-plus tropical semiring (where plus is
--   max), Infinity 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 plus is min),
--   Infinity unifies with the typical interpretation of positive
--   infinity, and thus it is the identity for the minimum.
module Data.Semiring.Tropical

-- | The tropical semiring.
--   
--   Tropical 'Minima a is equivalent to the
--   semiring <math>, where <math> and <math>.
--   
--   Tropical 'Maxima a is equivalent to the
--   semiring <math>, where <math> and <math>.
--   
--   In literature, the Semiring instance of the Tropical
--   semiring lifts the underlying semiring's additive structure. One might
--   ask why this lifting doesn't instead witness a Monoid, since we
--   only lift zero and plus - the reason is that usually the
--   additive structure of a semiring is monotonic, i.e. a +
--   (min b c) == min (a + b) (a + c), but
--   in general this is not true. For example, lifting Product
--   Word into Tropical is lawful, but Product
--   Int is not, lacking distributivity: (-1) *
--   (min 0 1) /= min ((-1) * 0) ((-1) *
--   1). So, we deviate from literature and instead witness the
--   lifting of a Monoid, so the user must take care to ensure that
--   their implementation of mappend 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 Extremum typeclass exists for us to match on the kind-level
--   Extrema, so that we can recover which ordering to use in the
--   Semiring instance for Tropical.
class Extremum (e :: Extrema)
extremum :: Extremum e => EProxy e -> Extrema

-- | On older GHCs, Proxy is not polykinded, so we provide our own
--   proxy type for Extrema. This turns out not to be a problem,
--   since Extremum 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
