Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
See the connections package for idempotent & selective semirings, and lattices.
Synopsis
- nonunital_on :: Presemiring r => Rel r b -> r -> r -> b
- morphism_presemiring :: Eq s => Presemiring r => Presemiring s => (r -> s) -> r -> r -> r -> Bool
- associative_addition_on :: (Additive - Semigroup) r => Rel r b -> r -> r -> r -> b
- commutative_addition_on :: (Additive - Semigroup) r => Rel r b -> r -> r -> b
- associative_multiplication_on :: (Multiplicative - Semigroup) r => Rel r b -> r -> r -> r -> b
- distributive_on :: Presemiring r => Rel r b -> r -> r -> r -> b
- distributive_finite1_on :: Presemiring r => Foldable1 f => Rel r b -> f r -> r -> b
- morphism_additive_on :: (Additive - Semigroup) r => (Additive - Semigroup) s => Rel s b -> (r -> s) -> r -> r -> b
- morphism_multiplicative_on :: (Multiplicative - Semigroup) r => (Multiplicative - Semigroup) s => Rel s b -> (r -> s) -> r -> r -> b
- morphism_distribitive_on :: Presemiring r => Presemiring s => Rel s b -> (r -> s) -> r -> r -> r -> b
- neutral_addition_on :: (Additive - Monoid) r => Rel r b -> r -> b
- neutral_multiplication_on :: (Multiplicative - Monoid) r => Rel r b -> r -> b
- annihilative_multiplication_on :: Semiring r => Rel r b -> r -> b
- distributive_finite_on :: Semiring r => Foldable f => Rel r b -> f r -> r -> b
- morphism_additive_on' :: (Additive - Monoid) r => (Additive - Monoid) s => Rel s b -> (r -> s) -> b
- morphism_multiplicative_on' :: (Multiplicative - Monoid) r => (Multiplicative - Monoid) s => Rel s b -> (r -> s) -> b
- morphism_semiring :: Eq s => Semiring r => Semiring s => (r -> s) -> r -> r -> r -> Bool
- distributive_xmult_on :: Semiring r => Applicative f => Foldable f => Rel r b -> f r -> f r -> b
- distributive_xmult1_on :: Presemiring r => Apply f => Foldable1 f => Rel r b -> f r -> f r -> b
- commutative_multiplication_on :: (Multiplicative - Semigroup) r => Rel r b -> r -> r -> b
- cancellative_addition_on :: (Additive - Semigroup) r => Rel r Bool -> r -> r -> r -> Bool
- cancellative_multiplication_on :: (Multiplicative - Semigroup) r => Rel r Bool -> r -> r -> r -> Bool
- idempotent_addition_on :: (Additive - Semigroup) r => Rel r b -> r -> b
- idempotent_multiplication_on :: (Multiplicative - Semigroup) r => Rel r b -> r -> b
Required properties of pre-semirings
nonunital_on :: Presemiring r => Rel r b -> r -> r -> b Source #
\( \forall a, b \in R: a * b \sim a * b + b \)
If R is non-unital (i.e. one is not distinct from zero) then it will instead satisfy a right-absorbtion property.
This follows from right-neutrality and right-distributivity.
When R is also left-distributive we get: \( \forall a, b \in R: a * b = a + a * b + b \)
See also Warning
and https://blogs.ncl.ac.uk/andreymokhov/united-monoids/#whatif.
morphism_presemiring :: Eq s => Presemiring r => Presemiring s => (r -> s) -> r -> r -> r -> Bool Source #
Presemiring morphisms are distributive semigroup morphisms.
This is a required property for presemiring morphisms.
associative_addition_on :: (Additive - Semigroup) r => Rel r b -> r -> r -> r -> b Source #
\( \forall a, b, c \in R: (a + b) + c \sim a + (b + c) \)
A semigroup must right-associate addition.
This is a required property for semigroups.
commutative_addition_on :: (Additive - Semigroup) r => Rel r b -> r -> r -> b Source #
\( \forall a, b \in R: a + b \sim b + a \)
This is a an optional property for semigroups, and a required property for semirings.
associative_multiplication_on :: (Multiplicative - Semigroup) r => Rel r b -> r -> r -> r -> b Source #
\( \forall a, b, c \in R: (a * b) * c \sim a * (b * c) \)
A semigroup must right-associate multiplication.
This is a required property for semigroups.
distributive_on :: Presemiring r => Rel r b -> r -> r -> r -> b Source #
\( \forall a, b, c \in R: (a + b) * c \sim (a * c) + (b * c) \)
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_finite1_on :: Presemiring r => Foldable1 f => Rel r b -> f r -> r -> b Source #
\( \forall M \geq 1; a_1 \dots a_M, b \in R: (\sum_{i=1}^M a_i) * b \sim \sum_{i=1}^M a_i * b \)
R must right-distribute multiplication over finite (non-empty) sums.
For types with exact arithmetic this follows from distributive_on
and the universality of folds.
morphism_additive_on :: (Additive - Semigroup) r => (Additive - Semigroup) s => Rel s b -> (r -> s) -> r -> r -> b Source #
This is a required property for additive semigroup morphisms.
morphism_multiplicative_on :: (Multiplicative - Semigroup) r => (Multiplicative - Semigroup) s => Rel s b -> (r -> s) -> r -> r -> b Source #
This is a required property for multiplicative semigroup morphisms.
morphism_distribitive_on :: Presemiring r => Presemiring s => Rel s b -> (r -> s) -> r -> r -> r -> b Source #
\( \forall a, b, c \in R: f ((a + b) * c) \sim f (a * c) + f (b * c) \)
Presemiring morphisms must be compatible with right-distribution.
Required properties of semirings
neutral_multiplication_on :: (Multiplicative - Monoid) r => Rel r b -> r -> b Source #
annihilative_multiplication_on :: Semiring r => Rel r b -> r -> b Source #
distributive_finite_on :: Semiring r => Foldable f => Rel r b -> f r -> r -> b Source #
\( \forall M \geq 0; a_1 \dots a_M, b \in R: (\sum_{i=1}^M a_i) * b \sim \sum_{i=1}^M a_i * b \)
R must right-distribute multiplication between finite sums.
For types with exact arithmetic this follows from distributive_on
& neutral_multiplication_on
.
morphism_additive_on' :: (Additive - Monoid) r => (Additive - Monoid) s => Rel s b -> (r -> s) -> b Source #
This is a required property for additive monoid morphisms.
morphism_multiplicative_on' :: (Multiplicative - Monoid) r => (Multiplicative - Monoid) s => Rel s b -> (r -> s) -> b Source #
This is a required property for multiplicative monoid morphisms.
morphism_semiring :: Eq s => Semiring r => Semiring s => (r -> s) -> r -> r -> r -> Bool Source #
Semiring morphisms are monoidal presemiring morphisms.
This is a required property for semiring morphisms.
Left-distributive presemirings and semirings
distributive_xmult_on :: Semiring r => Applicative f => Foldable f => Rel r b -> f r -> f r -> b Source #
\( \forall M,N \geq 0; a_1 \dots a_M, b_1 \dots b_N \in R: (\sum_{i=1}^M a_i) * (\sum_{j=1}^N b_j) \sim \sum_{i=1 j=1}^{i=M j=N} a_i * b_j \)
If R is also left-distributive then it supports xmult-multiplication.
distributive_xmult1_on :: Presemiring r => Apply f => Foldable1 f => Rel r b -> f r -> f r -> b Source #
\( \forall M,N \geq 1; a_1 \dots a_M, b_1 \dots b_N \in R: (\sum_{i=1}^M a_i) * (\sum_{j=1}^N b_j) = \sum_{i=1 j=1}^{i=M j=N} a_i * b_j \)
If R is also left-distributive then it supports (non-empty) xmult-multiplication.
Commutative presemirings & semirings
commutative_multiplication_on :: (Multiplicative - Semigroup) r => Rel r b -> r -> r -> b Source #
\( \forall a, b \in R: a * b \sim b * a \)
This is a an optional property for semigroups, and a optional property for semirings and rings.
Cancellative presemirings & semirings
cancellative_addition_on :: (Additive - Semigroup) r => Rel r Bool -> r -> r -> r -> Bool Source #
\( \forall a, b, c \in R: b + a \sim c + a \Rightarrow b = c \)
If R is right-cancellative wrt addition then for all a the section (a +) is injective.
cancellative_multiplication_on :: (Multiplicative - Semigroup) r => Rel r Bool -> r -> r -> r -> Bool Source #
\( \forall a, b, c \in R: b * a \sim c * a \Rightarrow b = c \)
If R is right-cancellative wrt multiplication then for all a the section (a *) is injective.
Properties of idempotent semigroups
idempotent_addition_on :: (Additive - Semigroup) r => Rel r b -> r -> b Source #
Idempotency property for additive semigroups.
See https://en.wikipedia.org/wiki/Band_(mathematics).
This is a an optional property for semigroups and semirings.
This is a required property for lattices.
idempotent_multiplication_on :: (Multiplicative - Semigroup) r => Rel r b -> r -> b Source #
Idempotency property for multplicative semigroups.
See https://en.wikipedia.org/wiki/Band_(mathematics).
This is a an optional property for semigroups and semirings.
This is a required property for lattices.