[GAP Forum] Filter trouble

[Thomas Breuer]

Dear GAP Forum,

Marc Roeder had started a discussion about different kinds of filters,
and how to distinguish them.
Stefan Kohl has already explained the difference between properties
and categories,
and then Marc asked the following.

> Is there a way to know which filters are Categories and which are Pro=
> perties (something like IsCategory)? And is there a way to know which=
>  Properties of an object are stored after calculation (to use Redispa=
> tchOnCondition)?
> 
> Guessing Categories seems to be a little  bit difficult, as for examp=
> le
> IS_INT(2) is true, while CategoryCollections(IS_INT)([2]) is false.

Let us go one step back.

Each filter in GAP is either a simple filter or a meet of filters.
For example, `IsInt' and `IsPosRat' are simple filters,
and `IsPosInt' is defined as their meet `IsInt and IsPosRat'.

Each *simple filter* is of one of the following kinds.

1. property:
   Such a filter is an operation, the filter value can be computed.
   The (unary) methods of this operation must return `true' or `false',
   and the return value is stored in the argument,
   except if the argument is of a basic data type such as cyclotomic
   (including rationals and integers), finite field element, permutation,
   or internally represented list --the latter with a few exceptions.
   Examples of properties are `IsFinite', `IsAbelian', `IsSSortedList'.

2. attribute tester:
   Such a filter is associated to an operation that has been created
   via `DeclareAttribute',
   in the sense that the value is `true' if and only if a return value
   for (a unary method of) this operation is stored in the argument.
   Currently, attribute values are stored in objects in the filter
   `IsAttributeStoringRep'.
   Examples of attribute testers are `HasSize', `HasCentre',
   `HasDerivedSubgroup'.

2.' property tester:
   Such a filter is similar to an attribute tester,
   but the associated operation is a property.
   So property testers can return `true' also if the argument is not in
   the filter `IsAttributeStoringRep'.
   Examples of property testers are `HasIsFinite', `HasIsAbelian',
   `HasIsSSortedList'.

3. category or representation:
   These filters are not associated to operations, their values cannot
   be computed but are set upon creation of an object and should not be
   changed later, such that for a filter of this kind, one can rely on
   the fact that if the value is `true' then it was `true' already when
   the object in question was created.

   The distinction between representation and category is intended to
   express dependency on or independence of the way how the object is
   stored internally.
   For example, `IsPositionalObjectRep', `IsComponentObjectRep', and
   `IsInternalRep' are filters of the representation kind;
   the idea is that such filters are used in low level methods,
   and that higher level methods can be implemented without referring
   to these filters.
   (To be honest, this distinction is not used in a clean way throughout
   the system.)

   Examples of categories are `IsInt', `IsRat', `IsPerm', `IsFFE',
   and filters expressing algebraic structures,
   such as `IsMagma', `IsMagmaWithOne', `IsAdditiveMagma'.
   When one calls such a filter, one can be sure that no computation is
   triggered.
   For example, whenever a quotient of two integers is formed, the result
   is clearly in the filter `IsRat', but the system also stores the value
   of `IsInt', i.e., GAP does not support ``unevaluated rationals'' for
   which the `IsInt' value is computed on demand and then stored.

4. other filters:
   Some filters do not belong to the above kinds,
   they are not associated to operations but they are intended to be
   set (or even reset) by the user or by functions also after the creation
   of objects.
   Examples are `IsQuickPositionList', `CanEasilyTestMembership',
   `IsHandledByNiceBasis'.

(The functions `KnownPropertiesOfObject', `KnownTruePropertiesOfObject',
`KnownAttributesOfObject', `CategoriesOfObject',
and `RepresentationsOfObject' give an overview of the properties,
attributes, categories, and representations of a GAP object,
see the GAP Reference Manual.)

Each *meet of filters* can involve computable simple filters (properties,
attribute and property testers) and not computable simple filters
(categories, representations, other filters).
When one calls a meet of two filters then the two filters from which
the meet was formed are evaluated (if necessary).
So a meet of filters is computable only if at least one computable simple
filter is involved.

Coming to Marc's question whether there is an easy way to find out
whether a filter is a category or a property,
the interesting point seems to be whether a filter is computable or not.
I am not aware of such a function in the current distribution,
but it can be implemented as follows.

    IsComputableFilter:= filt -> IsFilter( filt )
                       and FLAG2_FILTER( filt ) <> 0
                       and (    IsInt( FLAG1_FILTER( filt ) )
                             or IsComputableFilter( FLAG1_FILTER( filt ) )
                             or IsComputableFilter( FLAG2_FILTER( filt ) ) );

Note that this function regards also attribute and property testers
as computable, although one cannot install methods for computing them.

    gap> IsComputableFilter( IsFinite );
    true
    gap> IsComputableFilter( HasSize ); 
    true
    gap> IsComputableFilter( HasIsFinite );
    true
    gap> IsComputableFilter( IsPositionalObjectRep );
    false
    gap> IsComputableFilter( IsInt );                
    false
    gap> IsComputableFilter( IsQuickPositionList );
    false
    gap> IsComputableFilter( IsInt and IsPosRat ); 
    false
    gap> IsComputableFilter( IsMagma );
    false
    gap> IsComputableFilter( IsMagma and IsFinite );
    true

Marc mentioned also that `CategoryCollections( IsInt )' returns `false'
for the list `[ 2 ]' although this list is a collection and consists
only of integers.
The point is that `CategoryCollections( IsInt )' is not a meaningful
filter.
This can be explained as follows.
In addition to the filter values that are stored in the type of an object,
GAP stores one more bit of information in the type
that describes a partition of all GAP objects into so-called families.
Whenever a category is associated to a family F in the sense that each object
in F automatically lies in this category then it makes sense to
form the collections category:
Each object in the collections family of F automatically lies in this
collections category.
This is used for example in the case of permutations, the category `IsPerm'
is `true' for each object in `PermutationsFamily',
and `IsPermCollection' is `true' for each permutation group and for each
dense list of permutations.
The same holds for cyclotomics, which form the family `CyclotomicsFamily',
or for finite field elements in a given characteristic.

However, this does not hold for `IsInt' or `IsRat' or for a possible filter
that might describe elements in a finite prime field.
As stated above, the family information is not hierarchical
but describes just a partition of objects.
Therefore, a list of integers or rationals in GAP does not store in its type
the information that it is a list that consists only of integers or rationals,
respectively.

All the best,
Thomas