Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
| Download
GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
Project: cocalc-sagemath-dev-slelievre
Views: 418346#############################################################################
##
#W coll.gd GAP library Martin Schönert
#W & Thomas Breuer
##
##
#Y Copyright (C) 1997, Lehrstuhl D für Mathematik, RWTH Aachen, Germany
#Y (C) 1998 School Math and Comp. Sci., University of St Andrews, Scotland
#Y Copyright (C) 2002 The GAP Group
##
## This file declares the operations for collections.
##
#T change the installation of isomorphism and factor maintained methods
#T in the same way as that of subset maintained methods!
#############################################################################
##
## <#GAPDoc Label="[1]{coll}">
## A <E>collection</E> in &GAP; consists of elements in the same family
## (see <Ref Sect="Families"/>).
## The most important kinds of collections are <E>homogeneous lists</E>
## (see <Ref Chap="Lists"/>)
## and <E>domains</E> (see <Ref Chap="Domains"/>).
## Note that a list is never a domain, and a domain is never a list.
## A list is a collection if and only if it is nonempty and homogeneous.
## <P/>
## Basic operations for collections are <Ref Func="Size"/>
## and <Ref Func="Enumerator"/>;
## for <E>finite</E> collections,
## <Ref Func="Enumerator"/> admits to delegate the other
## operations for collections
## (see <Ref Sect="Attributes and Properties for Collections"/>
## and <Ref Sect="Operations for Collections"/>)
## to functions for lists (see <Ref Chap="Lists"/>).
## Obviously, special methods depending on the arguments are needed for
## the computation of e.g. the intersection of two <E>infinite</E>
## domains.
## <#/GAPDoc>
##
#############################################################################
##
#C IsListOrCollection( <obj> )
##
## <#GAPDoc Label="IsListOrCollection">
## <ManSection>
## <Filt Name="IsListOrCollection" Arg='obj' Type='Category'/>
##
## <Description>
## Several functions are defined for both lists and collections,
## for example <Ref Func="Intersection" Label="for a list"/>,
## <Ref Func="Iterator"/>,
## and <Ref Func="Random" Label="for a list or collection"/>.
## <Ref Func="IsListOrCollection"/> is a supercategory of
## <Ref Func="IsList"/> and <Ref Func="IsCollection"/>
## (that is, all lists and collections lie in this category),
## which is used to describe the arguments of functions such as the ones
## listed above.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsListOrCollection", IsObject );
#############################################################################
##
#C IsCollection( <obj> ) . . . . . . . . . test if an object is a collection
##
## <#GAPDoc Label="IsCollection">
## <ManSection>
## <Filt Name="IsCollection" Arg='obj' Type='Category'/>
##
## <Description>
## tests whether an object is a collection.
## <P/>
## Some of the functions for lists and collections are described in the
## chapter about lists,
## mainly in Section <Ref Sect="Operations for Lists"/>.
## In the current chapter, we describe those functions for which the
## <Q>collection aspect</Q> seems to be more important than the
## <Q>list aspect</Q>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsCollection", IsListOrCollection );
#############################################################################
##
#A CollectionsFamily( <Fam> ) . . . . . . . . . . make a collections family
##
## <#GAPDoc Label="CollectionsFamily">
## <ManSection>
## <Attr Name="CollectionsFamily" Arg='Fam'/>
##
## <Description>
## For a family <A>Fam</A>, <Ref Func="CollectionsFamily"/> returns the
## family of all collections over <A>Fam</A>,
## that is, of all dense lists and domains that consist of objects in
## <A>Fam</A>.
## <P/>
## The <Ref Func="NewFamily"/> call in the standard method of
## <Ref Func="CollectionsFamily"/> is executed with second argument
## <Ref Func="IsCollection"/>,
## since every object in the collections family must be a collection,
## and with third argument the collections categories of the involved
## categories in the implied filter of <A>Fam</A>.
## <P/>
## Note that families (see <Ref Sect="Families"/>)
## are used to describe relations between objects.
## Important such relations are that between an element <M>e</M> and each
## collection of elements that lie in the same family as <M>e</M>,
## and that between two collections whose elements lie in the same family.
## Therefore, all collections of elements in the family <A>Fam</A> form the
## new family <C>CollectionsFamily( <A>Fam</A> )</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "CollectionsFamily", IsFamily );
#############################################################################
##
#C IsCollectionFamily( <Fam> ) test if an object is a family of collections
##
## <#GAPDoc Label="IsCollectionFamily">
## <ManSection>
## <Filt Name="IsCollectionFamily" Arg='obj' Type='Category'/>
##
## <Description>
## is <K>true</K> if <A>Fam</A> is a family of collections,
## and <K>false</K> otherwise.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategoryFamily( "IsCollection" );
#############################################################################
##
#A ElementsFamily( <Fam> ) . . . . . . . . . . . . fetch the elements family
##
## <#GAPDoc Label="ElementsFamily">
## <ManSection>
## <Attr Name="ElementsFamily" Arg='Fam'/>
##
## <Description>
## If <A>Fam</A> is a collections family
## (see <Ref Func="IsCollectionFamily"/>)
## then <Ref Func="ElementsFamily"/>
## returns the family from which <A>Fam</A> was created
## by <Ref Func="CollectionsFamily"/>.
## The way a collections family is created, it always has its elements
## family stored.
## If <A>Fam</A> is not a collections family then an error is signalled.
## <P/>
## <Example><![CDATA[
## gap> fam:= FamilyObj( (1,2) );;
## gap> collfam:= CollectionsFamily( fam );;
## gap> fam = collfam; fam = ElementsFamily( collfam );
## false
## true
## gap> collfam = FamilyObj( [ (1,2,3) ] );
## true
## gap> collfam = FamilyObj( Group( () ) );
## true
## gap> collfam = CollectionsFamily( collfam );
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "ElementsFamily", IsFamily );
#############################################################################
##
#V CATEGORIES_COLLECTIONS . . . . . . global list of collections categories
##
## <ManSection>
## <Var Name="CATEGORIES_COLLECTIONS"/>
##
## <Description>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "CATEGORIES_COLLECTIONS", [] );
#############################################################################
##
#F CategoryCollections( <filter> ) . . . . . . . . . . collections category
##
## <#GAPDoc Label="CategoryCollections">
## <ManSection>
## <Func Name="CategoryCollections" Arg='filter'/>
##
## <Description>
## Let <A>filter</A> be a filter that is <K>true</K> for all elements of a
## family <A>Fam</A>, by the construction of <A>Fam</A>.
## Then <Ref Func="CategoryCollections"/> returns the
## <E>collections category</E> of <A>filter</A>.
## This is a category that is <K>true</K> for all elements in
## <C>CollectionsFamily( <A>Fam</A> )</C>.
## <P/>
## For example, the construction of
## <Ref Var="PermutationsFamily"/> guarantees that
## each of its elements lies in the filter
## <Ref Func="IsPerm"/>,
## and each collection of permutations (permutation group or dense list of
## permutations) lies in the category <C>CategoryCollections( IsPerm )</C>.
## <C>CategoryCollections( IsPerm )</C>.
## Note that this works only if the collections category is created
## <E>before</E> the collections family.
## So it is necessary to construct interesting collections categories
## immediately after the underlying category has been created.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "CategoryCollections", function ( elms_filter )
local pair, super, flags, name, coll_filter;
# Check whether the collections category is already defined.
for pair in CATEGORIES_COLLECTIONS do
if IsIdenticalObj( pair[1], elms_filter ) then
return pair[2];
fi;
od;
# Find the super category among the known collections categories.
super := IsCollection;
flags := WITH_IMPS_FLAGS( FLAGS_FILTER( elms_filter ) );
for pair in CATEGORIES_COLLECTIONS do
if IS_SUBSET_FLAGS( flags, FLAGS_FILTER( pair[1] ) ) then
super := super and pair[2];
fi;
od;
# Construct the name of the category.
name := "CategoryCollections(";
APPEND_LIST_INTR( name, SHALLOW_COPY_OBJ( NameFunction(elms_filter) ) );
APPEND_LIST_INTR( name, ")" );
CONV_STRING( name );
# Construct the collections category.
coll_filter:= NewCategory( name, super );
ADD_LIST( CATEGORIES_COLLECTIONS, [ elms_filter, coll_filter ] );
return coll_filter;
end );
#############################################################################
##
#f DeclareCategoryCollections( <name> )
##
## binds the collections category of the category that is bound to the
## global variable with name <name> to the global variable associated to the
## name <nname>.
## If <name> is of the form `<initname>Collection' then <nname> is equal to
## `<initname>CollColl',
## if <name> is of the form `<initname>Coll' then <nname> is equal to
## `<initname>CollColl',
## otherwise we have <nname> equal to `<name>Collection'.
##
BIND_GLOBAL( "DeclareCategoryCollections", function( name )
local len, coll_name;
len:= LEN_LIST( name );
if 3 < len and name{ [ len-3 .. len ] } = "Coll" then
coll_name:= SHALLOW_COPY_OBJ( name );
APPEND_LIST_INTR( coll_name, "Coll" );
elif 9 < len and name{ [ len-9 .. len ] } = "Collection" then
coll_name:= name{ [ 1 .. len-6 ] };
APPEND_LIST_INTR( coll_name, "Coll" );
else
coll_name:= SHALLOW_COPY_OBJ( name );
APPEND_LIST_INTR( coll_name, "Collection" );
fi;
BIND_GLOBAL( coll_name, CategoryCollections( VALUE_GLOBAL( name ) ) );
end );
#############################################################################
##
#F DeclareSynonym( <name>, <value> )
#F DeclareSynonymAttr( <name>, <value> )
##
## <#GAPDoc Label="DeclareSynonym">
## <ManSection>
## <Func Name="DeclareSynonym" Arg='name, value'/>
## <Func Name="DeclareSynonymAttr" Arg='name, value'/>
##
## <Description>
## <Ref Func="DeclareSynonym"/> assigns the string <A>name</A> to a global
## variable as a synonym for <A>value</A>.
## Two typical intended usages are to declare an <Q>and-filter</Q>, e.g.
## <P/>
## <Log><![CDATA[
## DeclareSynonym( "IsGroup", IsMagmaWithInverses and IsAssociative );
## ]]></Log>
## <P/>
## and to provide a previously declared global function with an alternative
## name, e.g.
## <P/>
## <Log><![CDATA[
## DeclareGlobalFunction( "SizeOfSomething" );
## DeclareSynonym( "OrderOfSomething", SizeOfSomething );
## ]]></Log>
## <P/>
## <E>Note:</E> Before using <Ref Func="DeclareSynonym"/> in the way of this
## second example,
## one should determine whether the synonym is really needed.
## Perhaps an extra index entry in the documentation would be sufficient.
## <P/>
## When <A>value</A> is actually an attribute then
## <Ref Func="DeclareSynonymAttr"/> should be used;
## this binds also globals variables <C>Set</C><A>name</A> and
## <C>Has</C><A>name</A> for its setter and tester, respectively.
## <P/>
## <Log><![CDATA[
## DeclareSynonymAttr( "IsField", IsDivisionRing and IsCommutative );
## DeclareAttribute( "GeneratorsOfDivisionRing", IsDivisionRing );
## DeclareSynonymAttr( "GeneratorsOfField", GeneratorsOfDivisionRing );
## ]]></Log>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "DeclareSynonym", function( name, value )
BIND_GLOBAL( name, value );
end );
BIND_GLOBAL( "DeclareSynonymAttr", function( name, value )
local nname;
BIND_GLOBAL( name, value );
nname:= "Set";
APPEND_LIST_INTR( nname, name );
BIND_GLOBAL( nname, Setter( value ) );
nname:= "Has";
APPEND_LIST_INTR( nname, name );
BIND_GLOBAL( nname, Tester( value ) );
end );
#############################################################################
##
#V SUBSET_MAINTAINED_INFO
##
## <ManSection>
## <Var Name="SUBSET_MAINTAINED_INFO"/>
##
## <Description>
## is a list of length two.
## At the first position, a list of lists of the form
## <C>[ <A>filtsuper</A>, <A>filtsub</A>, <A>opr</A>, <A>testopr</A>, <A>settopr</A> ]</C>
## is stored,
## which is used for calls of <C>UseSubsetRelation( <A>super</A>, <A>sub</A> )</C>.
## At the second position, a corresponding list of lists of the form
## <C>[ <A>flagsopr</A>, <A>flagssub</A>, <A>rank</A> ]</C>
## is stored, which is used for choosing an appropriate ordering of the
## entries when the lists are enlarged in a call to
## <C>InstallSubsetMaintenance</C>.
## <P/>
## The meaning of the entries is as follows.
## <List>
## <Mark><A>filtsuper</A> </Mark>
## <Item>
## required filter for <A>super</A>,
## </Item>
## <Mark><A>filtsub</A> </Mark>
## <Item>
## required filter for <A>sub</A>,
## </Item>
## <Mark><A>opr</A> </Mark>
## <Item>
## operation whose value is inherited from <A>super</A> to <A>sub</A>,
## </Item>
## <Mark><A>testopr</A> </Mark>
## <Item>
## tester filter of <A>opr</A>,
## </Item>
## <Mark><A>settopr</A> </Mark>
## <Item>
## setter filter of <A>opr</A>,
## </Item>
## <Mark><A>flagsopr</A> </Mark>
## <Item>
## list of those true flags of <A>opr</A>
## that belong neither to categories nor to representations,
## </Item>
## <Mark><A>flagssub</A> </Mark>
## <Item>
## list of those true flags of <A>filtsub</A>
## that belong neither to categories nor to representations,
## </Item>
## <Mark><A>rank</A> </Mark>
## <Item>
## a rational number that denotes the priority of the information
## in the list; <C>SUBSET_MAINTAINED_INFO</C> is sorted according to
## decreasing <A>rank</A> value.
## <!-- We must be careful to choose the right succession of the methods.-->
## <!-- Note that one method may require a property that is acquired using-->
## <!-- another method.-->
## <!-- For that, we give a method a rank that is lower than that of all methods-->
## <!-- that may yield some of the requirements and that is higher than that of-->
## <!-- all methods that require <A>opr</A>;-->
## <!-- if this is not possible then a warning is printed.-->
## <!-- (Maybe the mechanism has to be changed at some time because of this.-->
## <!-- Another reason would be the direct installation of methods for-->
## <!-- <C>UseSubsetRelation</C>, i.e., the ranks of these methods are not affected-->
## <!-- by the code in <C>InstallSubsetMaintenance</C>.) -->
## </Item>
## </List>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "SUBSET_MAINTAINED_INFO", [ [], [] ] );
#############################################################################
##
#O UseSubsetRelation( <super>, <sub> )
##
## <#GAPDoc Label="UseSubsetRelation">
## <ManSection>
## <Oper Name="UseSubsetRelation" Arg='super, sub'/>
##
## <Description>
## Methods for this operation transfer possibly useful information from the
## domain <A>super</A> to its subset <A>sub</A>, and vice versa.
## <P/>
## <Ref Oper="UseSubsetRelation"/> is designed to be called automatically
## whenever substructures of domains are constructed.
## So the methods must be <E>cheap</E>, and the requirements should be as
## sharp as possible!
## <P/>
## To achieve that <E>all</E> applicable methods are executed, all methods for
## this operation except the default method must end with <C>TryNextMethod()</C>.
## This default method deals with the information that is available by
## the calls of <Ref Func="InstallSubsetMaintenance"/> in the &GAP; library.
## <P/>
## <Example><![CDATA[
## gap> g:= Group( (1,2), (3,4), (5,6) );; h:= Group( (1,2), (3,4) );;
## gap> IsAbelian( g ); HasIsAbelian( h );
## true
## false
## gap> UseSubsetRelation( g, h );; HasIsAbelian( h ); IsAbelian( h );
## true
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "UseSubsetRelation", [ IsCollection, IsCollection ] );
InstallMethod( UseSubsetRelation,
"default method that checks maintenances and then returns `true'",
IsIdenticalObj,
[ IsCollection, IsCollection ],
# Make sure that this method is installed with ``real'' rank zero.
- 2 * RankFilter( IsCollection ),
function( super, sub )
local entry;
for entry in SUBSET_MAINTAINED_INFO[1] do
if entry[1]( super ) and entry[2]( sub ) and not entry[4]( sub ) then
entry[5]( sub, entry[3]( super ) );
fi;
od;
return true;
end );
#############################################################################
##
#F InstallSubsetMaintenance( <opr>, <super_req>, <sub_req> )
##
## <#GAPDoc Label="InstallSubsetMaintenance">
## <ManSection>
## <Func Name="InstallSubsetMaintenance" Arg='opr, super_req, sub_req'/>
##
## <Description>
## <A>opr</A> must be a property or an attribute.
## The call of <Ref Func="InstallSubsetMaintenance"/> has the effect that
## for a domain <M>D</M> in the filter <A>super_req</A>,
## and a domain <M>S</M> in the filter <A>sub_req</A>,
## the call <C>UseSubsetRelation</C><M>( D, S )</M>
## (see <Ref Func="UseSubsetRelation"/>)
## sets a known value of <A>opr</A> for <M>D</M> as value of <A>opr</A> also
## for <M>S</M>.
## A typical example for which <Ref Func="InstallSubsetMaintenance"/> is
## applied is given by <A>opr</A> <C>= IsFinite</C>,
## <A>super_req</A> <C>= IsCollection and IsFinite</C>,
## and <A>sub_req</A> <C>= IsCollection</C>.
## <P/>
## If <A>opr</A> is a property and the filter <A>super_req</A> lies in the
## filter <A>opr</A> then we can use also the following inverse implication.
## If <M>D</M> is in the filter whose intersection with <A>opr</A> is
## <A>super_req</A> and if <M>S</M> is in the filter <A>sub_req</A>,
## <M>S</M> is a subset of <M>D</M>, and the value of <A>opr</A> for
## <M>S</M> is <K>false</K> then the value of <A>opr</A> for <M>D</M> is
## also <K>false</K>.
## <!-- This is implemented only for the case <A>super_req</A> = <A>opr</A>
## and <A>sub_req</A>.-->
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "InstallSubsetMaintenance",
function( operation, super_req, sub_req )
local setter, # setter filter of `operation'
tester, # tester filter of `operation'
upper,
lower,
attrprop, # id `operation' an attribute/property?
rank,
filtssub, # property and attribute flags of `sub_req'
filtsopr, # property and attribute flags of `operation'
triple, # loop over `SUBSET_MAINTAINED_INFO[2]'
req,
flag,
filt1,
filt2,
i;
setter:= Setter( operation );
tester:= Tester( operation );
# Are there methods that may give us some of the requirements?
upper:= SUM_FLAGS;
# (We must not call `SUBTR_SET' here because the lists types may be
# not yet defined.)
filtssub:= [];
for flag in TRUES_FLAGS( FLAGS_FILTER( sub_req ) ) do
if not flag in CATS_AND_REPS then
ADD_LIST_DEFAULT( filtssub, flag );
fi;
od;
for triple in SUBSET_MAINTAINED_INFO[2] do
req:= SHALLOW_COPY_OBJ( filtssub );
INTER_SET( req, triple[1] );
if LEN_LIST( req ) <> 0 and triple[3] < upper then
upper:= triple[3];
fi;
od;
# Are there methods that require `operation'?
lower:= 0;
attrprop:= true;
filt1:= FLAGS_FILTER( operation );
if filt1 = false then
# `operation' is an attribute.
filt1:= FLAGS_FILTER( tester );
else
# Special treatment of categories, representations (makes sense?),
# and filters created by `NewFilter'.
if FLAG2_FILTER( operation ) = 0 then
attrprop:= false;
fi;
fi;
# (We must not call `SUBTR_SET' here because the lists types may be
# not yet defined.)
filtsopr:= [];
for flag in TRUES_FLAGS( filt1 ) do
if not flag in CATS_AND_REPS then
ADD_LIST_DEFAULT( filtsopr, flag );
fi;
od;
for triple in SUBSET_MAINTAINED_INFO[2] do
req:= SHALLOW_COPY_OBJ( filtsopr );
INTER_SET( req, triple[2] );
if LEN_LIST( req ) <> 0 and lower < triple[3] then
lower:= triple[3];
fi;
od;
# Compute the ``rank'' of the maintenance.
# (Do we have a cycle?)
if upper <= lower then
Print( "#W warning: cycle in `InstallSubsetMaintenance'\n" );
rank:= lower;
else
rank:= ( upper + lower ) / 2;
fi;
filt1:= IsCollection and Tester( super_req ) and super_req and tester;
filt2:= IsCollection and Tester( sub_req ) and sub_req;
# Update the info list.
i:= LEN_LIST( SUBSET_MAINTAINED_INFO[2] );
while 0 < i and SUBSET_MAINTAINED_INFO[2][i][3] < rank do
SUBSET_MAINTAINED_INFO[1][ i+1 ]:= SUBSET_MAINTAINED_INFO[1][ i ];
SUBSET_MAINTAINED_INFO[2][ i+1 ]:= SUBSET_MAINTAINED_INFO[2][ i ];
i:= i-1;
od;
SUBSET_MAINTAINED_INFO[2][ i+1 ]:= [ filtsopr, filtssub, rank ];
if attrprop then
SUBSET_MAINTAINED_INFO[1][ i+1 ]:=
[ filt1, filt2, operation, tester, setter ];
else
SUBSET_MAINTAINED_INFO[1][ i+1 ]:=
[ filt1, filt2, operation, operation,
function( sub, val )
SetFeatureObj( sub, operation, val );
end ];
fi;
#T missing in new implementation!
# # Install the method.
# if FLAGS_FILTER( operation ) <> false
# and IS_EQUAL_FLAGS( FLAGS_FILTER( operation and sub_req ),
# FLAGS_FILTER( super_req ) ) then
# InstallMethod( UseSubsetRelation, infostring, IsIdenticalObj,
# [ sub_req, sub_req ], 0,
# function( super, sub )
# if tester( sub ) and not operation( sub ) then
# setter( super, false );
# fi;
# TryNextMethod();
# end );
# fi;
end );
#############################################################################
##
#V ISOMORPHISM_MAINTAINED_INFO
##
## <ManSection>
## <Var Name="ISOMORPHISM_MAINTAINED_INFO"/>
##
## <Description>
## is a list of lists of the form
## <C>[ <A>filtsold</A>, <A>filtsnew</A>, <A>opr</A>, <A>testopr</A>, <A>settopr</A>, <A>old_req</A>,
## <A>new-req</A> ]</C>
## which is used for calls of <C>UseIsomorphismRelation( <A>old</A>, <A>new</A> )</C>.
## This list is enlarged by calls to <C>InstallIsomorphismMaintenance</C>.
## <P/>
## The meaning of the entries is as follows.
## <List>
## <Mark><A>filtsold</A> </Mark>
## <Item>
## required filter for <A>old</A>,
## </Item>
## <Mark><A>filtsnew</A> </Mark>
## <Item>
## required filter for <A>new</A>,
## </Item>
## <Mark><A>opr</A> </Mark>
## <Item>
## operation whose value is inherited from <A>old</A> to <A>new</A>,
## </Item>
## <Mark><A>testopr</A> </Mark>
## <Item>
## tester filter of <A>opr</A>,
## </Item>
## <Mark><A>settopr</A> </Mark>
## <Item>
## setter filter of <A>opr</A>,
## </Item>
## <Mark><A>old-req</A> </Mark>
## <Item>
## requirements for <A>old</A> in the <C>InstallIsomorphismMaintenance</C> call,
## </Item>
## <Mark><A>new-req</A> </Mark>
## <Item>
## requirements for <A>new</A> in the <C>InstallIsomorphismMaintenance</C> call.
## </Item>
## </List>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "ISOMORPHISM_MAINTAINED_INFO", [] );
#############################################################################
##
#O UseIsomorphismRelation( <old>, <new> )
##
## <#GAPDoc Label="UseIsomorphismRelation">
## <ManSection>
## <Oper Name="UseIsomorphismRelation" Arg='old, new'/>
##
## <Description>
## Methods for this operation transfer possibly useful information from the
## domain <A>old</A> to the isomorphic domain <A>new</A>.
## <P/>
## <Ref Oper="UseIsomorphismRelation"/> is designed to be called
## automatically whenever isomorphic structures of domains are constructed.
## So the methods must be <E>cheap</E>, and the requirements should be as
## sharp as possible!
## <P/>
## To achieve that <E>all</E> applicable methods are executed, all methods
## for this operation except the default method must end with a call to
## <Ref Func="TryNextMethod"/>.
## This default method deals with the information that is available by
## the calls of <Ref Func="InstallIsomorphismMaintenance"/> in the &GAP;
## library.
## <P/>
## <Example><![CDATA[
## gap> g:= Group( (1,2) );; h:= Group( [ [ -1 ] ] );;
## gap> Size( g ); HasSize( h );
## 2
## false
## gap> UseIsomorphismRelation( g, h );; HasSize( h ); Size( h );
## true
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "UseIsomorphismRelation", [ IsCollection, IsCollection ] );
InstallMethod( UseIsomorphismRelation,
"default method that checks maintenances and then returns `true'",
[ IsCollection, IsCollection ],
# Make sure that this method is installed with ``real'' rank zero.
- 2 * RankFilter( IsCollection ),
function( old, new )
local entry;
for entry in ISOMORPHISM_MAINTAINED_INFO do
if entry[1]( old ) and entry[2]( new ) and not entry[4]( new ) then
entry[5]( new, entry[3]( old ) );
fi;
od;
return true;
end );
#############################################################################
##
#F InstallIsomorphismMaintenanceFunction( <func> )
##
## <ManSection>
## <Func Name="InstallIsomorphismMaintenanceFunction" Arg='func'/>
##
## <Description>
## <C>InstallIsomorphismMaintenanceFunction</C> installs <A>func</A>, so that
## <C><A>func</A>( <A>filtsold</A>, <A>filtsnew</A>, <A>opr</A>, <A>testopr</A>, <A>settopr</A>, <A>old_req</A>,
## <A>new-req</A> )</C> is called for each isomorphism maintenance.
## More precisely, <A>func</A> is called for each entry in the global list
## <C>ISOMORPHISM_MAINTAINED_INFO</C>, also to those that are entered into this
## list after the installation of <A>func</A>.
## (The mechanism is the same as for attributes, which is installed in the
## file <C>lib/oper.g</C>.)
## </Description>
## </ManSection>
##
BIND_GLOBAL( "ISOM_MAINT_FUNCS", [] );
BIND_GLOBAL( "InstallIsomorphismMaintenanceFunction", function( func )
local entry;
for entry in ISOMORPHISM_MAINTAINED_INFO do
CallFuncList( func, entry );
od;
ADD_LIST( ISOM_MAINT_FUNCS, func );
end );
BIND_GLOBAL( "RUN_ISOM_MAINT_FUNCS",
function( arglist )
local func;
for func in ISOM_MAINT_FUNCS do
CallFuncList( func, arglist );
od;
ADD_LIST( ISOMORPHISM_MAINTAINED_INFO, arglist );
end );
#############################################################################
##
#F InstallIsomorphismMaintenance( <opr>, <old_req>, <new_req> )
##
## <#GAPDoc Label="InstallIsomorphismMaintenance">
## <ManSection>
## <Func Name="InstallIsomorphismMaintenance" Arg='opr, old_req, new_req'/>
##
## <Description>
## <A>opr</A> must be a property or an attribute.
## The call of <Ref Func="InstallIsomorphismMaintenance"/> has the effect
## that for a domain <M>D</M> in the filter <A>old_req</A>,
## and a domain <M>E</M> in the filter <A>new_req</A>,
## the call <C>UseIsomorphismRelation</C><M>( D, E )</M>
## (see <Ref Func="UseIsomorphismRelation"/>)
## sets a known value of <A>opr</A> for <M>D</M> as value of <A>opr</A> also
## for <M>E</M>.
## A typical example for which <Ref Func="InstallIsomorphismMaintenance"/>
## is applied is given by <A>opr</A> <C>= Size</C>,
## <A>old_req</A> <C>= IsCollection</C>,
## and <A>new_req</A> <C>= IsCollection</C>.
## <!-- Up to now, there are no dependencies between the maintenances-->
## <!-- (contrary to the case of subset maintenances),-->
## <!-- so we do not take care of the succession.-->
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "InstallIsomorphismMaintenance",
function( opr, old_req, new_req )
local tester;
tester:= Tester( opr );
RUN_ISOM_MAINT_FUNCS(
[ IsCollection and Tester( old_req ) and old_req and tester,
IsCollection and Tester( new_req ) and new_req,
opr,
tester,
Setter( opr ),
old_req,
new_req ] );
end );
#############################################################################
##
#V FACTOR_MAINTAINED_INFO
##
## <ManSection>
## <Var Name="FACTOR_MAINTAINED_INFO"/>
##
## <Description>
## is a list of lists of the form
## <C>[ <A>filtsnum</A>, <A>filtsden</A>, <A>filtsfac</A>, <A>opr</A>, <A>testopr</A>, <A>settopr</A> ]</C>
## which is used for calls of <C>UseFactorRelation( <A>num</A>, <A>den</A>, <A>fac</A> )</C>.
## This list is enlarged by calls to <C>InstallFactorMaintenance</C>.
## <P/>
## The meaning of the entries is as follows.
## <List>
## <Mark><A>filtsnum</A> </Mark>
## <Item>
## required filter for <A>num</A>,
## </Item>
## <Mark><A>filtsden</A> </Mark>
## <Item>
## required filter for <A>den</A>,
## </Item>
## <Mark><A>filtsfac</A> </Mark>
## <Item>
## required filter for <A>fac</A>,
## </Item>
## <Mark><A>opr</A> </Mark>
## <Item>
## operation whose value is inherited from <A>num</A> to <A>fac</A>,
## </Item>
## <Mark><A>testopr</A> </Mark>
## <Item>
## tester filter of <A>opr</A>,
## </Item>
## <Mark><A>settopr</A> </Mark>
## <Item>
## setter filter of <A>opr</A>.
## </Item>
## </List>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "FACTOR_MAINTAINED_INFO", [] );
#############################################################################
##
#O UseFactorRelation( <numer>, <denom>, <factor> )
##
## <#GAPDoc Label="UseFactorRelation">
## <ManSection>
## <Oper Name="UseFactorRelation" Arg='numer, denom, factor'/>
##
## <Description>
## Methods for this operation transfer possibly useful information from the
## domain <A>numer</A> or its subset <A>denom</A> to the domain
## <A>factor</A> that is isomorphic to the factor of <A>numer</A> by
## <A>denom</A>, and vice versa.
## <A>denom</A> may be <K>fail</K>, for example if <A>factor</A> is just
## known to be a factor of <A>numer</A> but <A>denom</A> is not available as
## a &GAP; object;
## in this case those factor relations are used that are installed without
## special requirements for <A>denom</A>.
## <P/>
## <Ref Oper="UseFactorRelation"/> is designed to be called automatically
## whenever factor structures of domains are constructed.
## So the methods must be <E>cheap</E>, and the requirements should be as
## sharp as possible!
## <P/>
## To achieve that <E>all</E> applicable methods are executed, all methods
## for this operation except the default method must end with a call to
## <Ref Func="TryNextMethod"/>.
## This default method deals with the information that is available by
## the calls of <Ref Func="InstallFactorMaintenance"/> in the &GAP; library.
## <P/>
## <Example><![CDATA[
## gap> g:= Group( (1,2,3,4), (1,2) );; h:= Group( (1,2,3), (1,2) );;
## gap> IsSolvableGroup( g ); HasIsSolvableGroup( h );
## true
## false
## gap> UseFactorRelation(g, Subgroup( g, [ (1,2)(3,4), (1,3)(2,4) ] ), h);;
## gap> HasIsSolvableGroup( h ); IsSolvableGroup( h );
## true
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "UseFactorRelation",
[ IsCollection, IsObject, IsCollection ] );
InstallMethod( UseFactorRelation,
"default method that checks maintenances and then returns `true'",
true,
[ IsCollection, IsObject, IsCollection ],
# Make sure that this method is installed with ``real'' rank zero.
- 2 * RankFilter( IsCollection )-RankFilter(IsObject),
function( num, den, fac )
local entry;
for entry in FACTOR_MAINTAINED_INFO do
if entry[1]( num ) and entry[2]( den ) and entry[3]( fac )
and not entry[5]( fac ) then
entry[6]( fac, entry[4]( num ) );
fi;
od;
return true;
end );
#############################################################################
##
#F InstallFactorMaintenance( <opr>, <numer_req>, <denom_req>, <factor_req> )
##
## <#GAPDoc Label="InstallFactorMaintenance">
## <ManSection>
## <Func Name="InstallFactorMaintenance"
## Arg='opr, numer_req, denom_req, factor_req'/>
##
## <Description>
## <A>opr</A> must be a property or an attribute.
## The call of <Ref Func="InstallFactorMaintenance"/> has the effect that
## for collections <M>N</M>, <M>D</M>, <M>F</M> in the filters
## <A>numer_req</A>, <A>denom_req</A>, and <A>factor_req</A>, respectively,
## the call <C>UseFactorRelation</C><M>( N, D, F )</M>
## (see <Ref Func="UseFactorRelation"/>)
## sets a known value of <A>opr</A> for <M>N</M> as value of <A>opr</A> also
## for <M>F</M>.
## A typical example for which <Ref Func="InstallFactorMaintenance"/> is
## applied is given by <A>opr</A> <C>= IsFinite</C>,
## <A>numer_req</A> <C>= IsCollection and IsFinite</C>,
## <A>denom_req</A> <C>= IsCollection</C>,
## and <A>factor_req</A> <C>= IsCollection</C>.
## <P/>
## For the other direction, if <A>numer_req</A> involves the filter
## <A>opr</A> then a known <K>false</K> value of <A>opr</A> for <M>F</M>
## implies a <K>false</K> value for <M>D</M> provided that <M>D</M> lies in
## the filter obtained from <A>numer_req</A> by removing <A>opr</A>.
## <P/>
## Note that an implication of a factor relation holds in particular for the
## case of isomorphisms.
## So one need <E>not</E> install an isomorphism maintained method when
## a factor maintained method is already installed.
## For example, <Ref Func="UseIsomorphismRelation"/>
## will transfer a known <Ref Prop="IsFinite"/> value because of the
## installed factor maintained method.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "InstallFactorMaintenance",
function( opr, numer_req, denom_req, factor_req )
local tester;
# Information that is maintained under taking factors
# is especially maintained under isomorphisms.
InstallIsomorphismMaintenance( opr, numer_req, factor_req );
tester:= Tester( opr );
ADD_LIST( FACTOR_MAINTAINED_INFO,
[ IsCollection and Tester( numer_req ) and numer_req and tester,
Tester( denom_req ) and denom_req,
IsCollection and Tester( factor_req ) and factor_req,
opr,
tester,
Setter( opr ) ] );
#T not yet available in the new implementation
# if FLAGS_FILTER( opr ) <> false
# and IS_EQUAL_FLAGS( FLAGS_FILTER( opr and factor_req ),
# FLAGS_FILTER( numer_req ) ) then
# InstallMethod( UseFactorRelation, infostring, IsFamFamX,
# [ factor_req, denom_req, factor_req ], 0,
# function( numer, denom, factor )
# if tester( factor ) and not opr( factor ) then
# setter( numer, false );
# fi;
# TryNextMethod();
# end );
# fi;
end );
#############################################################################
##
#O Iterator( <listorcoll> ) . . . . . . . iterator for a list or collection
##
## <#GAPDoc Label="Iterator">
## <ManSection>
## <Oper Name="Iterator" Arg='listorcoll'/>
## <Filt Name="IsStandardIterator" Arg='listorcoll'/>
##
## <Description>
## Iterators provide a possibility to loop over the elements of a
## (countable) collection or list <A>listorcoll</A>, without repetition.
## For many collections <M>C</M>,
## an iterator of <M>C</M> need not store all elements of <M>C</M>,
## for example it is possible to construct an iterator of some infinite
## domains, such as the field of rational numbers.
## <P/>
## <Ref Func="Iterator"/> returns a mutable <E>iterator</E> <M>iter</M> for
## its argument.
## If this argument is a list (which may contain holes),
## then <M>iter</M> iterates over the elements (but not the holes) of this
## list in the same order (see <Ref Func="IteratorList"/> for details).
## If this argument is a collection but not a list then <M>iter</M> iterates
## over the elements of this collection in an unspecified order,
## which may change for repeated calls of <Ref Func="Iterator"/>.
## Because iterators returned by <Ref Func="Iterator"/> are mutable
## (see <Ref Sect="Mutability and Copyability"/>),
## each call of <Ref Func="Iterator"/> for the same argument returns a
## <E>new</E> iterator.
## Therefore <Ref Func="Iterator"/> is not an attribute
## (see <Ref Sect="Attributes"/>).
## <P/>
## The only operations for iterators are <Ref Func="IsDoneIterator"/>,
## <Ref Func="NextIterator"/>, and <Ref Func="ShallowCopy"/>.
## In particular, it is only possible to access the next element of the
## iterator with <Ref Func="NextIterator"/> if there is one,
## and this can be checked with <Ref Func="IsDoneIterator"/>
## For an iterator <M>iter</M>, <Ref Func="ShallowCopy"/> returns a
## mutable iterator <M>new</M> that iterates over the remaining elements
## independent of <M>iter</M>;
## the results of <Ref Func="IsDoneIterator"/> for <M>iter</M> and
## <M>new</M> are equal,
## and if <M>iter</M> is mutable then also the results of
## <Ref Func="NextIterator"/> for <M>iter</M> and <M>new</M> are equal;
## note that <C>=</C> is not defined for iterators,
## so the equality of two iterators cannot be checked with <C>=</C>.
## <P/>
## When <Ref Func="Iterator"/> is called for a <E>mutable</E> collection
## <M>C</M> then it is not defined whether <M>iter</M> respects changes to
## <M>C</M> occurring after the construction of <M>iter</M>,
## except if the documentation explicitly promises a certain behaviour.
## The latter is the case if the argument is a mutable list
## (see <Ref Func="IteratorList"/> for subtleties in this case).
## <P/>
## It is possible to have <K>for</K>-loops run over mutable iterators
## instead of lists.
## <P/>
## In some situations, one can construct iterators with a special
## succession of elements,
## see <Ref Func="IteratorByBasis"/> for the possibility to loop over
## the elements of a vector space w.r.t. a given basis.
## <!-- (also for perm. groups, w.r.t. a given stabilizer chain?)-->
## <P/>
## For lists, <Ref Func="Iterator"/> is implemented by
## <Ref Func="IteratorList"/>.
## For collections <M>C</M> that are not lists, the default method is
## <C>IteratorList( Enumerator( </C><M>C</M><C> ) )</C>.
## Better methods depending on <M>C</M> should be provided if possible.
## <P/>
## For random access to the elements of a (possibly infinite) collection,
## <E>enumerators</E> are used.
## See <Ref Sect="Enumerators"/> for the facility to compute a list
## from <M>C</M>, which provides a (partial) mapping from <M>C</M> to the
## positive integers.
## <P/>
## The filter <Ref Filt="IsStandardIterator"/> means that the iterator is
## implemented as a component object and has components <C>IsDoneIterator</C>
## and <C>NextIterator</C> which are bound to the methods of the operations of
## the same name for this iterator.
## <!-- (This is used to avoid overhead when looping over such iterators.) -->
## <!-- We wanted to admit an iterator as first argument of <C>Filtered</C>,-->
## <!-- <C>First</C>, <C>ForAll</C>, <C>ForAny</C>, <C>Number</C>.-->
## <!-- This is not yet implemented.-->
## <!-- (Note that the iterator is changed in the call,-->
## <!-- so the meaning of the operations would be slightly abused,-->
## <!-- or we must define that these operations first make a shallow copy.)-->
## <!-- (Additionally, the unspecified order of the elements makes it-->
## <!-- difficult to define what <C>First</C> and <C>Filtered</C> means for an iterator.)-->
## <Example><![CDATA[
## gap> iter:= Iterator( GF(5) );
## <iterator>
## gap> l:= [];;
## gap> for i in iter do Add( l, i ); od; l;
## [ 0*Z(5), Z(5)^0, Z(5), Z(5)^2, Z(5)^3 ]
## gap> iter:= Iterator( [ 1, 2, 3, 4 ] );; l:= [];;
## gap> for i in iter do
## > new:= ShallowCopy( iter );
## > for j in new do Add( l, j ); od;
## > od; l;
## [ 2, 3, 4, 3, 4, 4 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareFilter("IsStandardIterator");
DeclareOperation( "Iterator", [ IsListOrCollection ] );
#############################################################################
##
#O IteratorSorted( <C> ) . . . . . . . . . . . set iterator for a collection
#O IteratorSorted( <list> ) . . . . . . . . . . . . set iterator for a list
##
## <#GAPDoc Label="IteratorSorted">
## <ManSection>
## <Oper Name="IteratorSorted" Arg='listorcoll'/>
##
## <Description>
## <Ref Func="IteratorSorted"/> returns a mutable iterator.
## The argument must be a collection or a list that is not
## necessarily dense but whose elements lie in the same family
## (see <Ref Sect="Families"/>).
## It loops over the different elements in sorted order.
## <P/>
## For a collection <M>C</M> that is not a list, the generic method is
## <C>IteratorList( EnumeratorSorted( </C><A>C</A><C> ) )</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "IteratorSorted", [ IsListOrCollection ] );
#############################################################################
##
#C IsIterator( <obj> ) . . . . . . . . . . test if an object is an iterator
##
## <#GAPDoc Label="IsIterator">
## <ManSection>
## <Filt Name="IsIterator" Arg='obj' Type='Category'/>
##
## <Description>
## Every iterator lies in the category <C>IsIterator</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsIterator", IsObject );
#############################################################################
##
#O IsDoneIterator( <iter> ) . . . . . . . test if an iterator is exhausted
##
## <#GAPDoc Label="IsDoneIterator">
## <ManSection>
## <Oper Name="IsDoneIterator" Arg='iter'/>
##
## <Description>
## If <A>iter</A> is an iterator for the list or collection <M>C</M> then
## <C>IsDoneIterator( <A>iter</A> )</C> is <K>true</K> if all elements of
## <M>C</M> have been returned already by <C>NextIterator( <A>iter</A> )</C>,
## and <K>false</K> otherwise.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "IsDoneIterator", [ IsIterator ] );
#############################################################################
##
#O NextIterator( <iter> ) . . . . . . . . . . next element from an iterator
##
## <#GAPDoc Label="NextIterator">
## <ManSection>
## <Oper Name="NextIterator" Arg='iter'/>
##
## <Description>
## Let <A>iter</A> be a mutable iterator for the list or collection <M>C</M>.
## If <C>IsDoneIterator( <A>iter</A> )</C> is <K>false</K> then
## <Ref Func="NextIterator"/> is applicable to <A>iter</A>,
## and the result is the next element of <M>C</M>,
## according to the succession defined by <A>iter</A>.
## <P/>
## If <C>IsDoneIterator( <A>iter</A> )</C> is <K>true</K> then it is not
## defined what happens when <Ref Func="NextIterator"/> is called for
## <A>iter</A>;
## that is, it may happen that an error is signalled or that something
## meaningless is returned, or even that &GAP; crashes.
## <P/>
## <Example><![CDATA[
## gap> iter:= Iterator( [ 1, 2, 3, 4 ] );
## <iterator>
## gap> sum:= 0;;
## gap> while not IsDoneIterator( iter ) do
## > sum:= sum + NextIterator( iter );
## > od;
## gap> IsDoneIterator( iter ); sum;
## true
## 10
## gap> ir:= Iterator( Rationals );;
## gap> l:= [];; for i in [1..20] do Add( l, NextIterator( ir ) ); od; l;
## [ 0, 1, -1, 1/2, 2, -1/2, -2, 1/3, 2/3, 3/2, 3, -1/3, -2/3, -3/2, -3,
## 1/4, 3/4, 4/3, 4, -1/4 ]
## gap> for i in ir do
## > if DenominatorRat( i ) > 10 then break; fi;
## > od;
## gap> i;
## 1/11
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "NextIterator", [ IsIterator and IsMutable ] );
#############################################################################
##
#F TrivialIterator( <elm> )
##
## <#GAPDoc Label="TrivialIterator">
## <ManSection>
## <Func Name="TrivialIterator" Arg='elm'/>
##
## <Description>
## is a mutable iterator for the collection <C>[ <A>elm</A> ]</C> that
## consists of exactly one element <A>elm</A>
## (see <Ref Func="IsTrivial"/>).
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "TrivialIterator" );
#############################################################################
##
#F IteratorByFunctions( <record> )
##
## <#GAPDoc Label="IteratorByFunctions">
## <ManSection>
## <Func Name="IteratorByFunctions" Arg='record'/>
##
## <Description>
## <Ref Func="IteratorByFunctions"/> returns a (mutable) iterator
## <A>iter</A> for which <Ref Func="NextIterator"/>,
## <Ref Func="IsDoneIterator"/>,
## and <Ref Func="ShallowCopy"/>
## are computed via prescribed functions.
## <P/>
## Let <A>record</A> be a record with at least the following components.
## <List>
## <Mark><C>NextIterator</C></Mark>
## <Item>
## a function taking one argument <A>iter</A>,
## which returns the next element of <A>iter</A>
## (see <Ref Func="NextIterator"/>);
## for that, the components of <A>iter</A> are changed,
## </Item>
## <Mark><C>IsDoneIterator</C></Mark>
## <Item>
## a function taking one argument <A>iter</A>,
## which returns the <Ref Func="IsDoneIterator"/> value of <A>iter</A>,
## </Item>
## <Mark><C>ShallowCopy</C></Mark>
## <Item>
## a function taking one argument <A>iter</A>,
## which returns a record for which <Ref Func="IteratorByFunctions"/>
## can be called in order to create a new iterator that is independent
## of <A>iter</A> but behaves like <A>iter</A> w.r.t. the operations
## <Ref Func="NextIterator"/> and <Ref Func="IsDoneIterator"/>.
## </Item>
## <Mark><C>ViewObj</C> and <C>PrintObj</C></Mark>
## <Item>
## two functions that print what one wants to be printed when
## <C>View( <A>iter</A> )</C> or <C>Print( <A>item</A> )</C> is called
## (see <Ref Sect="View and Print"/>),
## if the <C>ViewObj</C> component is missing then the <C>PrintObj</C>
## method is used as a default.
## </Item>
## </List>
## Further (data) components may be contained in <A>record</A> which can be
## used by these function.
## <P/>
## <Ref Func="IteratorByFunctions"/> does <E>not</E> make a shallow copy of
## <A>record</A>, this record is changed in place
## (see Section <Ref Sect="Creating Objects"/>).
## <P/>
## Iterators constructed with <Ref Func="IteratorByFunctions"/> are in the
## filter <Ref Filt="IsStandardIterator"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "IteratorByFunctions" );
#############################################################################
##
#P IsEmpty( <C> ) . . . . . . . . . . . . . . test if a collection is empty
#P IsEmpty( <list> ) . . . . . . . . . . . . . test if a collection is empty
##
## <#GAPDoc Label="IsEmpty">
## <ManSection>
## <Prop Name="IsEmpty" Arg='listorcoll'/>
##
## <Description>
## <Ref Func="IsEmpty"/> returns <K>true</K> if the collection or list
## <A>listorcoll</A> is <E>empty</E> (that is it contains no elements),
## and <K>false</K> otherwise.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsEmpty", IsListOrCollection );
#############################################################################
##
#P IsTrivial( <C> ) . . . . . . . . . . . . test if a collection is trivial
##
## <#GAPDoc Label="IsTrivial">
## <ManSection>
## <Prop Name="IsTrivial" Arg='C'/>
##
## <Description>
## <Ref Prop="IsTrivial"/> returns <K>true</K> if the collection <A>C</A>
## consists of exactly one element.
## <!-- 1996/08/08 M.Schönert is this a sensible definition?-->
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsTrivial", IsCollection );
InstallFactorMaintenance( IsTrivial,
IsCollection and IsTrivial, IsObject, IsCollection );
#############################################################################
##
#P IsNonTrivial( <C> ) . . . . . . . . . test if a collection is nontrivial
##
## <#GAPDoc Label="IsNonTrivial">
## <ManSection>
## <Prop Name="IsNonTrivial" Arg='C'/>
##
## <Description>
## <Ref Func="IsNonTrivial"/> returns <K>true</K> if the collection <A>C</A>
## is empty or consists of at least two elements
## (see <Ref Func="IsTrivial"/>).
## <P/>
## <!-- I need this to distinguish trivial rings-with-one from fields!-->
## <!-- (indication to introduce antifilters?)-->
## <!-- 1996/08/08 M.Schönert is this a sensible definition?-->
## <Example><![CDATA[
## gap> IsEmpty( [] ); IsEmpty( [ 1 .. 100 ] ); IsEmpty( Group( (1,2,3) ) );
## true
## false
## false
## gap> IsFinite( [ 1 .. 100 ] ); IsFinite( Integers );
## true
## false
## gap> IsTrivial( Integers ); IsTrivial( Group( () ) );
## false
## true
## gap> IsNonTrivial( Integers ); IsNonTrivial( Group( () ) );
## true
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsNonTrivial", IsCollection );
#############################################################################
##
#P IsFinite( <C> ) . . . . . . . . . . . . . test if a collection is finite
##
## <#GAPDoc Label="IsFinite">
## <ManSection>
## <Prop Name="IsFinite" Arg='C'/>
##
## <Description>
## <Index Subkey="for a list or collection">finiteness test</Index>
## <Ref Func="IsFinite"/> returns <K>true</K> if the collection <A>C</A>
## is finite, and <K>false</K> otherwise.
## <P/>
## The default method for <Ref Func="IsFinite"/> checks the size
## (see <Ref Func="Size"/>) of <A>C</A>.
## <P/>
## Methods for <Ref Func="IsFinite"/> may call <Ref Func="Size"/>,
## but methods for <Ref Func="Size"/> must <E>not</E> call
## <Ref Func="IsFinite"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsFinite", IsCollection );
InstallSubsetMaintenance( IsFinite,
IsCollection and IsFinite, IsCollection );
InstallFactorMaintenance( IsFinite,
IsCollection and IsFinite, IsObject, IsCollection );
InstallTrueMethod( IsFinite, IsTrivial );
#############################################################################
##
#P IsWholeFamily( <C> ) . . test if a collection contains the whole family
##
## <#GAPDoc Label="IsWholeFamily">
## <ManSection>
## <Prop Name="IsWholeFamily" Arg='C'/>
##
## <Description>
## <Ref Prop="IsWholeFamily"/> returns <K>true</K> if the collection
## <A>C</A> contains the whole family (see <Ref Sect="Families"/>)
## of its elements.
## <P/>
## <Example><![CDATA[
## gap> IsWholeFamily( Integers )
## > ; # all rationals and cyclotomics lie in the family
## false
## gap> IsWholeFamily( Integers mod 3 )
## > ; # all finite field elements in char. 3 lie in this family
## false
## gap> IsWholeFamily( Integers mod 4 );
## true
## gap> IsWholeFamily( FreeGroup( 2 ) );
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsWholeFamily", IsCollection );
#############################################################################
##
#A Size( <C> ) . . . . . . . . . . . . . . . . . . . . size of a collection
#A Size( <list> ) . . . . . . . . . . . . . . . . . . size of a collection
##
## <#GAPDoc Label="Size">
## <ManSection>
## <Attr Name="Size" Arg='listorcoll'/>
##
## <Description>
## <Index Subkey="of a list or collection">size</Index>
## <Index Subkey="of a list, collection or domain">order</Index>
## <Ref Attr="Size"/> returns the size of the list or collection
## <A>listorcoll</A>, which is either an integer or <Ref Var="infinity"/>.
## If the argument is a list then the result is its length
## (see <Ref Func="Length"/>).
## <P/>
## The default method for <Ref Attr="Size"/> checks the length of an
## enumerator of <A>listorcoll</A>.
## <P/>
## Methods for <Ref Prop="IsFinite"/> may call <Ref Attr="Size"/>,
## but methods for <Ref Attr="Size"/> must not call <Ref Prop="IsFinite"/>.
## <P/>
## <Example><![CDATA[
## gap> Size( [1,2,3] ); Size( Group( () ) ); Size( Integers );
## 3
## 1
## infinity
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "Size", IsListOrCollection );
InstallIsomorphismMaintenance( Size, IsCollection, IsCollection );
#############################################################################
##
#A Representative( <C> ) . . . . . . . . . . . . one element of a collection
##
## <#GAPDoc Label="Representative">
## <ManSection>
## <Attr Name="Representative" Arg='C'/>
##
## <Description>
## <Ref Attr="Representative"/> returns a <E>representative</E>
## of the collection <A>C</A>.
## <P/>
## Note that <Ref Attr="Representative"/> is free in choosing
## a representative if there are several elements in <A>C</A>.
## It is not even guaranteed that <Ref Attr="Representative"/> returns
## the same representative if it is called several times for one collection.
## The main difference between <Ref Attr="Representative"/> and
## <Ref Func="Random" Label="for a list or collection"/>
## is that <Ref Attr="Representative"/> is free
## to choose a value that is cheap to compute,
## while <Ref Func="Random" Label="for a list or collection"/>
## must make an effort to randomly distribute its answers.
## <P/>
## If <A>C</A> is a domain then there are methods for
## <Ref Attr="Representative"/> that try
## to fetch an element from any known generator list of <A>C</A>,
## see <Ref Chap="Domains and their Elements"/>.
## Note that <Ref Attr="Representative"/> does not try to <E>compute</E>
## generators of <A>C</A>,
## thus <Ref Attr="Representative"/> may give up and signal an error
## if <A>C</A> has no generators stored at all.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "Representative", IsListOrCollection );
#############################################################################
##
#A RepresentativeSmallest( <C> ) . . . . . smallest element of a collection
##
## <#GAPDoc Label="RepresentativeSmallest">
## <ManSection>
## <Attr Name="RepresentativeSmallest" Arg='C'/>
##
## <Description>
## <Index Subkey="of a list or collection">representative</Index>
## returns the smallest element in the collection <A>C</A>, w.r.t. the
## ordering <Ref Func="\<"/>.
## While the operation defaults to comparing all elements,
## better methods are installed for some collections.
## <P/>
## <Example><![CDATA[
## gap> Representative( Rationals );
## 0
## gap> Representative( [ -1, -2 .. -100 ] );
## -1
## gap> RepresentativeSmallest( [ -1, -2 .. -100 ] );
## -100
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "RepresentativeSmallest", IsListOrCollection );
#############################################################################
##
#O Random( <C> ) . . . . . . . . . . random element of a list or collection
#O Random( <list> ) . . . . . . . . random element of a list or collection
#O Random( <from>, <to> )
##
## <#GAPDoc Label="Random:coll">
## <ManSection>
## <Oper Name="Random" Arg='listorcoll' Label="for a list or collection"/>
## <Oper Name="Random" Arg='from, to' Label="for lower and upper bound"/>
##
## <Description>
## <!-- to get this on top of results for ?Random -->
## <Index Key="Random"><Ref Func="Random"
## Label="for a list or collection"/></Index>
## <Ref Oper="Random" Label="for a list or collection"/> returns a
## (pseudo-)random element of the list or collection <A>listorcoll</A>.
## <P/>
## As lists or ranges are restricted in length (<M>2^{28}-1</M> or
## <M>2^{60}-1</M> depending on your system), the second form returns a
## random integer in the range <A>from</A> to <A>to</A> (inclusive) for
## arbitrary integers <A>from</A> and <A>to</A>.
## <P/>
## The distribution of elements returned by
## <Ref Oper="Random" Label="for a list or collection"/> depends
## on the argument.
## For a list the distribution is uniform (all elements are equally likely).
## The same holds usually for finite collections that are
## not lists.
## For infinite collections some reasonable distribution is used.
## <P/>
## See the chapters of the various collections to find out
## which distribution is being used.
## <P/>
## For some collections ensuring a reasonable distribution can be
## difficult and require substantial runtime (for example for large
## finite groups). If speed is more important than a guaranteed
## distribution,
## the operation <Ref Func="PseudoRandom"/> should be used instead.
## <P/>
## Note that <Ref Oper="Random" Label="for a list or collection"/>
## is of course <E>not</E> an attribute.
## <P/>
## <Example><![CDATA[
## gap> Random([1..6]);
## 6
## gap> Random(1, 2^100);
## 866227015645295902682304086250
## gap> g:= Group( (1,2,3) );; Random( g ); Random( g );
## (1,3,2)
## ()
## gap> Random(Rationals);
## -4
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "Random", [ IsListOrCollection ] );
DeclareOperation( "Random", [ IS_INT, IS_INT ] );
#############################################################################
##
## <#GAPDoc Label="[2]{coll}">
## The method used by &GAP; to obtain random elements may depend on the
## type object.
## <P/>
## Most methods which produce random elements in &GAP; use a global random
## number generator (see <Ref Var="GlobalMersenneTwister"/>).
## This random number generator is (deliberately) initialized to the same
## values when &GAP; is started, so different runs of &GAP; with the same
## input will always produce the same result, even if random calculations
## are involved.
## <P/>
## See <Ref Oper="Reset"/> for a description of how to reset the
## random number generator to a previous state.
## <P/>
##
## <!-- all outdated? (FL)
## Many random methods in the library are eventually based on the function
## <Ref Func="RandomList"/>.
## As <Ref Func="RandomList"/> is restricted to lists of <M>2^{28}</M>
## elements, this may create problems for very large collections. Also note
## that the method used by <Ref Func="RandomList"/> is intended to provide
## a fast algorithm rather than to produce high quality randomness for
## statistical purposes.
## <P/>
## If you implement your own
## <Ref Func="Random" Label="for a list or collection"/> methods we recommend
## that they initialize their seed to a defined value when they are loaded
## to permit to reproduce calculations even if they involved random
## elements.
## -->
## <#/GAPDoc>
##
#############################################################################
##
#F RandomList( <list> )
##
## <#GAPDoc Label="RandomList">
## <ManSection>
## <Func Name="RandomList" Arg='list'/>
##
## <Description>
## <Index>random seed</Index>
## For a dense list <A>list</A>,
## <Ref Func="RandomList"/> returns a (pseudo-)random element with equal
## distribution.
## <P/>
## This function uses the <Ref Var="GlobalMersenneTwister"/> to produce the
## random elements (a source of high quality random numbers).
## <P/>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "RandomList" );
#############################################################################
##
#O PseudoRandom( <C> ) . . . . . . . . pseudo random element of a collection
#O PseudoRandom( <list> ) . . . . . . . . . pseudo random element of a list
##
## <#GAPDoc Label="PseudoRandom">
## <ManSection>
## <Oper Name="PseudoRandom" Arg='listorcoll'/>
##
## <Description>
## <Ref Oper="PseudoRandom"/> returns a pseudo random element
## of the list or collection <A>listorcoll</A>,
## which can be roughly described as follows.
## For a list, <Ref Oper="PseudoRandom"/> returns the same as
## <Ref Oper="Random" Label="for a list or collection"/>.
## For collections that are not lists,
## the elements returned by <Ref Oper="PseudoRandom"/> are
## <E>not</E> necessarily equally distributed,
## even for finite collections;
## the idea is that <Ref Oper="Random" Label="for a list or collection"/>
## returns elements according to
## a reasonable distribution, <Ref Oper="PseudoRandom"/> returns elements
## that are cheap to compute but need not satisfy this strong condition, and
## <Ref Attr="Representative"/> returns arbitrary elements,
## probably the same element for each call.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "PseudoRandom", [ IsListOrCollection ] );
#############################################################################
##
#A PseudoRandomSeed( <C> )
##
## <ManSection>
## <Attr Name="PseudoRandomSeed" Arg='C'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareAttribute( "PseudoRandomSeed", IsListOrCollection, "mutable" );
#############################################################################
##
#A Enumerator( <C> ) . . . . . . . . . . . list of elements of a collection
#A Enumerator( <list> ) . . . . . . . . . . . . list of elements of a list
##
## <#GAPDoc Label="Enumerator">
## <ManSection>
## <Attr Name="Enumerator" Arg='listorcoll'/>
##
## <Description>
## <Ref Func="Enumerator"/> returns an immutable list <M>enum</M>.
## If the argument is a list (which may contain holes),
## then <C>Length( </C><M>enum</M><C> )</C> is the length of this list,
## and <M>enum</M> contains the elements (and holes) of this list in the
## same order.
## If the argument is a collection that is not a list,
## then <C>Length( </C><M>enum</M><C> )</C> is the number of different
## elements of <A>C</A>,
## and <M>enum</M> contains the different elements of the collection in an
## unspecified order, which may change for repeated calls of
## <Ref Func="Enumerator"/>.
## <M>enum[pos]</M> may not execute in constant time
## (see <Ref Func="IsConstantTimeAccessList"/>),
## and the size of <M>enum</M> in memory is as small as is feasible.
## <P/>
## For lists, the default method is <Ref Func="Immutable"/>.
## For collections that are not lists, there is no default method.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "Enumerator", IsListOrCollection );
#############################################################################
##
#A EnumeratorSorted( <C> ) . . . . . proper set of elements of a collection
#A EnumeratorSorted( <list> ) . . . . . . proper set of elements of a list
##
## <#GAPDoc Label="EnumeratorSorted">
## <ManSection>
## <Attr Name="EnumeratorSorted" Arg='listorcoll'/>
##
## <Description>
## <Ref Func="EnumeratorSorted"/> returns an immutable list <M>enum</M>.
## The argument must be a collection or a list <A>listorcoll</A>
## which may contain holes but whose elements lie in the same family
## (see <Ref Sect="Families"/>).
## <C>Length( </C><M>enum</M><C> )</C> is the number of different elements
## of the argument,
## and <M>enum</M> contains the different elements in sorted order,
## w.r.t. <C><</C>.
## <M>enum[pos]</M> may not execute in constant time
## (see <Ref Func="IsConstantTimeAccessList"/>),
## and the size of <M>enum</M> in memory is as small as is feasible.
## <P/>
## <Example><![CDATA[
## gap> Enumerator( [ 1, 3,, 2 ] );
## [ 1, 3,, 2 ]
## gap> enum:= Enumerator( Rationals );; elm:= enum[ 10^6 ];
## -69/907
## gap> Position( enum, elm );
## 1000000
## gap> IsMutable( enum ); IsSortedList( enum );
## false
## false
## gap> IsConstantTimeAccessList( enum );
## false
## gap> EnumeratorSorted( [ 1, 3,, 2 ] );
## [ 1, 2, 3 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "EnumeratorSorted", IsListOrCollection );
#############################################################################
##
#F EnumeratorOfSubset( <list>, <blist>[, <ishomog>] )
##
## <ManSection>
## <Func Name="EnumeratorOfSubset" Arg='list, blist[, ishomog]'/>
##
## <Description>
## Let <A>list</A> be a list, and <A>blist</A> a Boolean list of the same
## length (see <Ref Chap="Boolean Lists"/>).
## <Ref Func="EnumeratorOfSubset"/> returns a list <A>new</A> of length
## equal to the number of <K>true</K> entries in <A>blist</A>,
## such that <C><A>new</A>[i]</C>, if bound, equals the entry of <A>list</A>
## at the <A>i</A>-th <K>true</K> position in <A>blist</A>.
## <P/>
## If <A>list</A> is homogeneous then also <A>new</A> is homogeneous.
## If <A>list</A> is <E>not</E> homogeneous then the third argument
## <A>ishomog</A> must be present and equal to <K>true</K> or <K>false</K>,
## saying whether or not <A>new</A> is homogeneous.
## <P/>
## This construction is used for example in the situation that <A>list</A>
## is an enumerator of a large set,
## and <A>blist</A> describes a union of orbits in an action on this set.
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "EnumeratorOfSubset" );
#############################################################################
##
#F EnumeratorByFunctions( <D>, <record> )
#F EnumeratorByFunctions( <Fam>, <record> )
##
## <#GAPDoc Label="EnumeratorByFunctions">
## <Heading>EnumeratorByFunctions</Heading>
## <ManSection>
## <Func Name="EnumeratorByFunctions" Arg='D, record'
## Label="for a domain and a record"/>
## <Func Name="EnumeratorByFunctions" Arg='Fam, record'
## Label="for a family and a record"/>
##
## <Description>
## <Ref Func="EnumeratorByFunctions" Label="for a domain and a record"/>
## returns an immutable, dense, and duplicate-free list <M>enum</M> for
## which <Ref Func="IsBound" Label="for a list index"/>,
## element access via <Ref Func="\[\]"/>,
## <Ref Func="Length"/>, and <Ref Func="Position"/>
## are computed via prescribed functions.
## <P/>
## Let <A>record</A> be a record with at least the following components.
## <List>
## <Mark><C>ElementNumber</C></Mark>
## <Item>
## a function taking two arguments <A>enum</A> and <A>pos</A>,
## which returns <C><A>enum</A>[ <A>pos</A> ]</C>
## (see <Ref Sect="Basic Operations for Lists"/>);
## it can be assumed that the argument <A>pos</A> is a positive integer,
## but <A>pos</A> may be larger than the length of <A>enum</A>
## (in which case an error must be signalled);
## note that the result must be immutable since <A>enum</A> itself is
## immutable,
## </Item>
## <Mark><C>NumberElement</C></Mark>
## <Item>
## a function taking two arguments <A>enum</A> and <A>elm</A>,
## which returns <C>Position( <A>enum</A>, <A>elm</A> )</C>
## (see <Ref Func="Position"/>);
## it cannot be assumed that <A>elm</A> is really contained in
## <A>enum</A> (and <K>fail</K> must be returned if not);
## note that for the three argument version of <Ref Func="Position"/>,
## the method that is available for duplicate-free lists suffices.
## </Item>
## </List>
## <P/>
## Further (data) components may be contained in <A>record</A>
## which can be used by these function.
## <P/>
## If the first argument is a domain <A>D</A> then <A>enum</A> lists the
## elements of <A>D</A> (in general <A>enum</A> is <E>not</E> sorted),
## and methods for <Ref Attr="Length"/>,
## <Ref Func="IsBound" Label="for a list index"/>,
## and <Ref Func="PrintObj"/> may use <A>D</A>.
## <!-- is this really true for Length?-->
## <P/>
## If one wants to describe the result without creating a domain then the
## elements are given implicitly by the functions in <A>record</A>,
## and the first argument must be a family <A>Fam</A> which will become the
## family of <A>enum</A>;
## if <A>enum</A> is not homogeneous then <A>Fam</A> must be
## <C>ListsFamily</C>,
## otherwise it must be the collections family of any element in <A>enum</A>.
## In this case, additionally the following component in <A>record</A> is
## needed.
## <P/>
## <List>
## <Mark><C>Length</C></Mark>
## <Item>
## a function taking the argument <A>enum</A>,
## which returns the length of <A>enum</A>
## (see <Ref Func="Length"/>).
## </Item>
## </List>
## <P/>
## The following components are optional; they are used if they are present
## but default methods are installed for the case that they are missing.
## <List>
## <Mark><C>IsBound\[\]</C></Mark>
## <Item>
## a function taking two arguments <A>enum</A> and <A>k</A>,
## which returns <C>IsBound( <A>enum</A>[ <A>k</A> ] )</C>
## (see <Ref Sect="Basic Operations for Lists"/>);
## if this component is missing then <Ref Func="Length"/> is used for
## computing the result,
## </Item>
## <Mark><C>Membership</C></Mark>
## <Item>
## a function taking two arguments <A>elm</A> and <A>enum</A>,
## which returns <K>true</K> is <A>elm</A> is an element of <A>enum</A>,
## and <K>false</K> otherwise
## (see <Ref Sect="Basic Operations for Lists"/>);
## if this component is missing then <C>NumberElement</C> is used
## for computing the result,
## </Item>
## <Mark><C>AsList</C></Mark>
## <Item>
## a function taking one argument <A>enum</A>, which returns a list with
## the property that the access to each of its elements will take
## roughly the same time
## (see <Ref Func="IsConstantTimeAccessList"/>);
## if this component is missing then
## <Ref Func="ConstantTimeAccessList"/> is used for computing the result,
## </Item>
## <Mark><C>ViewObj</C> and <C>PrintObj</C></Mark>
## <Item>
## two functions that print what one wants to be printed when
## <C>View( <A>enum</A> )</C> or <C>Print( <A>enum</A> )</C> is called
## (see <Ref Sect="View and Print"/>),
## if the <C>ViewObj</C> component is missing then the <C>PrintObj</C>
## method is used as a default.
## </Item>
## </List>
## <P/>
## If the result is known to have additional properties such as being
## strictly sorted (see <Ref Func="IsSSortedList"/>) then it can be
## useful to set these properties after the construction of the enumerator,
## before it is used for the first time.
## And in the case that a new sorted enumerator of a domain is implemented
## via <Ref Func="EnumeratorByFunctions" Label="for a domain and a record"/>,
## and this construction is
## installed as a method for the operation <Ref Func="Enumerator"/>,
## then it should be installed also as a method for
## <Ref Func="EnumeratorSorted"/>.
## <P/>
## Note that it is <E>not</E> checked that
## <Ref Func="EnumeratorByFunctions" Label="for a domain and a record"/>
## really returns a dense and duplicate-free list.
## <Ref Func="EnumeratorByFunctions" Label="for a domain and a record"/>
## does <E>not</E> make a shallow copy of <A>record</A>,
## this record is changed in place,
## see <Ref Sect="Creating Objects"/>.
## <P/>
## It would be easy to implement a slightly generalized setup for
## enumerators that need not be duplicate-free (where the three argument
## version of <Ref Func="Position"/> is supported),
## but the resulting overhead for the methods seems not to be justified.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "EnumeratorByFunctions" );
#############################################################################
##
#A UnderlyingCollection( <enum> )
##
## <ManSection>
## <Attr Name="UnderlyingCollection" Arg='enum'/>
##
## <Description>
## An enumerator of a domain can delegate the task to compute its length to
## <C>Size</C> for the underlying domain, and <C>ViewObj</C> and <C>PrintObj</C> methods
## may refer to this domain.
## </Description>
## </ManSection>
##
DeclareAttribute( "UnderlyingCollection", IsListOrCollection );
#############################################################################
##
#F List( <list>[, <func>] ) . . . . . . . list of elements of a collection
#F List( <C> )
##
## <#GAPDoc Label="List:list">
## <ManSection>
## <Func Name="List" Arg='list[, func]' Label="for a list (and a function)"/>
##
## <Description>
## This function returns a new mutable list <C>new</C> of the same length
## as the list <A>list</A> (which may have holes). The entry <C>new[i]</C>
## is unbound if <C><A>list</A>[i]</C> is unbound. Otherwise
## <C>new[i] = <A>func</A>(<A>list</A>[i])</C>. If the argument <A>func</A> is
## omitted, its default is <Ref Func="IdFunc"/>, so this function does the
## same as <Ref Oper="ShallowCopy"/> (see also
## <Ref Sect="Duplication of Lists"/>).
## <P/>
## <Example><![CDATA[
## gap> List( [1,2,3], i -> i^2 );
## [ 1, 4, 9 ]
## gap> List( [1..10], IsPrime );
## [ false, true, true, false, true, false, true, false, false, false ]
## gap> List([,1,,3,4], x-> x > 2);
## [ , false,, true, true ]
## ]]></Example>
## <P/>
## (See also <Ref Func="List" Label="for a collection"/>.)
## </Description>
## </ManSection>
## <#/GAPDoc>
##
## <#GAPDoc Label="List:coll">
## <ManSection>
## <Func Name="List" Arg='C' Label="for a collection"/>
##
## <Description>
## For a collection <A>C</A> (see <Ref Chap="Collections"/>)
## that is not a list, <Ref Func="List" Label="for a collection"/> returns
## a new mutable list <A>new</A> such that <C>Length( <A>new</A> )</C>
## is the number of different elements of <A>C</A>,
## and <A>new</A> contains the different elements of <A>C</A> in an
## unspecified order which may change for repeated calls.
## <C><A>new</A>[<A>pos</A>]</C> executes in constant time
## (see <Ref Func="IsConstantTimeAccessList"/>),
## and the size of <A>new</A> is proportional to its length.
## The generic method for this case is
## <C>ShallowCopy( Enumerator( <A>C</A> ) )</C>.
## <!-- this is not reasonable since <C>ShallowCopy</C> need not guarantee to return-->
## <!-- a constant time access list-->
## <P/>
## <Example><![CDATA[
## gap> l:= List( Group( (1,2,3) ) );
## [ (), (1,3,2), (1,2,3) ]
## gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );
## true
## false
## true
## ]]></Example>
## <P/>
## (See also <Ref Func="List" Label="for a list (and a function)"/>.)
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "List" );
DeclareOperation( "ListOp", [ IsListOrCollection ] );
DeclareOperation( "ListOp", [ IsListOrCollection, IsFunction ] );
#############################################################################
##
#O SortedList( <C> )
#O SortedList( <list> )
##
## <#GAPDoc Label="SortedList">
## <ManSection>
## <Oper Name="SortedList" Arg='listorcoll'/>
##
## <Description>
## <Ref Func="SortedList"/> returns a new mutable and dense list <A>new</A>.
## The argument must be a collection or list <A>listorcoll</A> which may
## contain holes but whose elements lie in the same family
## (see <Ref Sect="Families"/>).
## <C>Length( <A>new</A> )</C> is the number of elements of
## <A>listorcoll</A>,
## and <A>new</A> contains the elements in sorted order,
## w.r.t. <C><=</C>.
## <C><A>new</A>[<A>pos</A>]</C> executes in constant time
## (see <Ref Func="IsConstantTimeAccessList"/>),
## and the size of <A>new</A> in memory is proportional to its length.
## <P/>
## <Example><![CDATA[
## gap> l:= SortedList( Group( (1,2,3) ) );
## [ (), (1,2,3), (1,3,2) ]
## gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );
## true
## true
## true
## gap> SortedList( [ 1, 2, 1,, 3, 2 ] );
## [ 1, 1, 2, 2, 3 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "SortedList", [ IsListOrCollection ] );
#############################################################################
##
#O SSortedList( <C> ) . . . . . . . . . . . set of elements of a collection
#O SSortedList( <list> ) . . . . . . . . . . . . . set of elements of a list
#O Set( <C> )
##
## <#GAPDoc Label="SSortedList">
## <ManSection>
## <Oper Name="SSortedList" Arg='listorcoll'/>
## <Oper Name="Set" Arg='C'/>
##
## <Description>
## <Ref Func="SSortedList"/> (<Q>strictly sorted list</Q>) returns a new
## dense, mutable, and duplicate free list <A>new</A>.
## The argument must be a collection or list <A>listorcoll</A>
## which may contain holes but whose elements lie in the same family
## (see <Ref Sect="Families"/>).
## <C>Length( <A>new</A> )</C> is the number of different elements of
## <A>listorcoll</A>,
## and <A>new</A> contains the different elements in strictly sorted order,
## w.r.t. <Ref Func="\<"/>.
## <C><A>new</A>[<A>pos</A>]</C> executes in constant time
## (see <Ref Func="IsConstantTimeAccessList"/>),
## and the size of <A>new</A> in memory is proportional to its length.
## <P/>
## <Ref Func="Set"/> is simply a synonym for <Ref Func="SSortedList"/>.
## <!-- <P/> -->
## <!-- For collections that are not lists, the default method is-->
## <!-- <C>ShallowCopy( EnumeratorSorted( <A>C</A> ) )</C>.-->
## <P/>
## <Example><![CDATA[
## gap> l:= SSortedList( Group( (1,2,3) ) );
## [ (), (1,2,3), (1,3,2) ]
## gap> IsMutable( l ); IsSSortedList( l ); IsConstantTimeAccessList( l );
## true
## true
## true
## gap> SSortedList( [ 1, 2, 1,, 3, 2 ] );
## [ 1, 2, 3 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "SSortedList", [ IsListOrCollection ] );
DeclareSynonym( "Set", SSortedList );
#############################################################################
##
#A AsList( <C> ) . . . . . . . . . . . . . list of elements of a collection
#A AsList( <list> ) . . . . . . . . . . . . . . list of elements of a list
##
## <#GAPDoc Label="AsList">
## <ManSection>
## <Attr Name="AsList" Arg='listorcoll'/>
##
## <Description>
## <Ref Func="AsList"/> returns a immutable list <A>imm</A>.
## If the argument is a list (which may contain holes),
## then <C>Length( <A>imm</A> )</C> is the <Ref Func="Length"/> value of
## this list,
## and <A>imm</A> contains the elements (and holes) of of the list
## in the same order.
## If the argument is a collection that is not a list,
## then <C>Length( <A>imm</A> )</C> is the number of different elements
## of this collection, and <A>imm</A> contains the different elements of
## the collection in an unspecified order,
## which may change for repeated calls of <Ref Func="AsList"/>.
## <C><A>imm</A>[<A>pos</A>]</C> executes in constant time
## (see <Ref Func="IsConstantTimeAccessList"/>),
## and the size of <A>imm</A> in memory is proportional to its length.
## <P/>
## If you expect to do many element tests in the resulting list, it might
## be worth to use a sorted list instead, using <Ref Func="AsSSortedList"/>.
## <!-- <P/> -->
## <!-- For both lists and collections, the default method is-->
## <!-- <C>ConstantTimeAccessList( Enumerator( <A>C</A> ) )</C>.-->
## <P/>
## <Example><![CDATA[
## gap> l:= AsList( [ 1, 3, 3,, 2 ] );
## [ 1, 3, 3,, 2 ]
## gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );
## false
## false
## true
## gap> AsList( Group( (1,2,3), (1,2) ) );
## [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "AsList", IsListOrCollection );
#############################################################################
##
#A AsSortedList( <C> )
#A AsSortedList( <list> )
##
## <#GAPDoc Label="AsSortedList">
## <ManSection>
## <Attr Name="AsSortedList" Arg='listorcoll'/>
##
## <Description>
## <Ref Func="AsSortedList"/> returns a dense and immutable list <A>imm</A>.
## The argument must be a collection or list <A>listorcoll</A>
## which may contain holes but whose elements lie in the same family
## (see <Ref Sect="Families"/>).
## <C>Length( <A>imm</A> )</C> is the number of elements of the argument,
## and <A>imm</A> contains the elements in sorted order,
## w.r.t. <C><=</C>.
## <C><A>new</A>[<A>pos</A>]</C> executes in constant time
## (see <Ref Func="IsConstantTimeAccessList"/>),
## and the size of <A>imm</A> in memory is proportional to its length.
## <P/>
## The only difference to the operation <Ref Func="SortedList"/>
## is that <Ref Func="AsSortedList"/> returns an <E>immutable</E> list.
## <P/>
## <Example><![CDATA[
## gap> l:= AsSortedList( [ 1, 3, 3,, 2 ] );
## [ 1, 2, 3, 3 ]
## gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );
## false
## true
## true
## gap> IsSSortedList( l );
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "AsSortedList", IsListOrCollection );
#############################################################################
##
#A AsSSortedList( <C> ) . . . . . . . . . . set of elements of a collection
#A AsSSortedList( <list> ) . . . . . . . . . . . . set of elements of a list
#A AsSet( <C> )
##
## <#GAPDoc Label="AsSSortedList">
## <ManSection>
## <Attr Name="AsSSortedList" Arg='listorcoll'/>
## <Attr Name="AsSet" Arg='listorcoll'/>
##
## <Description>
## <Index Subkey="of a list or collection">elements</Index>
## <Ref Func="AsSSortedList"/> (<Q>as strictly sorted list</Q>) returns
## a dense, immutable, and duplicate free list <A>imm</A>.
## The argument must be a collection or list <A>listorcoll</A>
## which may contain holes but whose elements lie in the same family
## (see <Ref Sect="Families"/>).
## <C>Length( <A>imm</A> )</C> is the number of different elements
## of <A>listorcoll</A>,
## and <A>imm</A> contains the different elements in strictly sorted order,
## w.r.t. <Ref Func="\<"/>.
## <C><A>imm</A>[<A>pos</A>]</C> executes in constant time
## (see <Ref Func="IsConstantTimeAccessList"/>),
## and the size of <A>imm</A> in memory is proportional to its length.
## <P/>
## Because the comparisons required for sorting can be very expensive for
## some kinds of objects, you should use <Ref Func="AsList"/> instead
## if you do not require the result to be sorted.
## <P/>
## The only difference to the operation <Ref Func="SSortedList"/>
## is that <Ref Attr="AsSSortedList"/> returns an <E>immutable</E> list.
## <P/>
## <Ref Attr="AsSet"/> is simply a synonym for <Ref Attr="AsSSortedList"/>.
## <P/>
## In general a function that returns a set of elements is free, in fact
## encouraged, to return a domain instead of the proper set of its elements.
## This allows one to keep a given structure, and moreover the
## representation by a domain object is usually more space efficient.
## <Ref Attr="AsSSortedList"/> must of course <E>not</E> do this,
## its only purpose is to create the proper set of elements.
## <!-- <P/> -->
## <!-- For both lists and collections, the default method is-->
## <!-- <C>ConstantTimeAccessList( EnumeratorSorted( <A>C</A> ) )</C>.-->
## <P/>
## <Example><![CDATA[
## gap> l:= AsSSortedList( l );
## [ 1, 2, 3 ]
## gap> IsMutable( l ); IsSSortedList( l ); IsConstantTimeAccessList( l );
## false
## true
## true
## gap> AsSSortedList( Group( (1,2,3), (1,2) ) );
## [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "AsSSortedList", IsListOrCollection );
DeclareSynonym( "AsSet", AsSSortedList );
#############################################################################
##
#A AsSSortedListNonstored( <C> )
##
## <ManSection>
## <Attr Name="AsSSortedListNonstored" Arg='C'/>
##
## <Description>
## returns the <Ref Func="AsSSortedList"/> value of the list or collection
## <A>C</A> but ensures that this list
## (nor a permutation or substantial subset) will not be
## stored in attributes of <A>C</A> unless such a list is already stored.
## This permits to obtain an element list once
## without danger of clogging up memory in the long run.
## <P/>
## Because of this guarantee of nonstorage, methods for
## <Ref Func="AsSSortedListNonstored"/> may not default to
## <Ref Func="AsSSortedList"/>, but only vice versa.
## </Description>
## </ManSection>
##
DeclareOperation( "AsSSortedListNonstored", [IsListOrCollection] );
#############################################################################
##
#F Elements( <C> )
##
## <#GAPDoc Label="Elements">
## <ManSection>
## <Func Name="Elements" Arg='C'/>
##
## <Description>
## <Ref Func="Elements"/> does the same as <Ref Func="AsSSortedList"/>,
## that is, the return value is a strictly sorted list of the elements in
## the list or collection <A>C</A>.
## <P/>
## <Ref Func="Elements"/> is only supported for backwards compatibility.
## In many situations, the sortedness of the <Q>element list</Q> for a
## collection is in fact not needed, and one can save a lot of time by
## asking for a list that is <E>not</E> necessarily sorted,
## using <Ref Func="AsList"/>.
## If one is really interested in the strictly sorted list of elements in
## <A>C</A> then one should use <Ref Func="AsSet"/> or
## <Ref Func="AsSSortedList"/> instead.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Elements" );
#############################################################################
##
#F Sum( <list>[, <init>] ) . . . . . . . . . . sum of the elements of a list
#F Sum( <C>[, <init>] ) . . . . . . . . sum of the elements of a collection
#F Sum( <list>, <func>[, <init>] ) . . . . . sum of images under a function
#F Sum( <C>, <func>[, <init>] ) . . . . . . sum of images under a function
##
## <#GAPDoc Label="Sum">
## <ManSection>
## <Func Name="Sum" Arg='listorcoll[, func][, init]'/>
##
## <Description>
## Called with one argument, a dense list or collection <A>listorcoll</A>,
## <Ref Func="Sum"/> returns the sum of the elements of <A>listorcoll</A>
## (see <Ref Chap="Collections"/>).
## <P/>
## Called with a dense list or collection <A>listorcoll</A> and a function
## <A>func</A>, which must be a function taking one argument,
## <Ref Func="Sum"/> applies the function <A>func</A>
## to the elements of <A>listorcoll</A>, and returns the sum of the results.
## In either case <Ref Func="Sum"/> returns <C>0</C> if the first argument
## is empty.
## <P/>
## The general rules for arithmetic operations apply
## (see <Ref Sect="Mutability Status and List Arithmetic"/>),
## so the result is immutable if and only if all summands are immutable.
## <P/>
## If <A>listorcoll</A> contains exactly one element then this element
## (or its image under <A>func</A> if applicable) itself is returned,
## not a shallow copy of this element.
## <P/>
## If an additional initial value <A>init</A> is given,
## <Ref Func="Sum"/> returns the sum of <A>init</A> and the elements of the
## first argument resp. of their images under the function <A>func</A>.
## This is useful for example if the first argument is empty and a different
## zero than <C>0</C> is desired, in which case <A>init</A> is returned.
## <P/>
## <Example><![CDATA[
## gap> Sum( [ 2, 3, 5, 7, 11, 13, 17, 19 ] );
## 77
## gap> Sum( [1..10], x->x^2 );
## 385
## gap> Sum( [ [1,2], [3,4], [5,6] ] );
## [ 9, 12 ]
## gap> Sum( GF(8) );
## 0*Z(2)
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Sum" );
#############################################################################
##
#O SumOp( <C> )
#O SumOp( <C>, <func> )
#O SumOp( <C>, <init> )
#O SumOp( <C>, <func>, <init> )
##
## <ManSection>
## <Oper Name="SumOp" Arg='C'/>
## <Oper Name="SumOp" Arg='C, func'/>
## <Oper Name="SumOp" Arg='C, init'/>
## <Oper Name="SumOp" Arg='C, func, init'/>
##
## <Description>
## <C>SumOp</C> is the operation called by <C>Sum</C>
## if <A>C</A> is not an internal list.
## </Description>
## </ManSection>
##
DeclareOperation( "SumOp", [ IsListOrCollection ] );
#############################################################################
##
#F Product( <list>[, <init>] ) . . . . . . product of the elements of a list
#F Product( <C>[, <init>] ) . . . . product of the elements of a collection
#F Product( <list>, <func>[, <init>] ) . product of images under a function
#F Product( <C>, <func>[, <init>] ) . . product of images under a function
##
## <#GAPDoc Label="Product">
## <ManSection>
## <Func Name="Product" Arg='listorcoll[, func][, init]'/>
##
## <Description>
## Called with one argument, a dense list or collection <A>listorcoll</A>,
## <Ref Func="Product"/> returns the product of the elements of
## <A>listorcoll</A> (see <Ref Chap="Collections"/>).
## <P/>
## Called with a dense list or collection <A>listorcoll</A> and a function
## <A>func</A>, which must be a function taking one argument,
## <Ref Func="Product"/> applies the function <A>func</A>
## to the elements of <A>listorcoll</A>, and returns the product of the
## results.
## In either case <Ref Func="Product"/> returns <C>1</C> if the first
## argument is empty.
## <P/>
## The general rules for arithmetic operations apply
## (see <Ref Sect="Mutability Status and List Arithmetic"/>),
## so the result is immutable if and only if all summands are immutable.
## <P/>
## If <A>listorcoll</A> contains exactly one element then this element
## (or its image under <A>func</A> if applicable) itself is returned,
## not a shallow copy of this element.
## <P/>
## If an additional initial value <A>init</A> is given,
## <Ref Func="Product"/> returns the product of <A>init</A> and the elements
## of the first argument resp. of their images under the function
## <A>func</A>.
## This is useful for example if the first argument is empty and a different
## identity than <C>1</C> is desired, in which case <A>init</A> is returned.
## <P/>
## <Example><![CDATA[
## gap> Product( [ 2, 3, 5, 7, 11, 13, 17, 19 ] );
## 9699690
## gap> Product( [1..10], x->x^2 );
## 13168189440000
## gap> Product( [ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) ] );
## (1,4)(2,3)
## gap> Product( GF(8) );
## 0*Z(2)
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Product" );
#############################################################################
##
#O ProductOp( <C> )
#O ProductOp( <C>, <func> )
#O ProductOp( <C>, <init> )
#O ProductOp( <C>, <func>, <init> )
##
## <ManSection>
## <Oper Name="ProductOp" Arg='C'/>
## <Oper Name="ProductOp" Arg='C, func'/>
## <Oper Name="ProductOp" Arg='C, init'/>
## <Oper Name="ProductOp" Arg='C, func, init'/>
##
## <Description>
## <C>ProductOp</C> is the operation called by <C>Product</C>
## if <A>C</A> is not an internal list.
## </Description>
## </ManSection>
##
DeclareOperation( "ProductOp", [ IsListOrCollection ] );
#############################################################################
##
#F Filtered( <list>, <func> ) . . . . extract elements that have a property
#F Filtered( <C>, <func> ) . . . . . . extract elements that have a property
##
## <#GAPDoc Label="Filtered">
## <ManSection>
## <Func Name="Filtered" Arg='listorcoll, func'/>
##
## <Description>
## returns a new list that contains those elements of the list or collection
## <A>listorcoll</A> (see <Ref Chap="Collections"/>), respectively,
## for which the unary function <A>func</A> returns <K>true</K>.
## <P/>
## If the first argument is a list, the order of the elements in the result
## is the same as the order of the corresponding elements of this list.
## If an element for which <A>func</A> returns <K>true</K> appears several
## times in the list it will also appear the same number of times
## in the result.
## The argument list may contain holes,
## they are ignored by <Ref Func="Filtered"/>.
## <P/>
## For each element of <A>listorcoll</A>,
## <A>func</A> must return either <K>true</K> or <K>false</K>,
## otherwise an error is signalled.
## <P/>
## The result is a new list that is not identical to any other list.
## The elements of that list however are identical to the corresponding
## elements of the argument list (see <Ref Sect="Identical Lists"/>).
## <P/>
## List assignment using the operator <Ref Func="\{\}"/>
## (see <Ref Sect="List Assignment"/>) can be used to extract
## elements of a list according to indices given in another list.
## <P/>
## <Example><![CDATA[
## gap> Filtered( [1..20], IsPrime );
## [ 2, 3, 5, 7, 11, 13, 17, 19 ]
## gap> Filtered( [ 1, 3, 4, -4, 4, 7, 10, 6 ], IsPrimePowerInt );
## [ 3, 4, 4, 7 ]
## gap> Filtered( [ 1, 3, 4, -4, 4, 7, 10, 6 ],
## > n -> IsPrimePowerInt(n) and n mod 2 <> 0 );
## [ 3, 7 ]
## gap> Filtered( Group( (1,2), (1,2,3) ), x -> Order( x ) = 2 );
## [ (2,3), (1,2), (1,3) ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Filtered" );
#############################################################################
##
#O FilteredOp( <C>, <func> )
##
## <ManSection>
## <Oper Name="FilteredOp" Arg='C, func'/>
##
## <Description>
## <C>FilteredOp</C> is the operation called by <C>Filtered</C>
## if <A>C</A> is not an internal list.
## </Description>
## </ManSection>
##
DeclareOperation( "FilteredOp", [ IsListOrCollection, IsFunction ] );
#############################################################################
##
#F Number( <list> )
#F Number( <list>, <func> ) . . . . . . count elements that have a property
#F Number( <C>, <func> ) . . . . . . . . count elements that have a property
##
## <#GAPDoc Label="Number">
## <ManSection>
## <Func Name="Number" Arg='listorcoll[, func]'/>
##
## <Description>
## Called with a list <A>listorcoll</A>, <Ref Func="Number"/> returns the
## number of bound entries in this list.
## For dense lists <Ref Func="Number"/>, <Ref Func="Length"/>,
## and <Ref Func="Size"/> return the same value;
## for lists with holes <Ref Func="Number"/> returns the number of bound
## entries, <Ref Func="Length"/> returns the largest index of a bound entry,
## and <Ref Func="Size"/> signals an error.
## <P/>
## Called with two arguments, a list or collection <A>listorcoll</A> and a
## unary function <A>func</A>, <Ref Func="Number"/> returns the number of
## elements of <A>listorcoll</A> for which <A>func</A> returns <K>true</K>.
## If an element for which <A>func</A> returns <K>true</K> appears several
## times in <A>listorcoll</A> it will also be counted the same number of
## times.
## <P/>
## For each element of <A>listorcoll</A>,
## <A>func</A> must return either <K>true</K> or <K>false</K>,
## otherwise an error is signalled.
## <P/>
## <Ref Func="Filtered"/> allows you to extract the elements of a list
## that have a certain property.
## <P/>
## <Example><![CDATA[
## gap> Number( [ 2, 3, 5, 7 ] );
## 4
## gap> Number( [, 2, 3,, 5,, 7,,,, 11 ] );
## 5
## gap> Number( [1..20], IsPrime );
## 8
## gap> Number( [ 1, 3, 4, -4, 4, 7, 10, 6 ], IsPrimePowerInt );
## 4
## gap> Number( [ 1, 3, 4, -4, 4, 7, 10, 6 ],
## > n -> IsPrimePowerInt(n) and n mod 2 <> 0 );
## 2
## gap> Number( Group( (1,2), (1,2,3) ), x -> Order( x ) = 2 );
## 3
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Number" );
#############################################################################
##
#O NumberOp( <C>, <func> )
##
## <ManSection>
## <Oper Name="NumberOp" Arg='C, func'/>
##
## <Description>
## <C>NumberOp</C> is the operation called by <C>Number</C>
## if <A>C</A> is not an internal list.
## </Description>
## </ManSection>
##
DeclareOperation( "NumberOp", [ IsListOrCollection, IsFunction ] );
#############################################################################
##
#F ForAll( <list>, <func> )
#F ForAll( <C>, <func> )
##
## <#GAPDoc Label="ForAll">
## <ManSection>
## <Func Name="ForAll" Arg='listorcoll, func'/>
##
## <Description>
## tests whether the unary function <A>func</A> returns <K>true</K>
## for all elements in the list or collection <A>listorcoll</A>.
## <P/>
## <Example><![CDATA[
## gap> ForAll( [1..20], IsPrime );
## false
## gap> ForAll( [2,3,4,5,8,9], IsPrimePowerInt );
## true
## gap> ForAll( [2..14], n -> IsPrimePowerInt(n) or n mod 2 = 0 );
## true
## gap> ForAll( Group( (1,2), (1,2,3) ), i -> SignPerm(i) = 1 );
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "ForAll" );
#############################################################################
##
#O ForAllOp( <C>, <func> )
##
## <ManSection>
## <Oper Name="ForAllOp" Arg='C, func'/>
##
## <Description>
## <C>ForAllOp</C> is the operation called by <C>ForAll</C>
## if <A>C</A> is not an internal list.
## </Description>
## </ManSection>
##
DeclareOperation( "ForAllOp", [ IsListOrCollection, IsFunction ] );
#############################################################################
##
#F ForAny( <list>, <func> )
#F ForAny( <C>, <func> )
##
## <#GAPDoc Label="ForAny">
## <ManSection>
## <Func Name="ForAny" Arg='listorcoll, func'/>
##
## <Description>
## tests whether the unary function <A>func</A> returns <K>true</K>
## for at least one element in the list or collection <A>listorcoll</A>.
## <P/>
## <Example><![CDATA[
## gap> ForAny( [1..20], IsPrime );
## true
## gap> ForAny( [2,3,4,5,8,9], IsPrimePowerInt );
## true
## gap> ForAny( [2..14],
## > n -> IsPrimePowerInt(n) and n mod 5 = 0 and not IsPrime(n) );
## false
## gap> ForAny( Integers, i -> i > 0
## > and ForAll( [0,2..4], j -> IsPrime(i+j) ) );
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "ForAny" );
#############################################################################
##
#O ForAnyOp( <C>, <func> )
##
## <ManSection>
## <Oper Name="ForAnyOp" Arg='C, func'/>
##
## <Description>
## <C>ForAnyOp</C> is the operation called by <C>ForAny</C>
## if <A>C</A> is not an internal list.
## </Description>
## </ManSection>
##
DeclareOperation( "ForAnyOp", [ IsListOrCollection, IsFunction ] );
#############################################################################
##
#O ListX( <arg1>, <arg2>, ... <argn>, <func> )
##
## <#GAPDoc Label="ListX">
## <ManSection>
## <Func Name="ListX" Arg='arg1, arg2, ... argn, func'/>
##
## <Description>
## <Ref Func="ListX"/> returns a new list constructed from the arguments.
## <P/>
## Each of the arguments <A>arg1</A>, <A>arg2</A>, <M>\ldots</M> <A>argn</A>
## must be one of the following:
## <List>
## <Mark>a list or collection</Mark>
## <Item>
## this introduces a new for-loop in the sequence of nested
## for-loops and if-statements;
## </Item>
## <Mark>a function returning a list or collection</Mark>
## <Item>
## this introduces a new for-loop in the sequence of nested
## for-loops and if-statements, where the loop-range depends on
## the values of the outer loop-variables; or
## </Item>
## <Mark>a function returning <K>true</K> or <K>false</K></Mark>
## <Item>
## this introduces a new if-statement in the sequence of nested
## for-loops and if-statements.
## </Item>
## </List>
## <P/>
## The last argument <A>func</A> must be a function,
## it is applied to the values of the loop-variables
## and the results are collected.
## <P/>
## Thus <C>ListX( <A>list</A>, <A>func</A> )</C> is the same as
## <C>List( <A>list</A>, <A>func</A> )</C>,
## and <C>ListX( <A>list</A>, <A>func</A>, x -> x )</C> is the same as
## <C>Filtered( <A>list</A>, <A>func</A> )</C>.
## <P/>
## As a more elaborate example, assume <A>arg1</A> is a list or collection,
## <A>arg2</A> is a function returning <K>true</K> or <K>false</K>,
## <A>arg3</A> is a function returning a list or collection, and
## <A>arg4</A> is another function returning <K>true</K> or <K>false</K>,
## then
## <P/>
## <C><A>result</A> := ListX( <A>arg1</A>, <A>arg2</A>, <A>arg3</A>,
## <A>arg4</A>, <A>func</A> );</C>
## <P/>
## is equivalent to
## <P/>
## <Listing><![CDATA[
## result := [];
## for v1 in arg1 do
## if arg2( v1 ) then
## for v2 in arg3( v1 ) do
## if arg4( v1, v2 ) then
## Add( result, func( v1, v2 ) );
## fi;
## od;
## fi;
## od;
## ]]></Listing>
## <P/>
## The following example shows how <Ref Func="ListX"/> can be used to
## compute all pairs and all strictly sorted pairs of elements in a list.
## <P/>
## <Example><![CDATA[
## gap> l:= [ 1, 2, 3, 4 ];;
## gap> pair:= function( x, y ) return [ x, y ]; end;;
## gap> ListX( l, l, pair );
## [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 2 ],
## [ 2, 3 ], [ 2, 4 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ], [ 3, 4 ],
## [ 4, 1 ], [ 4, 2 ], [ 4, 3 ], [ 4, 4 ] ]
## ]]></Example>
## <P/>
## In the following example, <Ref Func="\<"/> is the comparison
## operation:
## <P/>
## <Example><![CDATA[
## gap> ListX( l, l, \<, pair );
## [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "ListX" );
#############################################################################
##
#O SetX( <arg1>, <arg2>, ... <func> )
##
## <#GAPDoc Label="SetX">
## <ManSection>
## <Func Name="SetX" Arg='arg1, arg2, ... func'/>
##
## <Description>
## The only difference between <Ref Func="SetX"/> and <Ref Func="ListX"/>
## is that the result list of <Ref Func="SetX"/> is strictly sorted.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "SetX" );
#############################################################################
##
#O SumX( <arg1>, <arg2>, ... <func> )
##
## <#GAPDoc Label="SumX">
## <ManSection>
## <Func Name="SumX" Arg='arg1, arg2, ... func'/>
##
## <Description>
## <Ref Func="SumX"/> returns the sum of the elements in the list obtained
## by <Ref Func="ListX"/> when this is called with the same arguments.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "SumX" );
#############################################################################
##
#O ProductX( <arg1>, <arg2>, ... <func> )
##
## <#GAPDoc Label="ProductX">
## <ManSection>
## <Func Name="ProductX" Arg='arg1, arg2, ... func'/>
##
## <Description>
## <Ref Func="ProductX"/> returns the product of the elements in the list
## obtained by <Ref Func="ListX"/> when this is called with the same
## arguments.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "ProductX" );
#############################################################################
##
#O Perform( <list>, <func>)
##
## <#GAPDoc Label="Perform">
## <ManSection>
## <Func Name="Perform" Arg='list, func'/>
##
## <Description>
## <Ref Func="Perform"/> applies the function <A>func</A> to every element
## of the list <A>list</A>, discarding any return values.
## It does not return a value.
## <P/>
## <Example><![CDATA[
## gap> l := [1, 2, 3];; Perform(l,
## > function(x) if IsPrimeInt(x) then Print(x,"\n"); fi; end);
## 2
## 3
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Perform" );
#############################################################################
##
#O IsSubset( <C1>, <C2> ) . . . . . . . . . test for subset of collections
##
## <#GAPDoc Label="IsSubset">
## <ManSection>
## <Oper Name="IsSubset" Arg='C1, C2'/>
##
## <Description>
## <Index Subkey="for collections">subset test</Index>
## <Ref Oper="IsSubset"/> returns <K>true</K> if <A>C2</A>,
## which must be a collection, is a <E>subset</E> of <A>C1</A>,
## which also must be a collection, and <K>false</K> otherwise.
## <P/>
## <A>C2</A> is considered a subset of <A>C1</A> if and only if each element
## of <A>C2</A> is also an element of <A>C1</A>.
## That is <Ref Oper="IsSubset"/> behaves as if implemented as
## <C>IsSubsetSet( AsSSortedList( <A>C1</A> ), AsSSortedList( <A>C2</A> ) )</C>,
## except that it will also sometimes, but not always,
## work for infinite collections,
## and that it will usually work much faster than the above definition.
## Either argument may also be a proper set
## (see <Ref Sect="Sorted Lists and Sets"/>).
## <P/>
## <Example><![CDATA[
## gap> IsSubset( Rationals, Integers );
## true
## gap> IsSubset( Integers, [ 1, 2, 3 ] );
## true
## gap> IsSubset( Group( (1,2,3,4) ), [ (1,2,3) ] );
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "IsSubset", [ IsListOrCollection, IsListOrCollection ] );
#############################################################################
##
#F Intersection( <C1>, <C2> ... ) . . . . . . . intersection of collections
#F Intersection( <list> ) . . . . . . . . . . . intersection of collections
#O Intersection2( <C1>, <C2> ) . . . . . . . . . intersection of collections
##
## <#GAPDoc Label="Intersection">
## <ManSection>
## <Heading>Intersection</Heading>
## <Func Name="Intersection" Arg='C1, C2 ...'
## Label="for various collections"/>
## <Func Name="Intersection" Arg='list' Label="for a list"/>
## <Oper Name="Intersection2" Arg='C1, C2'/>
##
## <Description>
## <Index Subkey="of collections">intersection</Index>
## In the first form
## <Ref Func="Intersection" Label="for various collections"/> returns the
## intersection of the collections <A>C1</A>, <A>C2</A>, etc.
## In the second form <A>list</A> must be a <E>nonempty</E> list of
## collections and <Ref Func="Intersection" Label="for a list"/> returns
## the intersection of those collections.
## Each argument or element of <A>list</A> respectively may also be a
## homogeneous list that is not a proper set,
## in which case <Ref Func="Intersection" Label="for a list"/> silently
## applies <Ref Func="Set"/> to it first.
## <P/>
## The result of <Ref Func="Intersection" Label="for a list"/> is the set
## of elements that lie in every of the collections <A>C1</A>, <A>C2</A>,
## etc.
## If the result is a list then it is mutable and new, i.e., not identical
## to any of <A>C1</A>, <A>C2</A>, etc.
## <P/>
## Methods can be installed for the operation <Ref Func="Intersection2"/>
## that takes only two arguments.
## <Ref Func="Intersection" Label="for a list"/> calls
## <Ref Func="Intersection2"/>.
## <P/>
## Methods for <Ref Func="Intersection2"/> should try to maintain as much
## structure as possible, for example the intersection of two permutation
## groups is again a permutation group.
## <P/>
## <Example><![CDATA[
## gap> # this is one of the rare cases where the intersection of two
## gap> # infinite domains works ('CF' is a shorthand for 'CyclotomicField'):
## gap> Intersection( CyclotomicField(9), CyclotomicField(12) );
## CF(3)
## gap> D12 := Group( (2,6)(3,5), (1,2)(3,6)(4,5) );;
## 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) ] )
## > ; # note that the second argument is not a proper set
## [ (1,3)(4,6) ]
## gap> # although the result is mathematically a group it is returned as a
## gap> # proper set because the second argument is not regarded as a group:
## gap> Intersection( D12, [ (), (1,2)(3,4), (1,3)(4,6), (1,4)(5,6) ] );
## [ (), (1,3)(4,6) ]
## gap> Intersection( Group( () ), [1,2,3] );
## [ ]
## gap> Intersection( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] )
## > ; # two or more lists or collections as arguments are legal
## [ ]
## gap> Intersection( [ [1,2,4], [2,3,4], [1,3,4] ] )
## > ; # or one list of lists or collections
## [ 4 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Intersection" );
DeclareOperation( "Intersection2",
[ IsListOrCollection, IsListOrCollection ] );
#############################################################################
##
#F Union( <C1>, <C2> ... ) . . . . . . . . . . . . . . union of collections
#F Union( <list> ) . . . . . . . . . . . . . . . . . . union of collections
#O Union2( <C1>, <C2> ) . . . . . . . . . . . . . . . union of collections
##
## <#GAPDoc Label="Union">
## <ManSection>
## <Heading>Union</Heading>
## <Func Name="Union" Arg='C1, C2 ...' Label="for various collections"/>
## <Func Name="Union" Arg='list' Label="for a list"/>
## <Oper Name="Union2" Arg='C1, C2'/>
##
## <Description>
## <Index Subkey="of collections">union</Index>
## In the first form <Ref Func="Union" Label="for various collections"/>
## returns the union of the collections <A>C1</A>, <A>C2</A>, etc.
## In the second form <A>list</A> must be a list of collections
## and <Ref Func="Union" Label="for a list"/> returns the union of those
## collections.
## Each argument or element of <A>list</A> respectively may also be a
## homogeneous list that is not a proper set,
## in which case <Ref Func="Union" Label="for a list"/> silently applies
## <Ref Func="Set"/> to it first.
## <P/>
## The result of <Ref Func="Union" Label="for a list"/> is the set of
## elements that lie in any of the collections <A>C1</A>, <A>C2</A>, etc.
## If the result is a list then it is mutable and new, i.e., not identical
## to any of <A>C1</A>, <A>C2</A>, etc.
## <P/>
## Methods can be installed for the operation <Ref Oper="Union2"/>
## that takes only two arguments.
## <Ref Func="Union" Label="for a list"/> calls <Ref Func="Union2"/>.
## <P/>
## <Example><![CDATA[
## gap> Union( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) );
## [ (), (2,3), (1,2), (1,2,3), (1,2,3,4), (1,3,2), (1,3) ]
## gap> Union( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] )
## > ; # two or more lists or collections as arguments are legal
## [ 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20, 25 ]
## gap> Union( [ [1,2,4], [2,3,4], [1,3,4] ] )
## > ; # or one list of lists or collections
## [ 1, 2, 3, 4 ]
## gap> Union( [ ] );
## [ ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Union" );
DeclareOperation( "Union2", [ IsListOrCollection, IsListOrCollection ] );
#############################################################################
##
#O Difference( <C1>, <C2> ) . . . . . . . . . . . difference of collections
##
## <#GAPDoc Label="Difference">
## <ManSection>
## <Oper Name="Difference" Arg='C1, C2'/>
##
## <Description>
## <Index Subkey="of collections">set difference</Index>
## <Ref Func="Difference"/> returns the set difference of the collections
## <A>C1</A> and <A>C2</A>.
## Either argument may also be a homogeneous list that is not a proper set,
## in which case <Ref Func="Difference"/> silently applies <Ref Func="Set"/>
## to it first.
## <P/>
## The result of <Ref Func="Difference"/> is the set of elements that lie in
## <A>C1</A> but not in <A>C2</A>.
## Note that <A>C2</A> need not be a subset of <A>C1</A>.
## The elements of <A>C2</A>, however, that are not elements of <A>C1</A>
## play no role for the result.
## If the result is a list then it is mutable and new, i.e., not identical
## to <A>C1</A> or <A>C2</A>.
## <P/>
## <Example><![CDATA[
## gap> Difference( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) );
## [ (1,2,3,4) ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "Difference", [ IsListOrCollection, IsListOrCollection ] );
#############################################################################
##
#P CanEasilyCompareElements( <obj> )
#F CanEasilyCompareElementsFamily( <fam> )
#P CanEasilySortElements( <obj> )
#F CanEasilySortElementsFamily( <fam> )
##
## <#GAPDoc Label="CanEasilyCompareElements">
## <ManSection>
## <Prop Name="CanEasilyCompareElements" Arg='obj'/>
## <Func Name="CanEasilyCompareElementsFamily" Arg='fam'/>
## <Prop Name="CanEasilySortElements" Arg='obj'/>
## <Func Name="CanEasilySortElementsFamily" Arg='fam'/>
##
## <Description>
## For some objects a <Q>normal form</Q> is hard to compute
## and thus equality of elements of a domain might be expensive to test.
## Therefore &GAP; provides a (slightly technical) property with which an
## algorithm can test whether an efficient equality test is available
## for elements of a certain kind.
## <P/>
## <Ref Func="CanEasilyCompareElements"/> indicates whether the elements in
## the family <A>fam</A> of <A>obj</A> can be easily compared with
## <Ref Func="\="/>.
## <P/>
## The default method for this property is to ask the family of <A>obj</A>,
## the default method for the family is to return <K>false</K>.
## <P/>
## The ability to compare elements may depend on the successful computation
## of certain information. (For example for finitely presented groups it
## might depend on the knowledge of a faithful permutation representation.)
## This information might change over time and thus it might not be a good
## idea to store a value <K>false</K> too early in a family. Instead the
## function <Ref Func="CanEasilyCompareElementsFamily"/> should be called
## for the family of <A>obj</A> which returns <K>false</K> if the value of
## <Ref Func="CanEasilyCompareElements"/> is not known for the family
## without computing it. (This is in fact what the above mentioned family
## dispatch does.)
## <P/>
## If a family knows ab initio that it can compare elements this property
## should be set as implied filter <E>and</E> filter for the family
## (the 3rd and 4th argument of <Ref Func="NewFamily"/>
## respectively).
## This guarantees that code which directly asks the family gets a right
## answer.
## <P/>
## The property <Ref Func="CanEasilySortElements"/> and the function
## <Ref Func="CanEasilySortElementsFamily"/> behave exactly in the same way,
## except that they indicate that objects can be compared via
## <Ref Func="\<"/>.
## This property implies <Ref Func="CanEasilyCompareElements"/>,
## as the ordering must be total.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "CanEasilyCompareElements", IsObject );
DeclareGlobalFunction( "CanEasilyCompareElementsFamily" );
DeclareProperty( "CanEasilySortElements", IsObject );
DeclareGlobalFunction( "CanEasilySortElementsFamily" );
InstallTrueMethod(CanEasilyCompareElements,CanEasilySortElements);
#############################################################################
##
#O CanComputeIsSubset( <A>, <B> )
##
## <#GAPDoc Label="CanComputeIsSubset">
## <ManSection>
## <Oper Name="CanComputeIsSubset" Arg='A, B'/>
##
## <Description>
## This filter indicates that &GAP; can test (via <Ref Func="IsSubset"/>)
## whether <A>B</A> is a subset of <A>A</A>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "CanComputeIsSubset", [IsObject,IsObject] );
#############################################################################
##
#F CanComputeSize( <dom> )
##
## <#GAPDoc Label="CanComputeSize">
## <ManSection>
## <Func Name="CanComputeSize" Arg='dom'/>
##
## <Description>
## This filter indicates whether the size of the domain <A>dom</A>
## (which might be <Ref Var="infinity"/>) can be computed.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareFilter( "CanComputeSize" );
InstallTrueMethod( CanComputeSize, HasSize );
DeclareOperation( "Randomizer", [IsCollection] );
DeclareOperation( "CheapRandomizer", [IsCollection] );
DeclareAttribute( "RandomizerAttr", IsCollection );
DeclareAttribute( "CheapRandomizerAttr", IsCollection );
# to allow for recusive calls
DeclareGlobalFunction("JoinRanges");
#############################################################################
##
#E