Predefined magmas

This library predefines a number of magmas. In some cases, this is just a wrapper around existing behaviour.

Arithmetic magma

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.

Cost and max semirings

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.

template <class Type>
class math::cost

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.

Templates
  • Type -

    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

cost()

Initialise with infinite cost. This results in the additive identity, also known as “zero”.

Post
this->value() == std::numeric_limits<Type>::infinity()

cost(Type const & value)

Initialise with a cost of value.

Type const & value() const

Return the underlying value.

template <class Type>
class math::max_semiring

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.

Templates
  • Type -

    Underlying type that represents the value.

Public Functions

max_semiring()

Initialise with 0.

max_semiring(Type const & value)

Initialise with value as the value.

Type const & value() const

Return the underlying value.

Sequence semiring

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.

template <class Symbol, class Direction = left>
class math::sequence

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.

See
math::empty_sequence, math::single_sequence, math::optional_sequence, math::sequence_annihilator

Public Functions

sequence()

Initialise with no symbols. (Multiplicative identity.)

sequence(empty_sequence< Symbol, Direction > const &)

Initialise with the empty sequence.

sequence(single_sequence< Symbol, Direction > const & s)

Initialise with a sequence with one element.

sequence(optional_sequence< Symbol, Direction > const & s)

Initialise with a sequence with zero or one element.

sequence(sequence_annihilator< Symbol, Direction > const &)

Initialise as the multiplicative annihilator. (Additive identity.)

template <class Range, class Enable = typename boost::enable_if <range::is_range <Range>>::type>
sequence(Range && range)

Initialise with a range of symbols.

template <class Range>
sequence(std::vector< Symbol > && range)

Initialise with a range of symbols. (Optimised version using the move constructor of std::vector.)

bool is_annihilator() const

Return true iff this is an annihilator.

bool empty() const

Return true iff this contains a symbol sequence of zero elements.

Pre
This is not an annihilator.

std::vector< Symbol > const & symbols() const

Return a range containing the symbols.

Pre
This is not an annihilator.

template <class Symbol, class Direction = left>
class math::empty_sequence

Sequence that is known at compile time to be of zero length.

See
math::sequence, math::single_sequence, math::optional_sequence

Public Functions

empty_sequence(sequence< Symbol, Direction > const & s)

Initialise with a sequence, which must be empty.

Exceptions

empty_sequence(single_sequence< Symbol, Direction > const &)

Initialise with single_sequence, which is never possible and always throws.

Exceptions

empty_sequence(optional_sequence< Symbol, Direction > const & s)

Initialise with optional_sequence, which must be empty.

Exceptions

template <class Range, class Enable = typename boost::enable_if <range::is_range <Range>>::type>
empty_sequence(Range && range)

Initialise with a range of symbols. This range must be empty.

template <class Symbol, class Direction = left>
class math::single_sequence

Sequence that is known at compile time to be of length one.

See
math::sequence, math::empty_sequence, math::optional_sequence

Public Functions

single_sequence(Symbol const & symbol)

Initialise with an explicit symbol.

template <class Range, class Enable1 = typename boost::enable_if <range::is_range <Range>>::type, class Enable2 = typename utility::disable_if_same_or_derived <Symbol, Range>::type>
single_sequence(Range && range)

Initialise with a range of symbols, which must have one element.

single_sequence(sequence< Symbol, Direction > const & that)

Convert from sequence: explicit.

Pre
The sequence must contain exactly one element.
Exceptions

template <class Symbol, class Direction = left>
class math::optional_sequence

Sequence that is known at compile time to be of length zero or one.

See
math::sequence

Public Functions

optional_sequence()

Initialise empty.

optional_sequence(Symbol const & symbol)

Initialise with an explicit symbol.

optional_sequence(empty_sequence< Symbol, Direction > const & that)

Convert empty, from empty_sequence.

optional_sequence(single_sequence< Symbol, Direction > const & that)

Convert with one symbol, from single_sequence.

optional_sequence(sequence< Symbol, Direction > const & that)

Convert from sequence: explicit.

Pre
The sequence must contain either zero or one element.
Exceptions

template <class Range, class Enable1 = typename boost::enable_if <range::is_range <Range>>::type, class Enable2 = typename utility::disable_if_same_or_derived <Symbol, Range>::type>
optional_sequence(Range && range)

Initialise with a range of symbols, which must have one element.

template <class Symbol, class Direction = left>
class math::sequence_annihilator

Sequence that is known at compile time to be the multiplicative annihilator: Multiplying this with any sequence yields a sequence_annihilator.

See
math::sequence

Public Functions

sequence_annihilator(sequence< Symbol, Direction > const & s)

Construct from a sequence, which must be an annihilator.

Exceptions

Composite magmas

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.

template <class Components, class Inverse = with_inverse<>>
class math::product

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.

Templates
  • Components -

    The list of components, given as math::over.

  • Inverse -

    (optional) An inverse operation that is allowed, given as math::with_inverse.

template <class Components>
class math::lexicographical

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.

Templates
  • Components -

    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.

template <class... Components>
struct math::over

Tag to indicate component types of a composite magma.

Table Of Contents

Previous topic

Operations

Next topic

Extending the sublibrary

This Page