Domain is GAP3's name for structured sets. The ring of Gaussian integers Z[I] is an example of a domain, the group D12 of symmetries of a regular hexahedron is another.
The GAP3 library predefines some domains. For example the ring of
Gaussian integers is predefined as GaussianIntegers
(see Gaussians)
and the field of rationals is predefined as Rationals
(see
Rationals). Most domains are constructed by functions, which are
called domain constructors. For example the group D12 is
constructed by the construction Group( (1,2,3,4,5,6), (2,6)(3,5) )
(see
Group) and the finite field with 16 elements is constructed by
GaloisField( 16 )
(see GaloisField).
The first place where you need domains in GAP3 is the obvious one.
Sometimes you simply want to talk about a domain. For example if you
want to compute the size of the group D12, you had better be able to
represent this group in a way that the Size
function can understand.
The second place where you need domains in GAP3 is when you want to be
able to specify that an operation or computation takes place in a certain
domain. For example suppose you want to factor 10 in the ring of
Gaussian integers. Saying Factors( 10 )
will not do, because this will
return the factorization in the ring of integers [ 2, 5 ]
. To allow
operations and computations to happen in a specific domain, Factors
,
and many other functions as well, accept this domain as optional first
argument. Thus Factors( GaussianIntegers, 10 )
yields the desired
result [ 1+E(4), 1-E(4), 2+E(4), 2-E(4) ]
.
Each domain in GAP3 belongs to one or more categories, which are simply sets of domains. The categories in which a domain lies determine the functions that are applicable to this domain and its elements. Examples of domains are rings (the functions applicable to a domain that is a ring are described in Rings), fields (see Fields), groups (see Groups), vector spaces (see Vector Spaces), and of course the category domains that contains all domains (the functions applicable to any domain are described in this chapter).
This chapter describes how domains are represented in GAP3 (see Domain Records), how functions that can be applied to different types of domains know how to solve a problem for each of those types (see Dispatchers, More about Dispatchers, and An Example of a Computation in a Domain), how domains are compared (see Comparisons of Domains), and the set theoretic functions that can be applied to any domain (see Elements, Membership Test for Domains, IsFinite, Size, IsSubset, Intersection, Union, Difference, Random).
The functions described in this chapter are implemented in the file
LIBNAME/"domain.g"
.
Domains are represented by records (see Records), which are called domain records in the following. Which components need to be present, which may, and what those components hold, differs from category to category, and, to a smaller extent, from domain to domain. It is generally possible though to distinguish four types of components.
Each domain record has the component isDomain
, which has the value
true
. Furthermore, most domains also have a component that specifies
which category this domain belongs to. For example, each group has the
component isGroup
, holding the value true
. Those components are
called the category components of the domain record. A domain that
only has the component isDomain
is a member only of the category
Domains and only the functions described in this chapter are applicable
to such a domain.
Every domain record also contains enough information to identify uniquely
the domain in the so called identification components. For example,
for a group the domain record, called group record in this case, has a
component called generators
containing a system of generators (and also
a component identity
holding the identity element of the group, needed
if the generator list is empty, as is the case for the trivial group).
Next the domain record holds all the knowledge GAP3 has about the domain, for example the size of the domain, in the so called knowledge components. Of course, the knowledge about a certain domain will usually increase as time goes by. For example, a group record may initially hold only the knowledge that the group is finite, but may end holding all kinds of knowledge, for example the derived series, the Sylow subgroups, etc.
Finally each domain record has a component, which is called its
operations record (because it is the component with the name
operations
and it holds a record), that tells functions like Size
how
to compute this information for this domain. The exact mechanism is
described later (see Dispatchers).
In the previous section it was mentioned that domains are represented by
domain records, and that each domain record has an operations record.
This operations record is used by functions like Size
to find out how
to compute this information for the domain. Let us discuss this
mechanism using the example of Size
. Suppose you call Size
with a
domain D.
First Size
tests whether D has a component called size
, i.e., if
D.size
is bound. If it is, Size
assumes that it holds the size of
the domain and returns this value.
Let us suppose that this component has no assigned value. Then Size
looks at the component D.operations
, which must be a record. Size
takes component D.operations.Size
of this record, which must be a
function. Size
calls this function passing D as argument. If a
domain record has no Size
function in its operations record, an error
is signalled.
Finally Size
stores the value returned by D.operations.Size( D )
in the component D.size
, where it is available for the next call of
Size( D )
.
Because functions like Size
do little except dispatch to the function
in the operations record they are called dispatcher functions.
Which function is called through this mechanism obviously depends on the
domain and its operations record. In principle each domain could have
its own Size
function. In practice however this is not the case. For
example all permutation groups share the operations record PermGroupOps
so they all use the same Size
function PermGroupOps.Size
.
Note that in fact domains of the same type not only share the functions,
in fact they share the operations record. So for example all permutation
groups have the same operations record. This means that changing such a
function for a domain D in the following way D.operations.function
:= new-function;
will also change this function for all domains of
the same type, even those that do not yet exist at the moment of the
assignment and will only be constructed later. This is usually not
desirable, since supposedly new-function uses some special properties
of the domain D to work efficiently. We suggest therefore, that you
use the following assignments instead:
D.operations := Copy( D.operations );
D.operations.function := new-function;
.
Some domains do not provide a special Size
function, either because no
efficient method is known or because the author that implemented the
domain simply was too lazy to write one. In those cases the domain
inherits the default function, which is DomainOps.Size
. Such
inheritance is uncommon for the Size
function, but rather common for
the Union
function.
Usually you need not care about the mechanism described in the previous
section. You just call the dispatcher functions like Size
. They will
call the function in the operations record, which is hopefully
implementing an algorithm that is well suited for their domain, by using
the structure of this domain.
There are three reasons why you might want to avoid calling the dispatcher function and call the dispatched to function directly.
The first reason is efficiency. The dispatcher functions don't do very
much. They only check the types of their arguments, check if the
requested information is already present, and dispatch to the appropriate
function in the operations record. But sometimes, for example in the
innermost loop of your algorithm, even this little is too much. In those
cases you can avoid the overhead introduced by the dispatcher function by
calling the function in the operations record directly. For example, you
would use G.operations.Size(G)
instead of Size(G)
.
The second reason is flexibility. Sometimes you do not want to call the
function in the operations record, but another function that performs the
same task, using a different algorithm. In that case you will call this
different function. For example, if G is a permutation group, and the
orbit of p under G is very short, GroupOps.Orbit(G,p)
, which is
the default function to compute an orbit, may be slightly more efficient
than Orbit(G,p)
, which calls G.operations.Orbit(G,p)
, which
is the same as PermGroupOps.Orbit(G,p)
.
The third has to do with the fact that the dispatcher functions check for
knowledge components like D.size
or D.elements
and also store
their result in such components. For example, suppose you know that the
result of a computation takes up quite some space, as is the case with
Elements(D)
, and that you will never need the value again. In this
case you would not want the dispatcher function to enter the value in the
domain record, and therefore would call D.operations.Elements(D)
directly. On the other hand you may not want to use the value in the
domain record, because you mistrust it. In this case you should call the
function in the operations record directly, e.g., you would use
G.operations.Size(G)
instead of Size(G)
(and then compare the
result with G.size
).
4.4 An Example of a Computation in a Domain
This section contains an extended example to show you how a computation
in a domain may use default and special functions to achieve its goal.
Suppose you defined G
, x
, and y
as follows.
gap> G := SymmetricGroup( 8 );; gap> x := [ (2,7,4)(3,5), (1,2,6)(4,8) ];; gap> y := [ (2,5,7)(4,6), (1,5)(3,8,7) ];;
Now you ask for an element of G
that conjugates x
to y
, i.e., a
permutation on 8 points that takes (2,7,4)(3,5)
to (2,5,7)(4,6)
and
(1,2,6)(4,8)
to (1,5)(3,8,7)
. This is done as follows (see
RepresentativeOperation and Other Operations).
gap> RepresentativeOperation( G, x, y, OnTuples ); (1,8)(2,7)(3,4,5,6)
Let us look at what happens step by step. First
RepresentativeOperation
is called. After checking the arguments it
calls the function G.operations.RepresentativeOperation
, which is the
function SymmetricGroupOps.RepresentativeOperation
, passing the
arguments G
, x
, y
, and OnTuples
.
SymmetricGroupOps.RepresentativeOperation
handles a lot of cases
specially, but the operation on tuples of permutations is not among them.
Therefore it delegates this problem to the function that it overlays,
which is PermGroupOps.RepresentativeOperation
.
PermGroupOps.RepresentativeOperation
also does not handle this special
case, and delegates the problem to the function that it overlays, which
is the default function called GroupOps.RepresentativeOperation
.
GroupOps.RepresentativeOperation
views this problem as a general tuples
problem, i.e., it does not care whether the points in the tuples are
integers or permutations, and decides to solve it one step at a time. So
first it looks for an element taking (2,7,4)(3,5)
to (2,5,7)(4,6)
by
calling RepresentativeOperation( G, (2,7,4)(3,5), (2,5,7)(4,6) )
.
RepresentativeOperation
calls G.operations.RepresentativeOperation
next, which is the function SymmetricGroupOps.RepresentativeOperation
,
passing the arguments G
, (2,7,4)(3,5)
, and (2,5,7)(4,6)
.
SymmetricGroupOps.RepresentativeOperation
can handle this case. It
knows that G
contains every permutation on 8 points, so it contains
(3,4,7,5,6)
, which obviously does what we want, namely it takes x[1]
to y[1]
. We will call this element t
.
Now GroupOps.RepresentativeOperation
(see above) looks for an s
in
the stabilizer of x[1]
taking x[2]
to y[2]^(t^-1)
, since then for
r=s*t
we have x[1]^r = (x[1]^s)^t = x[1]^t = y[1]
and also
x[2]^r = (x[2]^s)^t = (y[2]^(t^-1))^t = y[2]
. So the next step
is to compute the stabilizer of x[1]
in G
. To do this it calls
Stabilizer( G, (2,7,4)(3,5) )
.
Stabilizer
calls G.operations.Stabilizer
, which is
SymmetricGroupOps.Stabilizer
, passing the arguments G
and
(2,7,4)(3,5)
. SymmetricGroupOps.Stabilizer
detects that the second
argument is a permutation, i.e., an element of the group, and calls
Centralizer( G, (2,7,4)(3,5) )
. Centralizer
calls the function
G.operations.Centralizer
, which is SymmetricGroupOps.Centralizer
,
again passing the arguments G
, (2,7,4)(3,5)
.
SymmetricGroupOps.Centralizer
again knows how centralizers in
symmetric groups look, and after looking at the permutation
(2,7,4)(3,5)
sharply for a short while returns the centralizer as
Subgroup( G, [ (1,6), (1,6,8), (2,7,4), (3,5) ] )
, which we will call
S
. Note that S
is of course not a symmetric group, therefore
SymmetricGroupOps.Subgroup
gives it PermGroupOps
as operations record
and not SymmetricGroupOps
.
As explained above GroupOps.RepresentativeOperation
needs an element of
S
taking x[2]
((1,2,6)(4,8)
) to y[2]^(t^-1)
((1,7)(4,6,8)
).
So RepresentativeOperation( S, (1,2,6)(4,8), (1,7)(4,6,8) )
is called.
RepresentativeOperation
in turn calls the function
S.operations.RepresentativeOperation
, which is, since S
is a
permutation group, the function PermGroupOps.RepresentativeOperation
,
passing the arguments S
, (1,2,6)(4,8)
, and (1,7)(4,6,8)
.
PermGroupOps.RepresentativeOperation
detects that the points are
permutations and and performs a backtrack search through S
. It finds
and returns (1,8)(2,4,7)(3,5)
, which we call s
.
Then GroupOps.RepresentativeOperation
returns r = s*t =
(1,8)(2,7)(3,6)(4,5)
, and we are done.
In this example you have seen how functions use the structure of their
domain to solve a problem most efficiently, for example
SymmetricGroupOps.RepresentativeOperation
but also the backtrack search
in PermGroupOps.RepresentativeOperation
, how they use other functions,
for example SymmetricGroupOps.Stabilizer
called Centralizer
, and how
they delegate cases which they can not handle more efficiently back to
the function they overlaid, for example
SymmetricGroupOps.RepresentativeOperation
delegated to
PermGroupOps.RepresentativeOperation
, which in turn delegated to to the
function GroupOps.RepresentativeOperation
.
Domain( list )
Domain
returns a domain that contains all the elements in list and
that knows how to make the ring, field, group, or vector space that
contains those elements.
Note that the domain returned by Domain
need in general not be a ring,
field, group, or vector space itself. For example if passed a list of
elements of finite fields Domain
will return the domain
FiniteFieldElements
. This domain contains all finite field elements,
no matter of which characteristic. This domain has a function
FiniteFieldElementsOps.Field
that knows how to make a finite field that
contains the elements in list. This function knows that all elements
must have the same characteristic for them to lie in a common field.
gap> D := Domain( [ Z(4), Z(8) ] ); FiniteFieldElements gap> IsField( D ); false gap> D.operations.Field( [ Z(4), Z(8) ] ); GF(2^6)
Domain
is the only function in the whole GAP3 library that knows
about the various types of elements. For example, when Norm
is
confronted by a field element z, it does not know what to do with it.
So it calls F := DefaultField( [ z ] )
to get a field in which z
lies, because this field (more precisely F.operations.Norm
) will know
better. However, DefaultField
also does not know what to do with z.
So it calls D := Domain( [ z ] )
to get a domain in which z lies,
because it (more precisely D.operations.DefaultField
) will know how to
make a default field in which z lies.
Elements( D )
Elements
returns the set of elements of the domain D. The set is
returned as a new proper set, i.e., as a new sorted list without holes
and duplicates (see Sets). D may also be a list, in which case the
set of elements of this list is returned. An error is signalled if D
is an infinite domain.
gap> Elements( GaussianIntegers ); Error, the ring <R> must be finite to compute its elements gap> D12 := Group( (2,6)(3,5), (1,2)(3,6)(4,5) );; gap> Elements( D12 ); [ (), (2,6)(3,5), (1,2)(3,6)(4,5), (1,2,3,4,5,6), (1,3)(4,6), (1,3,5)(2,4,6), (1,4)(2,3)(5,6), (1,4)(2,5)(3,6), (1,5)(2,4), (1,5,3)(2,6,4), (1,6,5,4,3,2), (1,6)(2,5)(3,4) ]
Elements
remembers the set of elements in the component D.elements
and will return a shallow copy (see ShallowCopy) next time it is called
to compute the elements of D. If you want to avoid this, for example
for a large domain, for which you know that you will not need the list of
elements in the future, either unbind (see Unbind) D.elements
or
call D.operation.Elements(D)
directly.
Since there is no general method to compute the elements of a domain the
default function DomainOps.Elements
just signals an error. This
default function is overlaid for each special finite domain. In fact,
implementors of domains, must implement this function for new domains,
since it is, together with IsFinite
(see IsFinite) the most basic
function for domains, used by most of the default functions in the domain
package.
In general functions that return a set of elements are free, in fact
encouraged, to return a domain instead of the proper set of elements.
For one thing this allows to keep the structure, for another the
representation by a domain record is usually more space efficient.
Elements
must not do this, its only purpose is to create the proper set
of elements.
D = E
D <> E
=
evaluates to true
if the two domains D and E are equal, to
false
otherwise. <>
evaluates to true
if the two domains D and
E are different and to false
if they are equal.
Two domains are considered equal if and only if the sets of their
elements as computed by Elements
(see Elements) are equal. Thus, in
general =
behaves as if each domain operand were replaced by its set of
elements. Except that =
will also sometimes, but not always, work for
infinite domains, for which it is of course difficult to compute the set
of elements. Note that this implies that domains belonging to different
categories may well be equal. As a special case of this, either operand
may also be a proper set, i.e., a sorted list without holes or duplicates
(see Set), and the result will be true
if and only if the set of
elements of the domain is, as a set, equal to the set. It is also
possible to compare a domain with something else that is not a domain or
a set, but the result will of course always be false
in this case.
gap> GaussianIntegers = D12; false # GAP3 knows that those domains cannot be equal because #GaussianIntegers
is infinite andD12
is finite gap> GaussianIntegers = Integers; false # GAP3 knows how to compare those two rings gap> GaussianIntegers = Rationals; Error, sorry, cannot compare the infinite domains <D> and <E> gap> D12 = Group( (2,6)(3,5), (1,2)(3,6)(4,5) ); true gap> D12 = [(),(2,6)(3,5),(1,2)(3,6)(4,5),(1,2,3,4,5,6),(1,3)(4,6), > (1,3,5)(2,4,6),(1,4)(2,3)(5,6),(1,4)(2,5)(3,6), > (1,5)(2,4),(1,5,3)(2,6,4),(1,6,5,4,3,2),(1,6)(2,5)(3,4)]; true gap> D12 = [(1,6,5,4,3,2),(1,6)(2,5)(3,4),(1,5,3)(2,6,4),(1,5)(2,4), > (1,4)(2,5)(3,6),(1,4)(2,3)(5,6),(1,3,5)(2,4,6),(1,3)(4,6), > (1,2,3,4,5,6),(1,2)(3,6)(4,5),(2,6)(3,5),()]; false # since the left operand behaves as a set # while the right operand is not a set
The default function DomainOps.'='
checks whether both domains are
infinite. If they are, an error is signalled. Otherwise, if one domain
is infinite, false
is returned. Otherwise the sizes (see Size) of
the domains are compared. If they are different, false
is returned.
Finally the sets of elements of both domains are computed (see
Elements) and compared. This default function is overlaid by more
special functions for other domains.
D < E
D <= E
D > E
D >= E
<
, <=
, >
, and >=
evaluate to true
if the domain D is less
than, less than or equal to, greater than, and greater than or equal to
the domain E and to false
otherwise.
A domain D is considered less than a domain E if and only if the set of elements of D is less than the set of elements of the domain E. Generally you may just imagine that each domain operand is replaced by the set of its elements, and that the comparison is performed on those sets (see Comparisons of Lists). This implies that, if you compare a domain with an object that is not a list or a domain, this other object will be less than the domain, except if it is a record, in which case it is larger than the domain (see Comparisons).
Note that <
does not test whether the left domain is a subset of the
right operand, even though it resembles the mathematical subset
notation.
gap> GaussianIntegers < Rationals; Error, sorry, cannot compare <E> with the infinite domain <D> gap> Group( (1,2), (1,2,3,4,5,6) ) < D12; true # since(5,6)
, the second element of the left operand, # is less than(2,6)(3,5)
, the second element ofD12
. gap> D12 < [(1,6,5,4,3,2),(1,6)(2,5)(3,4),(1,5,3)(2,6,4),(1,5)(2,4), > (1,4)(2,5)(3,6),(1,4)(2,3)(5,6),(1,3,5)(2,4,6),(1,3)(4,6), > (1,2,3,4,5,6),(1,2)(3,6)(4,5),(2,6)(3,5),()]; true # since()
, the first element ofD12
, is less than #(1,6,5,4,3,2)
, the first element of the right operand. gap> 17 < D12; true # objects that are not lists or records are smaller # than domains, which behave as if they were a set
The default function DomainOps.'<'
checks whether either domain is
infinite. If one is, an error is signalled. Otherwise the sets of
elements of both domains are computed (see Elements) and compared.
This default function is only very seldom overlaid by more special
functions for other domains. Thus the operators <
, <=
, >
, and
>=
are quite expensive and their use should be avoided if possible.
4.8 Membership Test for Domains
elm in D
in
returns true
if the element elm, which may be an object of any
type, lies in the domain D, and false
otherwise.
gap> 13 in GaussianIntegers; true gap> GaussianIntegers in GaussianIntegers; false gap> (1,2) in D12; false gap> (1,2)(3,6)(4,5) in D12; true
The default function for domain membership tests is DomainOps.'in'
,
which computes the set of elements of the domain with the function
Elements
(see Elements) and tests whether elm lies in this set.
Special domains usually overlay this function with more efficient
membership tests.
IsFinite( D )
IsFinite
returns true
if the domain D is finite and false
otherwise. D may also be a proper set (see Set), in which case the
result is of course always true
.
gap> IsFinite( GaussianIntegers ); false gap> IsFinite( D12 ); true
The default function DomainOps.IsFinite
just signals an error, since
there is no general method to determine whether a domain is finite or
not. This default function is overlaid for each special domain. In
fact, implementors of domains must implement this function for new
domains, since it is, together with Elements
(see Elements), the most
basic function for domains, used by most of the default functions in the
domain package.
Size( D )
Size
returns the size of the domain D. If D is infinite, Size
returns the string "infinity"
. D may also be a proper set (see
Set), in which case the result is the length of this list. Size
will, however, signal an error if D is a list that is not a proper set,
i.e., that is not sorted, or has holes, or contains duplicates.
gap> Size( GaussianIntegers ); "infinity" gap> Size( D12 ); 12
The default function to compute the size of a domain is DomainOps.Size
,
which computes the set of elements of the domain with the function
Elements
(see Elements) and returns the length of this set. This
default function is overlaid in practically every domain.
IsSubset( D, E )
IsSubset
returns true
if the domain E is a subset of the domain D
and false
otherwise.
E is considered a subset of D if and only if the set of elements of
E is as a set a subset of the set of elements of D (see Elements
and Set Functions for Sets). That is IsSubset
behaves as if
implemented as IsSubsetSet( Elements(D), Elements(E) )
, except that
it will also sometimes, but not always, work for infinite domains, and
that it will usually work much faster than the above definition. Either
argument may also be a proper set.
gap> IsSubset( GaussianIntegers, [1,E(4)] ); true gap> IsSubset( GaussianIntegers, Rationals ); Error, sorry, cannot compare the infinite domains <D> and <E> gap> IsSubset( Group( (1,2), (1,2,3,4,5,6) ), D12 ); true gap> IsSubset( D12, [ (), (1,2)(3,4)(5,6) ] ); false
The default function DomainOps.IsSubset
checks whether both domains are
infinite. If they are it signals an error. Otherwise if the E is
infinite it returns false
. Otherwise if D is infinite it tests if
each element of E is in D (see Membership Test for Domains).
Otherwise it tests whether the proper set of elements of E is a subset
of the proper set of elements of D (see Elements and Set Functions
for Sets).
Intersection( D1, D2... )
Intersection( list )
In the first form Intersection
returns the intersection of the domains
D1, D2, etc. In the second form list must be a list of domains and
Intersection
returns the intersection of those domains. Each argument
D or element of list respectively may also be an arbitrary list, in
which case Intersection
silently applies Set
(see Set) to it first.
The result of Intersection
is the set of elements that lie in every of
the domains D1, D2, etc. Functions called by the dispatcher function
Intersection
however, are encouraged to keep as much structure as
possible. So if D1 and D2 are elements of a common category and if
this category is closed under taking intersections, then the result
should be a domain lying in this category too. So for example the
intersection of permutation groups will again be a permutation group.
gap> Intersection( CyclotomicField(9), CyclotomicField(12) ); CF(3) #CF
is a shorthand forCyclotomicField
# this is one of the rare cases where the intersection # of two infinite domains works gap> Intersection( GaussianIntegers, Rationals ); Error, sorry, cannot intersect infinite domains <D> and <E> gap> Intersection( D12, Group( (1,2), (1,2,3,4,5) ) ); Group( (1,5)(2,4) ) gap> Intersection( D12, [ (1,3)(4,6), (1,2)(3,4) ] ); [ (1,3)(4,6) ] # note that the second argument is not a set gap> Intersection( D12, [ (), (1,2)(3,4), (1,3)(4,6), (1,4)(5,6) ] ); [ (), (1,3)(4,6) ] # although the result is mathematically a # group it is returned as a proper set # because the second argument was not a group gap> Intersection( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] ); [ ] # two or more domains or sets as arguments are legal gap> Intersection( [ [1,2,4], [2,3,4], [1,3,4] ] ); [ 4 ] # or a list of domains or sets gap> Intersection( [ ] ); Error, List Element: <list>[1] must have a value
The dispatcher function (see Dispatchers) Intersection
is slightly
different from other dispatcher functions. It does not simply call the
function in the operations record passings its arguments. Instead it
loops over its arguments (or the list of domains or sets) and calls the
function in the operations record repeatedly, and passes each time only
two domains. This obviously makes writing the function for the
operations record simpler.
The default function DomainOps.Intersection
checks whether both domains
are infinite. If they are it signals an error. Otherwise, if one of the
domains is infinite it loops over the elements of the other domain, and
tests for each element whether it lies in the infinite domain. If both
domains are finite it computes the proper sets of elements of both and
intersects them (see Elements and Set Functions for Sets). This
default method is overlaid by more special functions for most other
domains. Those functions usually are faster and keep the structure of
the domains if possible.
Union( D1, D2... )
Union( list )
In the first form Union
returns the union of the domains D1, D2,
etc. In the second form list must be a list of domains and Union
returns the union of those domains. Each argument D or element of
list respectively may also be an arbitrary list, in which case Union
silently applies Set
(see Set) to it first.
The result of Union
is the set of elements that lie in any the domains
D1, D2, etc. Functions called by the dispatcher function Union
however, are encouraged to keep as much structure as possible. However,
currently GAP3 does not support any category that is closed under
taking unions except the category of all domains. So the only case that
structure will be kept is when one argument D or element of list
respectively is a superset of all the other arguments or elements of
list.
gap> Union( GaussianIntegers, Rationals ); Error, sorry, cannot unite <E> with the infinite domain <D> gap> Union( D12, Group( (1,2), (1,2,3) ) ); [ (), (2,3), (2,6)(3,5), (1,2), (1,2)(3,6)(4,5), (1,2,3), (1,2,3,4,5,6), (1,3,2), (1,3), (1,3)(4,6), (1,3,5)(2,4,6), (1,4)(2,3)(5,6), (1,4)(2,5)(3,6), (1,5)(2,4), (1,5,3)(2,6,4), (1,6,5,4,3,2), (1,6)(2,5)(3,4) ] gap> Union( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] ); [ 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20, 25 ] # two or more domains or sets as arguments are legal gap> Union( [ [1,2,4], [2,3,4], [1,3,4] ] ); [ 1, 2, 3, 4 ] # or a list of domains or sets gap> Union( [ ] ); [ ]
The dispatcher function (see Dispatchers) Union
is slightly different
from other dispatcher functions. It does not simply call the function in
the operations record passings its arguments. Instead it loops over its
arguments (or the list of domains or sets) and calls the function in the
operations record repeatedly, and passes each time only two domains.
This obviously makes writing the function for the operations record
simpler.
The default function DomainOps.Union
checks whether either domain is
infinite. If one is it signals an error. If both domains are finite it
computes the proper sets of elements of both and unites them (see
Elements and Set Functions for Sets). This default method is
overlaid by more special functions for some other domains. Those
functions usually are faster.
Difference( D, E )
Difference
returns the set difference of the domains D and E.
Either argument may also be an arbitrary list, in which case Difference
silently applies Set
(see Set) to it first.
The result of Difference
is the set of elements that lie in D but not
in E. Note that E need not be a subset of D. The elements of E,
however, that are not element of D play no role for the result.
gap> Difference( D12, [(),(1,2,3,4,5,6),(1,3,5)(2,4,6), > (1,4)(2,5)(3,6),(1,6,5,4,3,2),(1,5,3)(2,6,4)] ); [ (2,6)(3,5), (1,2)(3,6)(4,5), (1,3)(4,6), (1,4)(2,3)(5,6), (1,5)(2,4), (1,6)(2,5)(3,4) ]
The default function DomainOps.Difference
checks whether D is
infinite. If it is it signals an error. Otherwise Difference
computes
the proper sets of elements of D and E and returns the difference of
those sets (see Elements and SubtractSet). This default function is
currently not overlaid for any domain.
Representative( D )
Representative
returns a representative of the domain D.
The existence of a representative, and the exact definition of what a representative is, depends on the category of D. The representative should be an element that, within a given context, identifies the domain D. For example if D is a cyclic group, its representative would be a generator of D, or if D is a coset, its representative would be an arbitrary element of the coset.
Note that Representative
is pretty free in choosing a representative if
there are several. It is not even guaranteed that Representative
returns the same representative if it is called several times for one
domain. Thus the main difference between Representative
and Random
(see Random) is that Representative
is free to choose a value that is
cheap to compute, while Random
must make an effort to randomly
distribute its answers.
gap> C := Coset( Subgroup( G, [(1,4)(2,5)(3,6)] ), (1,6,5,4,3,2) );; gap> Representative( C ); (1,3,5)(2,4,6)
Representative
first tests whether the component D.representative
is bound. If the field is bound it returns its value. Otherwise it
calls D.operations.Representative( D )
, remembers the returned
value in D.representative
, and returns it.
The default function called this way is DomainOps.Representative
, which
simply signals an error, since there is no default way to find a
representative.
Random( D )
Random
returns a random element of the domain D. The distribution of
elements returned by Random
depends on the domain D. For finite
domains all elements are usually equally likely. For infinite domains
some reasonable distribution is used. See the chapters of the various
domains to find out which distribution is being used.
gap> Random( GaussianIntegers ); 1-4*E(4) gap> Random( GaussianIntegers ); 1+2*E(4) gap> Random( D12 ); () gap> Random( D12 ); (1,4)(2,5)(3,6)
The default function for random selection is DomainOps.Random
, which
computes the set of elements using Elements
and selects a random
element of this list using RandomList
(see RandomList for a
description of the pseudo random number generator used). This default
function can of course only be applied to finite domains. It is overlaid
by other functions for most other domains.
All random functions called this way rely on the low level random number
generator provided by RandomList
(see RandomList).
gap3-jm