MonoidOperation


Category: functors 
Component type: concept 
Description
A Monoid Operation is a special sort of Binary Function. A
Binary Function must satisfy three conditions in order to
be a Monoid Operation. First, its first argument type and second
argument type must be the same, and its result type must be the
same as its argument type. Second, there must be an identity
element. Third, the operation must be associative. Examples
of Monoid Operations are addition and multiplication. [1]
Refinement of
Binary Function
Associated types
Argument type

The type of the Monoid Operation's first argument and second argument,
and also the type returned when the Monoid Operation is returned.

Notation
F

A type that is a model of MonoidOperation

T

F's argument type.

f

Object of type F

x, y, z

Objects of type T

Definitions
A type F that is a model of binary function is associative if
F's first argument type, second argument type, and result type are
the same, and if, for every object f of type F and for every
objects x, y, and z of F's argument type,
f(x, f(y, z)) is the same as f(f(x, y), z). [2]
Valid Expressions
In addition to the expressions described in the Binary Function
requirements, the following expressions must be valid.
Name

Expression

Type requirements

Return type

Function call

f(x, y)


T

Identity element

identity_element(f) [3]


T

Expression semantics
Name

Expression

Precondition

Semantics

Postcondition

Function call

f(x, y)

x and y are in the domain of f.

Calls f with x and y as arguments.


Identity element

identity_element(f)


Returns the monoid's identity element. That is, the return value
is a value id of type T such that, for all x in the domain
of f, f(x, id) and f(id, x) both return x.


Complexity guarantees
Invariants
Associativity

For any x, y, and z of type T, f(x, f(y, z)) and
f(f(x, y), z) return the same value. [4]

Identity element.

There exists some element id of type T such that, for all
x of type T, f(x, id) and f(id, x) both return x.
The expression identity_element(f) returns id.

Models
Notes
[1]
A monoid is one of three closely related algebraic structures.
A semigroup is a set S, and a binary operation *, with the
properties that * is closed on S (that is, if x and y are elements of
S then x * y is also a member of S) and that * is associative (that
is, if x, y, and z are elements of S, then x * (y * z) = (x * y) * z).
A monoid is a semigroup that has an identity element. That is,
there exists some element id such that, for all x in S, x * id = id * x =
x. Finally, a group is a monoid with the property that every element
has an inverse. That is, for every x in S, there exists an element
xi such that x * xi = xi * x = id. As an example, the set of
real numbers under multiplication is a monoid (the identity element
is 1), but it isn't a group. It isn't a group because 0 has no inverse.
[2]
Mathematics textbooks typically write this as an equation,
instead of using words like "is the same as". We can't use
equality in this definition, however, because F's argument type
might not be equality comparable. If F's argument typeis
equality comparable, however, then these two expression are expected
to be equal: the condition of associativity becomes
f(x, f(y, z)) == f(f(x, y), z)
[3]
This is implemented as an overloaded function. The function
identity_element is defined, in function.h, for arguments of
type plus<T> and multiplies<T>. If you define a new
Monoid Operation F (matrix multiplication, for example), you must
overload identity_element for arguments of type F.
[4]
Associativity is not the same as commutativity. That is, the requirement
that x * (y * z) == (x * y) * z is completely unrelated to
the requirement that x * y == y * x. Monoid operations are
required to be associative, but they are not required to be
commutative. As an example, square matrices under multiplication
form a monoid even though matrix multiplication is not commutative.
See also
Binary Function, plus, multiplies
Copyright ©
1996 Silicon Graphics, Inc. All Rights Reserved.
TrademarkInformation