This library predefines a number of magmas. In some cases, this is just a wrapper around existing behaviour.
Trivial magmas are real and natural numbers. To treat these as magmas, indeed, semirings, say
#include "math/arithmetic_magma.hpp"
This will call an arithmetic magma, and allow operations and querying attributes, for which std::numeric_limits is specialized, except for bool. This is therefore implemented for math::log_float as well.
The cost semiring keeps track of costs that times adds up. plus selects the lowest-cost argument.
The max semiring in a sense is the opposite of the cost semiring: plus prefers the element with the greatest value. The value could, for example, be a probability.
Semiring that is helpful to minimise a cost. It is also known as the “tropical” semiring.
times adds costs; plus and choose pick the lowest-cost argument.
This type supports Boost.Hash, if boost/functional/hash.hpp is included.
Arithmetic type that represents the cost. The type needs to be able to represent infinity, so that the additive identity can be implemented. std::numeric_limits<Type>::has_infinity must be true.
Public Functions
Initialise with infinite cost. This results in the additive identity, also known as “zero”.
Initialise with a cost of value.
Return the underlying value.
Semiring whose plus (and choose) operation picks the maximum of the two values. times performs multiplication on the underlying value.
The underlying value must always be non-negative, so that the additive identity has value 0. The multiplicative identity has value 1.
Division is only implemented for non-integer types.
This type supports Boost.Hash, if boost/functional/hash.hpp is included.
Underlying type that represents the value.
Public Functions
Initialise with 0.
Initialise with value as the value.
Return the underlying value.
The sequence semiring represents a sequence of symbols. Two sequences can be concatenated with times. The longest common prefix (or suffix) can be found with plus. (This seems a strange operation for plus but it is useful when moving symbols around finite-state automata.)
There are common use cases for, for example, empty sequences or single-symbol sequences. To optimise code for these use cases, the semiring consists of five different classes. Any sequence can be represented with an object of type math::sequence. All the other types are convertible to that class. math::empty_sequence always contains an empty sequence. math::single_sequence always contains a sequence of length 1. math::optional_sequence contains a sequence of length 0 or 1. math::empty_sequence and math::single_sequence can always be converted to math::optional_sequence. math::sequence_annihilator is a special symbol indicating the multiplicative annihilator, which is required for a semiring. Operations such as plus, times, and divide return the appropriate type.
The Direction template parameter to each of the types can be left or right. It indicates whether the sequence forms a left or right semiring. The operation plus on two elements of a left sequence semiring returns longest common prefix, the longest symbol sequence that both sequences start with. On a right sequence semiring, the longest common suffix is taken, which is the longest symbol sequence that both sequences end with.
Semiring that contains a sequence of zero or more symbols, or it can be the multiplicative annihilator. All specialised classes can be converted to this one implicitly; the other way around the conversion is explicit, because they may not be possible.
times concatenates two sequences. plus returns the longest common prefix (if Direction is left) or suffix (if Direction is right). divide is only defined from Direction, and then only if the divisor is a prefix (or suffix) of the dividend.
compare implements a strict weak ordering by sorting elements lexicographically from Direction. choose picks the shortest sequence first, and uses lexicographical order from Direction as a tie-breaker. This makes the sequence a semiring with times and choose in both directions, whatever the value of Direction
Sequences support Boost.Hash, if boost/functional/hash.hpp is included. Sequences of different types that compare equal have the same hash value. The details of how the hashes are computed (in what direction, for example) are not defined, and likely to change in future versions.
Public Functions
Initialise with no symbols. (Multiplicative identity.)
Initialise with the empty sequence.
Initialise with a sequence with one element.
Initialise with a sequence with zero or one element.
Initialise as the multiplicative annihilator. (Additive identity.)
Initialise with a range of symbols.
Initialise with a range of symbols. (Optimised version using the move constructor of std::vector.)
Return true iff this is an annihilator.
Return true iff this contains a symbol sequence of zero elements.
Return a range containing the symbols.
Sequence that is known at compile time to be of zero length.
Public Functions
Initialise with a sequence, which must be empty.
If the sequence is non-empty.
Initialise with single_sequence, which is never possible and always throws.
Initialise with optional_sequence, which must be empty.
If the sequence is non-empty.
Initialise with a range of symbols. This range must be empty.
Sequence that is known at compile time to be of length one.
Public Functions
Initialise with an explicit symbol.
Initialise with a range of symbols, which must have one element.
Convert from sequence: explicit.
If the sequence has another length than 1.
Sequence that is known at compile time to be of length zero or one.
Public Functions
Initialise empty.
Initialise with an explicit symbol.
Convert empty, from empty_sequence.
Convert with one symbol, from single_sequence.
Convert from sequence: explicit.
If the sequence is an annihilator or has a greater length.
Initialise with a range of symbols, which must have one element.
Sequence that is known at compile time to be the multiplicative annihilator: Multiplying this with any sequence yields a sequence_annihilator.
Public Functions
Construct from a sequence, which must be an annihilator.
If the argument is not an annihilator.
Composite magmas are built out of other magmas. The product magma is a general magma which applies all operations to each element.
The lexicographical semiring is a semiring for which plus chooses the first in a lexicographical ordering of the components. It is not always necessary to care about the ordering of later components. For example, the first component could be a cost, and the second component a word sequence. This might be useful in finding the lowest-cost word sequence.
Magma that is the Cartesian product of a number of magmas.
If Inverse is with_inverse with an operation, then the inverse of this operation is implemented. In that case, the inverse cannot be defined on that component, and therefore the inverse cannot be defined for the whole product. If any component of this product is an annihilator for that operation, the whole product must therefore be an annihilator. Therefore, with with_inverse <Operation>, is_annihilator returns true if any component returns true for is_annihilator. Since any annihilator should be equal, equal returns true for two products that have any annihilator for that operation.
To produce (as opposed to detect) an annihilator, each of the components must have an annihilator for that operation.
order is not defined for the product: even if an operation implements a strict weak ordering on each component, that does not implement any ordering on the product.
Operations on this product are associative, commutative, idempotent, distributive, and the product is a semiring, if and only if each of the components is.
Products supports Boost.Hash, if boost/functional/hash.hpp is included. If the hash values of the components of two products are the same, then the hash value of the two products will be the same.
The list of components, given as math::over.
(optional) An inverse operation that is allowed, given as math::with_inverse.
The lexicographical semiring. This is a semiring that has multiple components. Operations plus and choose are defined as taking the best in a strict weak ordering. The ordering is defined by lexicographical comparison: if the first components are the same, the second components are compared, et cetera.
Often, the user will not care about the ordering of the later components, but it still needs to be defined to make this a proper semiring. For example, the first component could be of type cost or max_semiring, indicating a cost or probability. The components following it could form the payload, for example, the word sequence. Used on the correct automaton, the right algorithm might yield the lowest-cost or highest-probability word sequence.
All components must be monoids over times, and have choose defined. The first component must be a semiring over times and choose. Each of the other elements must almost be a semiring, but does not have to have a multiplicative annihilator.
The first component is used to indicate the additive identity (and, thus, the multiplicative annihilator), zero(), of the whole semiring. When the first component is zero, the meaning of the whole semiring object is the additive identity, whatever the value of the other components. Any two objects with the first component equal and the additive identity will therefore compare equal. Such objects can, however, have detectably different elements after the first component.
This type is implicitly convertible from another lexicographical semiring if all components are. It is explicitly convertible from if one or more of the components is explicitly convertible (and the rest is implicitly convertible).
This semiring does not have divide. This would require each component to be divided, which is impossible if any is an annihilator. Then, any element of a lexicographical semiring that has any component that is an annihilator would have to be an annihilator itself. This is functionality that could be added, but should not be the default. It is not currently implemented.
lexicographical objects can be constructed explicitly with a list of argument, each of which is pairwise convertible to the component. They can also be constructed from a compatible lexicographical: implicitly if all components are implicitly convertible; and explicitly if some are only explicitly convertible.
It has a member function components() which returns the range with the components in order.
The lexicographical semiring supports Boost.Hash, if boost/functional/hash.hpp is included. If the hash values of the components of two lexicographical semirings are the same, then the hash value of the two semirings will be the same.
Type of the form over<...> with the magmas that should be contained. All the magmas must have an ordered choose. The first of them must be a semiring over times and choose. The rest must be semirings except for the annihilator. That is, each must be a commutative monoid over choose; a monoid over times; and times must distribute over choose.
Tag to indicate component types of a composite magma.