-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Groups, rings, semirings, and dioids. -- -- Lawful algebraic classes and a la carte instances. @package rings @version 0.0.2.2 module Data.Group -- | A Group is a Monoid plus a function, negate, such -- that: -- -- 
--   g << negate g ≡ mempty
--
-- -- 
--   negate g << g ≡ mempty
--
class Monoid g => Group g negate :: Group g => g -> g (<<) :: Group g => g -> g -> g infixl 6 << module Data.Semiring -- | Constraint kind representing a unital semiring. -- -- Used for convenience and to distinguish unital semirings from -- semirings with only an additive unit. type Unital r = (Monoid r, Semiring r) -- | Right pre-semirings and (non-unital and unital) right semirings. -- -- A right pre-semiring (sometimes referred to as a bisemigroup) is a -- type R endowed with two associative binary (i.e. semigroup) -- operations: (<>) and (><), along with a -- right-distributivity property connecting them: -- -- 
--   (a <> b) >< c ≡ (a >< c) <> (b >< c)
--
-- -- A non-unital right semiring (sometimes referred to as a bimonoid) is a -- pre-semiring with a mempty element that is neutral with respect -- to both addition and multiplication. -- -- A unital right semiring is a pre-semiring with two distinct neutral -- elements, mempty and sunit, such that mempty is -- right-neutral wrt addition, sunit is right-neutral wrt -- multiplication, and mempty is right-annihilative wrt -- multiplication. -- -- Note that sunit needn't be distinct from mempty, -- moreover addition and multiplication needn't be commutative or -- left-distributive. -- -- See the properties module for a detailed specification of the laws. class Semigroup r => Semiring r -- | Multiplicative operation. (><) :: Semiring r => r -> r -> r -- | Semiring homomorphism from the Boolean semiring to r. -- -- If this map is injective then r has a distinct multiplicative -- unit. fromBoolean :: (Semiring r, Monoid r) => Bool -> r infixr 7 >< -- | Multiplicative unit of the semiring. sunit :: Unital r => r -- | Default implementation of fromBoolean given a multiplicative -- unit. fromBooleanDef :: Unital r => r -> Bool -> r -- | Fold over a collection using the multiplicative operation of a -- semiring. -- -- 
--   product f ≡ foldr' ((><) . f) sunit
--
-- -- 
--   >>> (foldMap . product) id [[1, 2], [3, (4 :: Int)]] -- 1 >< 2 <> 3 >< 4
--   14
--
-- -- 
--   >>> (product . foldMap) id [[1, 2], [3, (4 :: Int)]] -- 1 <> 2 >< 3 <> 4
--   21
--
-- -- For semirings without a distinct multiplicative sunit this is -- equivalent to const mempty: -- -- 
--   >>> product Just [1..(5 :: Int)]
--   Just 0
--
-- -- In this situation you most likely want to use product1. product :: Foldable t => Unital r => (a -> r) -> t a -> r -- | Fold over a non-empty collection using the multiplicative operation of -- a semiring. -- -- As the collection is non-empty this does not require a distinct -- multiplicative unit: -- -- 
--   >>> product1 Just $ 1 :| [2..(5 :: Int)]
--   Just 120
--
product1 :: Foldable1 t => Semiring r => (a -> r) -> t a -> r -- | Cross-multiply two collections. -- -- 
--   >>> cross [1,2,3 :: Int] [1,2,3]
--   36
--
-- -- 
--   >>> cross [1,2,3 :: Int] []
--   0
--
cross :: Foldable f => Applicative f => Unital r => f r -> f r -> r -- | Cross-multiply two non-empty collections. -- -- 
--   >>> cross1 (Right 2 :| [Left "oops"]) (Right 2 :| [Right 3]) :: Either [Char] Int
--   Right 4
--
cross1 :: Foldable1 f => Apply f => Semiring r => f r -> f r -> r -- | A generalization of replicate to an arbitrary Monoid. -- -- Adapted from -- http://augustss.blogspot.com/2008/07/lost-and-found-if-i-write-108-in.html. replicate :: Monoid r => Natural -> r -> r replicate' :: Unital r => Natural -> r -> r (^) :: Unital r => r -> Natural -> r infixr 8 ^ powers :: Unital r => Natural -> r -> r -- | Infinite closures of a semiring. -- -- Kleene adds a Kleene star operator to a Semiring, -- with an infinite closure property: -- -- 
--   star x ≡ star x >< x <> sunit ≡ x >< star x <> sunit
--
-- -- If r is a dioid then star must be monotonic: -- -- @x <~ y ==> star x <~ star y -- -- See also closed semiring class Semiring a => Kleene a star :: Kleene a => a -> a star :: (Kleene a, Monoid a) => a -> a plus :: Kleene a => a -> a -- | Monoid under ><. Analogous to Product, but uses -- the Semiring constraint, rather than Num. newtype Prod a Prod :: a -> Prod a [getProd] :: Prod a -> a instance GHC.Base.Functor Data.Semiring.Prod instance GHC.Generics.Generic1 Data.Semiring.Prod instance GHC.Generics.Generic (Data.Semiring.Prod a) instance GHC.Enum.Bounded a => GHC.Enum.Bounded (Data.Semiring.Prod a) instance GHC.Show.Show a => GHC.Show.Show (Data.Semiring.Prod a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Semiring.Prod a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.Prod a) instance GHC.Base.Applicative Data.Semiring.Prod instance Data.Semiring.Semiring a => GHC.Base.Semigroup (Data.Semiring.Prod a) instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => GHC.Base.Monoid (Data.Semiring.Prod a) instance Data.Semiring.Kleene () instance (GHC.Base.Monoid b, Data.Semiring.Kleene b) => Data.Semiring.Kleene (a -> b) instance Data.Semiring.Unital b => Data.Semiring.Semiring (a -> b) instance Data.Semiring.Unital a => Data.Semiring.Semiring (Data.Functor.Contravariant.Op a b) instance (Data.Semiring.Unital a, Data.Semiring.Unital b) => Data.Semiring.Semiring (a, b) instance (Data.Semiring.Unital a, Data.Semiring.Unital b, Data.Semiring.Unital c) => Data.Semiring.Semiring (a, b, c) instance GHC.Base.Semigroup a => Data.Semiring.Semiring (Data.Semigroup.First a) instance GHC.Base.Semigroup a => Data.Semiring.Semiring (Data.Semigroup.Last a) instance GHC.Classes.Ord a => Data.Semiring.Semiring (Data.Semigroup.Max a) instance GHC.Classes.Ord a => Data.Semiring.Semiring (Data.Semigroup.Min a) instance GHC.Base.Semigroup a => Data.Semiring.Semiring (Data.Either.Either e a) instance GHC.Base.Semigroup a => Data.Semiring.Semiring (GHC.Base.NonEmpty a) instance Data.Semiring.Semiring () instance Data.Semiring.Semiring GHC.Types.Ordering instance GHC.Base.Monoid a => Data.Semiring.Semiring [a] instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (GHC.Maybe.Maybe a) instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (Data.Semigroup.Internal.Dual a) instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (Data.Functor.Const.Const a b) instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (Data.Functor.Identity.Identity a) instance Data.Semiring.Semiring Data.Semigroup.Internal.Any instance Data.Semiring.Semiring Data.Semigroup.Internal.All instance (GHC.Base.Monoid a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (GHC.Types.IO a) instance Data.Semiring.Semiring (Data.Functor.Contravariant.Predicate a) instance Data.Semiring.Semiring (Data.Functor.Contravariant.Equivalence a) instance GHC.Classes.Ord a => Data.Semiring.Semiring (Data.Set.Internal.Set a) instance GHC.Base.Monoid a => Data.Semiring.Semiring (Data.Sequence.Internal.Seq a) instance (GHC.Classes.Ord k, GHC.Base.Monoid k, GHC.Base.Monoid a) => Data.Semiring.Semiring (Data.Map.Internal.Map k a) instance GHC.Base.Monoid a => Data.Semiring.Semiring (Data.IntMap.Internal.IntMap a) module Data.Ring (<<) :: Group g => g -> g -> g infixl 6 << -- | Multiplicative operation. (><) :: Semiring r => r -> r -> r infixr 7 >< -- | An associative operation. (<>) :: Semigroup a => a -> a -> a infixr 6 <> -- | Absolute value of an element. -- -- 
--   abs r ≡ r >< signum r
--
abs :: (Ring r, Ord r) => r -> r negate :: Group g => g -> g -- | Rings. -- -- A ring R is a commutative group with a second monoidal -- operation >< that distributes over <>. -- -- The basic properties of a ring follow immediately from the axioms: -- -- 
--   r >< mempty ≡ mempty ≡ mempty >< r
--
-- -- 
--   negate sunit >< r ≡ negate r
--
-- -- Furthermore, the binomial formula holds for any commuting pair of -- elements (that is, any a and b such that a >= -- b< a). -- -- If mempty = sunit in a ring R, then R has only -- one element, and is called the zero ring. Otherwise the additive -- identity, the additive inverse of each element, and the multiplicative -- identity are unique. -- -- See https://en.wikipedia.org/wiki/Ring_(mathematics). -- -- If the ring is ordered (i.e. has an Ord instance), then -- the following additional properties must hold: -- -- 
--   a b == a <> c b < c
--
-- -- 
--   mempty a && mempty <= b == mempty a< b
--
-- -- See the properties module for a detailed specification of the laws. class (Group r, Semiring r) => Ring r -- | A ring homomorphism from the integers to r. fromInteger :: Ring r => Integer -> r -- | Absolute value of an element. -- -- 
--   abs r ≡ r >< signum r
--
abs :: (Ring r, Ord r) => r -> r signum :: (Ring r, Ord r) => r -> r module Data.Int.Instance instance GHC.Base.Semigroup GHC.Types.Int instance GHC.Base.Semigroup GHC.Int.Int8 instance GHC.Base.Semigroup GHC.Int.Int16 instance GHC.Base.Semigroup GHC.Int.Int32 instance GHC.Base.Semigroup GHC.Int.Int64 instance GHC.Base.Semigroup GHC.Integer.Type.Integer instance GHC.Base.Monoid GHC.Types.Int instance GHC.Base.Monoid GHC.Int.Int8 instance GHC.Base.Monoid GHC.Int.Int16 instance GHC.Base.Monoid GHC.Int.Int32 instance GHC.Base.Monoid GHC.Int.Int64 instance GHC.Base.Monoid GHC.Integer.Type.Integer instance Data.Group.Group GHC.Types.Int instance Data.Group.Group GHC.Int.Int8 instance Data.Group.Group GHC.Int.Int16 instance Data.Group.Group GHC.Int.Int32 instance Data.Group.Group GHC.Int.Int64 instance Data.Group.Group GHC.Integer.Type.Integer 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.Integer.Type.Integer instance Data.Ring.Ring GHC.Types.Int instance Data.Ring.Ring GHC.Int.Int8 instance Data.Ring.Ring GHC.Int.Int16 instance Data.Ring.Ring GHC.Int.Int32 instance Data.Ring.Ring GHC.Int.Int64 instance Data.Ring.Ring GHC.Integer.Type.Integer module Data.Float.Instance instance GHC.Base.Semigroup GHC.Types.Float instance GHC.Base.Semigroup Foreign.C.Types.CFloat instance GHC.Base.Monoid GHC.Types.Float instance GHC.Base.Monoid Foreign.C.Types.CFloat instance Data.Semiring.Semiring GHC.Types.Float instance Data.Semiring.Semiring Foreign.C.Types.CFloat module Data.Fixed.Instance instance GHC.Base.Semigroup Data.Fixed.Uni instance GHC.Base.Semigroup Data.Fixed.Deci instance GHC.Base.Semigroup Data.Fixed.Centi instance GHC.Base.Semigroup Data.Fixed.Milli instance GHC.Base.Semigroup Data.Fixed.Micro instance GHC.Base.Semigroup Data.Fixed.Nano instance GHC.Base.Semigroup Data.Fixed.Pico instance GHC.Base.Monoid Data.Fixed.Uni instance GHC.Base.Monoid Data.Fixed.Deci instance GHC.Base.Monoid Data.Fixed.Centi instance GHC.Base.Monoid Data.Fixed.Milli instance GHC.Base.Monoid Data.Fixed.Micro instance GHC.Base.Monoid Data.Fixed.Nano instance GHC.Base.Monoid Data.Fixed.Pico instance Data.Group.Group Data.Fixed.Uni instance Data.Group.Group Data.Fixed.Deci instance Data.Group.Group Data.Fixed.Centi instance Data.Group.Group Data.Fixed.Milli instance Data.Group.Group Data.Fixed.Micro instance Data.Group.Group Data.Fixed.Nano instance Data.Group.Group Data.Fixed.Pico instance Data.Semiring.Semiring Data.Fixed.Uni instance Data.Semiring.Semiring Data.Fixed.Deci instance Data.Semiring.Semiring Data.Fixed.Centi instance Data.Semiring.Semiring Data.Fixed.Milli instance Data.Semiring.Semiring Data.Fixed.Micro instance Data.Semiring.Semiring Data.Fixed.Nano instance Data.Semiring.Semiring Data.Fixed.Pico instance Data.Ring.Ring Data.Fixed.Uni instance Data.Ring.Ring Data.Fixed.Deci instance Data.Ring.Ring Data.Fixed.Centi instance Data.Ring.Ring Data.Fixed.Milli instance Data.Ring.Ring Data.Fixed.Micro instance Data.Ring.Ring Data.Fixed.Nano instance Data.Ring.Ring Data.Fixed.Pico module Data.Double.Instance instance GHC.Base.Semigroup GHC.Types.Double instance GHC.Base.Semigroup Foreign.C.Types.CDouble instance GHC.Base.Monoid GHC.Types.Double instance GHC.Base.Monoid Foreign.C.Types.CDouble instance Data.Semiring.Semiring GHC.Types.Double instance Data.Semiring.Semiring Foreign.C.Types.CDouble module Data.Dioid type Topological a = (Dioid a, Kleene a, Yoneda a) -- | Right pre-dioids and dioids. -- -- A right-dioid is a semiring with a right-canonical pre-order relation -- relative to <>: a <~ b iff b ≡ a <> -- c for some c. -- -- In other words we have that: -- -- 
--   a <~ (a <> b) ≡ True
--
-- -- Consequently <~ is both reflexive and transitive: -- -- 
--   a <~ a ≡ True
--   a <~ b && b <~ c ==> a <~ c ≡ True
--
-- -- Finally <~ is an order relation: -- -- 
--   (a =~ b) == (a == b)
--
-- -- See Property class (Prd r, Semiring r) => Dioid r -- | A dioid homomorphism from the naturals to r. fromNatural :: Dioid r => Natural -> r instance (GHC.Base.Monoid a, GHC.Base.Monoid b, Data.Dioid.Dioid a, Data.Dioid.Dioid b) => Data.Dioid.Dioid (a, b) instance (GHC.Base.Monoid a, GHC.Base.Monoid b, GHC.Base.Monoid c, Data.Dioid.Dioid a, Data.Dioid.Dioid b, Data.Dioid.Dioid c) => Data.Dioid.Dioid (a, b, c) module Data.Complex.Instance instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Data.Complex.Complex a) instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Complex.Complex a) instance Data.Group.Group a => Data.Group.Group (Data.Complex.Complex a) instance (Data.Group.Group a, Data.Semiring.Semiring a) => Data.Semiring.Semiring (Data.Complex.Complex a) instance Data.Ring.Ring a => Data.Ring.Ring (Data.Complex.Complex a) module Data.Bool.Instance instance GHC.Base.Semigroup GHC.Types.Bool instance GHC.Base.Monoid GHC.Types.Bool instance Data.Semiring.Semiring GHC.Types.Bool instance Data.Semiring.Kleene GHC.Types.Bool instance Data.Dioid.Dioid GHC.Types.Bool module Data.Semiring.Module -- | Free semimodule over a generating set. -- -- See https://en.wikipedia.org/wiki/Free_module and -- https://en.wikipedia.org/wiki/Semimodule. type Free f = (Foldable1 f, Representable f, Eq (Rep f)) lensRep :: Eq (Rep f) => Representable f => Rep f -> forall g. Functor g => (a -> g a) -> f a -> g (f a) grateRep :: Representable f => forall g. Functor g => (Rep f -> g a -> b) -> g (f a) -> f b -- | The zero vector. fempty :: Monoid a => Representable f => f a -- | Negation of a vector. -- -- 
--   >>> neg (V2 2 4)
--   V2 (-2) (-4)
--
neg :: Group a => Functor f => f a -> f a -- | Sum of two vectors. -- -- 
--   >>> V2 1 2 `sum` V2 3 4
--   V2 4 6
--
-- -- 
--   >>> V2 1 2 <> V2 3 4
--   V2 4 6
--
-- -- 
--   >>> V2 (V2 1 2) (V2 3 4) <> V2 (V2 1 2) (V2 3 4)
--   V2 (V2 2 4) (V2 6 8)
--
sum :: Semigroup a => Representable f => f a -> f a -> f a infixl 6 `sum` -- | Difference between two vectors. -- -- 
--   >>> V2 4 5 `diff` V2 3 1
--   V2 1 4
--
-- -- 
--   >>> V2 4 5 << V2 3 1
--   V2 1 4
--
diff :: Group a => Representable f => f a -> f a -> f a infixl 6 `diff` -- | Outer (tensor) product. outer :: Semiring a => Functor f => Functor g => f a -> g a -> f (g a) -- | Dot product. (<.>) :: Semiring a => Free f => f a -> f a -> a infixl 6 <.> -- | Squared l2 norm of a vector. quadrance :: Semiring a => Free f => f a -> a -- | Squared l2 norm of the difference between two vectors. qd :: Ring a => Free f => f a -> f a -> a -- | Linearly interpolate between two vectors. lerp :: Ring a => Representable f => a -> f a -> f a -> f a -- | Dirac delta function. dirac :: Eq i => Unital a => i -> i -> a -- | Create a unit vector. -- -- 
--   >>> unit I21 :: V2 Int
--   V2 1 0
--
-- -- 
--   >>> unit I42 :: V4 Int
--   V4 0 1 0 0
--
unit :: Unital a => Free f => Rep f -> f a module Data.Semiring.Property -- | <math> -- -- A (pre-)semiring with a right-neutral additive sunit must satisfy: -- -- 
--   neutral_addition mempty ~~ const True
--
-- -- Or, equivalently: -- -- 
--   mempty <> r ~~ r
--
-- -- This is a required property. neutral_addition_on :: Semigroup r => Rel r -> r -> r -> Bool neutral_addition_on' :: Monoid r => Rel r -> r -> Bool -- | <math> -- -- A (pre-)semiring with a right-neutral multiplicative sunit must -- satisfy: -- -- 
--   neutral_multiplication sunit ~~ const True
--
-- -- Or, equivalently: -- -- 
--   sunit >< r ~~ r
--
-- -- This is a required property. neutral_multiplication_on :: Semiring r => Rel r -> r -> r -> Bool neutral_multiplication_on' :: Unital r => Rel r -> r -> Bool -- | <math> -- -- R must right-associate addition. -- -- This should be verified by the underlying Semigroup instance, -- but is included here for completeness. -- -- This is a required property. associative_addition_on :: Semigroup r => Rel r -> r -> r -> r -> Bool -- | <math> -- -- R must right-associate multiplication. -- -- This is a required property. associative_multiplication_on :: Semiring r => Rel r -> r -> r -> r -> Bool -- | <math> -- -- R must right-distribute multiplication. -- -- When R is a functor and the semiring structure is derived from -- Alternative, this translates to: -- -- 
--   (a <|> b) *> c = (a *> c) <|> (b *> c)
--
-- -- See -- https://en.wikibooks.org/wiki/Haskell/Alternative_and_MonadPlus. -- -- This is a required property. distributive_on :: Semiring r => Rel r -> r -> r -> r -> Bool -- | <math> -- -- If R is non-unital (i.e. sunit is not distinct from -- mempty) then it will instead satisfy a right-absorbtion -- property. -- -- This follows from right-neutrality and right-distributivity. -- -- Compare codistributive and closed_stable. -- -- When R is also left-distributive we get: <math> -- -- See also Warning and -- https://blogs.ncl.ac.uk/andreymokhov/united-monoids/#whatif. nonunital_on :: Unital r => Rel r -> r -> r -> Bool -- | <math> -- -- A R is unital then its addititive sunit must be -- right-annihilative, i.e.: -- -- 
--   mempty >< a ~~ mempty
--
-- -- For Alternative instances this property translates to: -- -- 
--   empty *> a ~~ empty
--
-- -- All right semirings must have a right-absorbative addititive sunit, -- however note that depending on the Prd instance this does not -- preclude IEEE754-mandated behavior such as: -- -- 
--   mempty >< NaN ~~ NaN
--
-- -- This is a required property. annihilative_multiplication_on :: Unital r => Rel r -> r -> Bool -- | fromBoolean must be a semiring homomorphism into R. -- -- This is a required property. homomorphism_boolean :: forall r. (Eq r, Unital r) => Bool -> Bool -> Bool -- | <math> -- -- If R is right-cancellative wrt addition then for all a -- the section (a <>) is injective. cancellative_addition_on :: Semigroup r => Rel r -> r -> r -> r -> Bool -- | <math> -- -- If R is right-cancellative wrt multiplication then for all -- a the section (a ><) is injective. cancellative_multiplication_on :: Semiring r => Rel r -> r -> r -> r -> Bool -- | <math> commutative_addition_on :: Semigroup r => Rel r -> r -> r -> Bool -- | <math> commutative_multiplication_on :: Semiring r => Rel r -> r -> r -> Bool -- | <math> -- -- R must right-distribute multiplication between finite sums. -- -- For types with exact arithmetic this follows from -- distributive & neutral_multiplication. distributive_finite_on :: Unital r => Rel r -> [r] -> r -> Bool -- | <math> -- -- R must right-distribute multiplication over finite (non-empty) -- sums. -- -- For types with exact arithmetic this follows from -- distributive and the universality of fold1. distributive_finite1_on :: Semiring r => Rel r -> NonEmpty r -> r -> Bool -- | <math> -- -- If R is also left-distributive then it supports -- cross-multiplication. distributive_cross_on :: Unital r => Rel r -> [r] -> [r] -> Bool -- | <math> -- -- If R is also left-distributive then it supports (non-empty) -- cross-multiplication. distributive_cross1_on :: Semiring r => Rel r -> NonEmpty r -> NonEmpty r -> Bool module Data.Dioid.Property -- | <~ is a preordered relation relative to <>. -- -- This is a required property. ordered_preordered :: Dioid r => r -> r -> Bool -- | mempty is a minimal or least element of r. -- -- This is a required property. ordered_monotone_zero :: (Monoid r, Dioid r) => r -> Bool -- | ( forall a, b, c: b leq c Rightarrow b + a leq c + a -- -- In an ordered semiring this follows directly from the definition of -- <~. -- -- Compare cancellative_addition. -- -- This is a required property. ordered_monotone_addition :: Dioid r => r -> r -> r -> Bool -- | <math> -- -- This is a required property. ordered_positive_addition :: (Prd r, Monoid r) => r -> r -> Bool -- | ( forall a, b, c: b leq c Rightarrow b * a leq c * a -- -- In an ordered semiring this follows directly from -- distributive and the definition of <~. -- -- Compare cancellative_multiplication. -- -- This is a required property. ordered_monotone_multiplication :: Dioid r => r -> r -> r -> Bool -- | <~ is consistent with annihilativity. -- -- This means that a dioid with an annihilative multiplicative sunit must -- satisfy: -- -- 
--   (one <~) ≡ (one ==)
--
ordered_annihilative_sunit :: (Monoid r, Dioid r) => r -> Bool -- | ( forall a, b: a leq b Rightarrow a + b = b ordered_idempotent_addition :: (Prd r, Monoid r) => r -> r -> Bool -- | <math> ordered_positive_multiplication :: (Monoid r, Dioid r) => r -> r -> Bool -- | <math> -- -- Right-additive absorbativity is a generalized form of idempotency: -- -- 
--   absorbative_addition sunit a ~~ a <> a ~~ a
--
absorbative_addition :: (Eq r, Dioid r) => r -> r -> Bool -- | <math> -- -- Left-additive absorbativity is a generalized form of idempotency: -- -- 
--   absorbative_addition sunit a ~~ a <> a ~~ a
--
absorbative_addition' :: (Eq r, Dioid r) => r -> r -> Bool idempotent_addition :: (Eq r, Monoid r, Dioid r) => r -> Bool -- | <math> -- -- Right-mulitplicative absorbativity is a generalized form of -- idempotency: -- -- 
--   absorbative_multiplication mempty a ~~ a >< a ~~ a
--
-- -- See https://en.wikipedia.org/wiki/Absorption_law. absorbative_multiplication :: (Eq r, Dioid r) => r -> r -> Bool -- | <math> -- -- Left-mulitplicative absorbativity is a generalized form of -- idempotency: -- -- 
--   absorbative_multiplication' mempty a ~~ a >< a ~~ a
--
-- -- See https://en.wikipedia.org/wiki/Absorption_law. absorbative_multiplication' :: (Eq r, Dioid r) => r -> r -> Bool -- | <math> -- -- A unital semiring with a right-annihilative muliplicative sunit must -- satisfy: -- -- 
--   sunit <> a ~~ sunit
--
-- -- For a dioid this is equivalent to: -- -- 
--   (sunit <~) ~~ (sunit ~~)
--
-- -- For Alternative instances this is known as the left-catch -- law: -- -- 
--   pure a <|> _ ~~ pure a
--
annihilative_addition :: (Eq r, Monoid r, Dioid r) => r -> Bool -- | <math> -- -- A unital semiring with a left-annihilative muliplicative sunit must -- satisfy: -- -- 
--   a <> sunit ~~ sunit
--
-- -- Note that the left-annihilative property is too strong for many -- instances. This is because it requires that any effects that r -- generates be undsunit. -- -- See https://winterkoninkje.dreamwidth.org/90905.html. annihilative_addition' :: (Eq r, Monoid r, Dioid r) => r -> Bool -- | <math> -- -- A right-codistributive semiring has a right-annihilative muliplicative -- sunit: -- -- 
--   codistributive sunit a mempty ~~ sunit ~~ sunit <> a
--
-- -- idempotent mulitiplication: -- -- 
--   codistributive mempty mempty a ~~ a ~~ a >< a
--
-- -- and idempotent addition: -- -- 
--   codistributive a mempty a ~~ a ~~ a <> a
--
-- -- Furthermore if R is commutative then it is a right-distributive -- lattice. codistributive :: (Eq r, Dioid r) => r -> r -> r -> Bool -- | <math> -- -- If a is p-stable for some p, then we have: -- -- 
--   powers p a ~~ a >< powers p a <> sunit  ~~ powers p a >< a <> sunit 
--
-- -- If <> and >< are idempotent then every -- element is 1-stable: -- -- 
--   a >< a <> a <> sunit = a <> a <> sunit = a <> sunit
--
kleene_pstable :: (Eq r, Prd r, Monoid r, Dioid r) => Natural -> r -> Bool -- | <math> -- -- If a is p-stable for some p, then we have: kleene_paffine :: (Eq r, Monoid r, Dioid r) => Natural -> r -> r -> Bool -- | <math> -- -- Closure is p-stability for all a in the limit as -- <math>. -- -- One way to think of this property is that all geometric series -- "converge": -- -- <math> kleene_stable :: (Eq r, Monoid r, Dioid r, Kleene r) => r -> Bool kleene_affine :: (Eq r, Monoid r, Dioid r, Kleene r) => r -> r -> Bool idempotent_star :: (Eq r, Monoid r, Dioid r, Kleene r) => r -> Bool module Data.Semiring.V2 data V2 a V2 :: !a -> !a -> V2 a data I2 I21 :: I2 I22 :: I2 instance GHC.Show.Show Data.Semiring.V2.I2 instance GHC.Classes.Ord Data.Semiring.V2.I2 instance GHC.Classes.Eq Data.Semiring.V2.I2 instance GHC.Show.Show a => GHC.Show.Show (Data.Semiring.V2.V2 a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Semiring.V2.V2 a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.V2.V2 a) instance Data.Functor.Rep.Representable Data.Semiring.V2.V2 instance Data.Prd.Prd Data.Semiring.V2.I2 instance Data.Prd.Minimal Data.Semiring.V2.I2 instance Data.Prd.Maximal Data.Semiring.V2.I2 instance Data.Prd.Prd a => Data.Prd.Prd (Data.Semiring.V2.V2 a) instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Data.Semiring.V2.V2 a) instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Semiring.V2.V2 a) instance Data.Semiring.Unital a => Data.Semiring.Semiring (Data.Semiring.V2.V2 a) instance (GHC.Base.Monoid a, Data.Dioid.Dioid a) => Data.Dioid.Dioid (Data.Semiring.V2.V2 a) instance Data.Group.Group a => Data.Group.Group (Data.Semiring.V2.V2 a) instance GHC.Base.Functor Data.Semiring.V2.V2 instance Data.Foldable.Foldable Data.Semiring.V2.V2 instance Data.Semigroup.Foldable.Class.Foldable1 Data.Semiring.V2.V2 instance Data.Distributive.Distributive Data.Semiring.V2.V2 module Data.Semiring.V3 data V3 a V3 :: !a -> !a -> !a -> V3 a -- | Cross product. -- -- 
--   >>> V3 1 1 1 <@> V3 (-2) 1 1
--   V3 0 (-3) 3
--
-- -- The cross product satisfies the following properties: -- -- 
--   a <@> a = 0 
--   a <@> b = − ( b <@> a ) , 
--   a <@> ( b + c ) = ( a <@> b ) + ( a <@> c ) , 
--   ( r a ) <@> b = a <@> ( r b ) = r ( a <@> b ) . 
--   a <@> ( b <@> c ) + b <@> ( c <@> a ) + c <@> ( a <@> b ) = 0 . 
--
(<@>) :: Ring a => V3 a -> V3 a -> V3 a infixl 7 <@> -- | Scalar triple product. triple :: Ring a => V3 a -> V3 a -> V3 a -> a data I3 I31 :: I3 I32 :: I3 I33 :: I3 instance GHC.Show.Show Data.Semiring.V3.I3 instance GHC.Classes.Ord Data.Semiring.V3.I3 instance GHC.Classes.Eq Data.Semiring.V3.I3 instance GHC.Show.Show a => GHC.Show.Show (Data.Semiring.V3.V3 a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Semiring.V3.V3 a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.V3.V3 a) instance Data.Functor.Rep.Representable Data.Semiring.V3.V3 instance Data.Prd.Prd Data.Semiring.V3.I3 instance Data.Prd.Minimal Data.Semiring.V3.I3 instance Data.Prd.Maximal Data.Semiring.V3.I3 instance Data.Prd.Prd a => Data.Prd.Prd (Data.Semiring.V3.V3 a) instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Data.Semiring.V3.V3 a) instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Semiring.V3.V3 a) instance Data.Semiring.Unital a => Data.Semiring.Semiring (Data.Semiring.V3.V3 a) instance (GHC.Base.Monoid a, Data.Dioid.Dioid a) => Data.Dioid.Dioid (Data.Semiring.V3.V3 a) instance Data.Group.Group a => Data.Group.Group (Data.Semiring.V3.V3 a) instance GHC.Base.Functor Data.Semiring.V3.V3 instance Data.Foldable.Foldable Data.Semiring.V3.V3 instance Data.Semigroup.Foldable.Class.Foldable1 Data.Semiring.V3.V3 instance Data.Distributive.Distributive Data.Semiring.V3.V3 module Data.Semiring.V4 data V4 a V4 :: !a -> !a -> !a -> !a -> V4 a data I4 I41 :: I4 I42 :: I4 I43 :: I4 I44 :: I4 instance GHC.Show.Show Data.Semiring.V4.I4 instance GHC.Classes.Ord Data.Semiring.V4.I4 instance GHC.Classes.Eq Data.Semiring.V4.I4 instance GHC.Show.Show a => GHC.Show.Show (Data.Semiring.V4.V4 a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Semiring.V4.V4 a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Semiring.V4.V4 a) instance Data.Functor.Rep.Representable Data.Semiring.V4.V4 instance Data.Prd.Prd Data.Semiring.V4.I4 instance Data.Prd.Minimal Data.Semiring.V4.I4 instance Data.Prd.Maximal Data.Semiring.V4.I4 instance Data.Prd.Prd a => Data.Prd.Prd (Data.Semiring.V4.V4 a) instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Data.Semiring.V4.V4 a) instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Semiring.V4.V4 a) instance Data.Semiring.Unital a => Data.Semiring.Semiring (Data.Semiring.V4.V4 a) instance (GHC.Base.Monoid a, Data.Dioid.Dioid a) => Data.Dioid.Dioid (Data.Semiring.V4.V4 a) instance Data.Group.Group a => Data.Group.Group (Data.Semiring.V4.V4 a) instance GHC.Base.Functor Data.Semiring.V4.V4 instance Data.Foldable.Foldable Data.Semiring.V4.V4 instance Data.Semigroup.Foldable.Class.Foldable1 Data.Semiring.V4.V4 instance Data.Distributive.Distributive Data.Semiring.V4.V4 -- | API essentially follows that of linear & hmatrix. module Data.Semiring.Matrix -- | A 2x2 matrix. type M22 a = V2 (V2 a) -- | A 2x3 matrix. type M23 a = V2 (V3 a) -- | A 2x4 matrix. type M24 a = V2 (V4 a) -- | A 3x2 matrix. type M32 a = V3 (V2 a) -- | A 3x3 matrix. type M33 a = V3 (V3 a) -- | A 3x4 matrix. type M34 a = V3 (V4 a) -- | A 4x2 matrix. type M42 a = V4 (V2 a) -- | A 4x3 matrix. type M43 a = V4 (V3 a) -- | A 4x4 matrix. type M44 a = V4 (V4 a) -- | Construct a 2x2 matrix. -- -- Arguments are in row-major order. m22 :: a -> a -> a -> a -> M22 a -- | Construct a 2x3 matrix. -- -- Arguments are in row-major order. m23 :: a -> a -> a -> a -> a -> a -> M23 a -- | Construct a 2x4 matrix. -- -- Arguments are in row-major order. m24 :: a -> a -> a -> a -> a -> a -> a -> a -> M24 a -- | Construct a 3x2 matrix. -- -- Arguments are in row-major order. m32 :: a -> a -> a -> a -> a -> a -> M32 a -- | Construct a 3x3 matrix. -- -- Arguments are in row-major order. m33 :: a -> a -> a -> a -> a -> a -> a -> a -> a -> M33 a -- | Construct a 3x4 matrix. -- -- Arguments are in row-major order. m34 :: a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> M34 a -- | Construct a 4x2 matrix. -- -- Arguments are in row-major order. m42 :: a -> a -> a -> a -> a -> a -> a -> a -> M42 a -- | Construct a 4x3 matrix. -- -- Arguments are in row-major order. m43 :: a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> M43 a -- | Construct a 4x4 matrix. -- -- Arguments are in row-major order. m44 :: a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> M44 a -- | Index into a row of a matrix or vector. -- -- 
--   >>> row I21 (V2 1 2)
--   1
--
row :: Representable f => Rep f -> f c -> c -- | Index into a column of a matrix. -- -- 
--   >>> row I22 . col I31 $ V2 (V3 1 2 3) (V3 4 5 6)
--   4
--
col :: Functor f => Representable g => Rep g -> f (g a) -> f a -- | Scalar-matrix product. -- -- The > arrow points towards the return type. -- -- 
--   >>> 5 .> V2 (V2 1 2) (V2 3 4)
--   V2 (V2 5 10) (V2 15 20)
--
(.>) :: Semiring a => Functor f => Functor g => a -> f (g a) -> f (g a) infixr 7 .> -- | Matrix-scalar product. -- -- The < arrow points towards the return type. -- -- 
--   >>> m22 1 2 3 4 <. 5
--   V2 (V2 5 10) (V2 15 20)
--
-- -- 
--   >>> m22 1 2 3 4 <. 5 <. 2
--   V2 (V2 10 20) (V2 30 40)
--
(<.) :: Semiring a => Functor f => Functor g => f (g a) -> a -> f (g a) infixl 7 <. -- | Multiply a matrix on the right by a column vector. -- -- 
--   >>> m23 1 2 3 4 5 6 #> V3 7 8 9
--   V2 50 122
--
-- -- 
--   >>> m22 1 0 0 0 #> m23 1 2 3 4 5 6 #> V3 7 8 9
--   V2 50 0
--
(#>) :: (Semiring a, Free f, Free g) => f (g a) -> g a -> f a infixr 7 #> -- | Multiply a matrix on the left by a row vector. -- -- 
--   >>> V2 1 2 <# m23 3 4 5 6 7 8
--   V3 15 18 21
--
-- -- 
--   >>> V2 1 2 <# m23 3 4 5 6 7 8 <# m32 1 0 0 0 0 0
--   V2 15 0
--
(<#) :: (Semiring a, Free f, Free g) => f a -> f (g a) -> g a infixl 7 <# -- | Multiply two matrices. -- -- 
--   >>> m22 1 2 3 4 <#> m22 1 2 3 4 :: M22 Int
--   V2 (V2 7 10) (V2 15 22)
--
-- -- 
--   >>> m23 1 2 3 4 5 6 <#> m32 1 2 3 4 4 5 :: M22 Int
--   V2 (V2 19 25) (V2 43 58)
--
(<#>) :: (Semiring a, Free f, Free g, Free h) => f (g a) -> g (h a) -> f (h a) infixr 7 <#> -- | Obtain a diagonal matrix from a vector. -- -- 
--   >>> scale (V2 2 3)
--   V2 (V2 2 0) (V2 0 3)
--
scale :: Monoid a => Free f => f a -> f (f a) -- | Identity matrix. -- -- 
--   >>> identity :: M44 Int
--   V4 (V4 1 0 0 0) (V4 0 1 0 0) (V4 0 0 1 0) (V4 0 0 0 1)
--
-- -- 
--   >>> identity :: V3 (V3 Int)
--   V3 (V3 1 0 0) (V3 0 1 0) (V3 0 0 1)
--
identity :: Unital a => Free f => f (f a) -- | Transpose a matrix. -- -- 
--   transpose (V3 (V2 1 2) (V2 3 4) (V2 5 6))
--
-- -- V2 (V3 1 3 5) (V3 2 4 6) transpose :: Functor f => Distributive g => f (g a) -> g (f a) -- | Compute the trace of a matrix. -- -- 
--   >>> trace (V2 (V2 a b) (V2 c d))
--   a <> d
--
trace :: Semigroup a => Free f => f (f a) -> a -- | Compute the diagonal of a matrix. -- -- 
--   >>> diagonal (V2 (V2 a b) (V2 c d))
--   V2 a d
--
diag :: Representable f => f (f a) -> f a -- | 2x2 matrix bideterminant over a commutative semiring. -- -- 
--   >>> bdet2 $ m22 1 2 3 4
--   (4,6)
--
bdet2 :: Semiring a => M22 a -> (a, a) -- | 2x2 matrix determinant over a commutative ring. -- -- 
--   det2 ≡ uncurry (<<) . bdet2
--
det2 :: Ring a => M22 a -> a -- | 2x2 double-precision matrix determinant. -- -- 
--   >>> det2d $ m22 1 2 3 4
--   -2.0
--
det2d :: M22 Double -> Double -- | 2x2 double-precision matrix inverse. -- -- 
--   >>> inv2d $ m22 1 2 3 4
--   V2 (V2 (-2.0) 1.0) (V2 1.5 (-0.5))
--
inv2d :: M22 Double -> M22 Double -- | 3x3 matrix bideterminant over a commutative semiring. -- -- 
--   >>> bdet3 (V3 (V3 1 2 3) (V3 4 5 6) (V3 7 8 9))
--   (225, 225)
--
bdet3 :: Semiring a => M33 a -> (a, a) -- | 3x3 matrix determinant over a commutative ring. -- -- 
--   det3 ≡ uncurry (<<) . bdet3
--
det3 :: Ring a => M33 a -> a -- | 3x3 double-precision matrix determinant. -- -- This implementation uses a cofactor expansion to avoid loss of -- precision. det3d :: M33 Double -> Double -- | 3x3 double-precision matrix inverse. -- -- 
--   >>> inv3d $ m33 1 2 4 4 2 2 1 1 1
--   V3 (V3 0.0 0.5 (-1.0)) (V3 (-0.5) (-0.75) 3.5) (V3 0.5 0.25 (-1.5))
--
inv3d :: M33 Double -> M33 Double -- | 4x4 matrix bideterminant over a commutative semiring. -- -- 
--   >>> bdet4 (V4 (V4 1 2 3 4) (V4 5 6 7 8) (V4 9 10 11 12) (V4 13 14 15 16))
--   (27728,27728)
--
bdet4 :: Semiring a => M44 a -> (a, a) -- | 4x4 matrix determinant over a commutative ring. -- -- 
--   det4 ≡ uncurry (<<) . bdet4
--
det4 :: Ring a => M44 a -> a -- | 4x4 double-precision matrix determinant. -- -- This implementation uses a cofactor expansion to avoid loss of -- precision. det4d :: M44 Double -> Double -- | 4x4 double-precision matrix inverse. inv4d :: M44 Double -> M44 Double module Data.Word.Instance instance GHC.Base.Semigroup GHC.Types.Word instance GHC.Base.Semigroup GHC.Word.Word8 instance GHC.Base.Semigroup GHC.Word.Word16 instance GHC.Base.Semigroup GHC.Word.Word32 instance GHC.Base.Semigroup GHC.Word.Word64 instance GHC.Base.Semigroup GHC.Natural.Natural instance GHC.Base.Monoid GHC.Types.Word instance GHC.Base.Monoid GHC.Word.Word8 instance GHC.Base.Monoid GHC.Word.Word16 instance GHC.Base.Monoid GHC.Word.Word32 instance GHC.Base.Monoid GHC.Word.Word64 instance GHC.Base.Monoid GHC.Natural.Natural 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.Natural.Natural instance Data.Dioid.Dioid GHC.Word.Word8 instance Data.Dioid.Dioid GHC.Word.Word16 instance Data.Dioid.Dioid GHC.Word.Word32 instance Data.Dioid.Dioid GHC.Word.Word64 instance Data.Dioid.Dioid GHC.Natural.Natural