Make Orbit, Permutation etc. more flexible?

[ThomasBreuer]

I would like to ask for comments about the following situation.

Let us look at functions like Orbit or Permutation from the viewpoint that they apply (group) elements to points, identify the images or their positions in some data structure, and stop when the desired result becomes stable.

Applying an element to a point is done via a function, this is fine. Finding (the position of) a point x, say, in a given data structure, can be done in several ways, for example as follows.

1. Compare x with the candidate points, with GAP's \= function. PermutationOp (there is just one method) does this, plus some attempt to use binary search in the case that it is cheap to sort the given list of points w.r.t. GAP's \<.

2. Find the hash value of x among the hash values of the candidate points, w.r.t. a given hash function. OrbitOp provides a method that uses a dictionary.

3. Call a custom comparison function instead of \=. An example for this idea is provided by PositionCanonical, which is used in PermutationOp. (RightTransversal returns special lists which support PositionCanonical.)

Now think of objects without special functionality in GAP, for example objects from other systems that are handled via the GAPJulia package. One can assume a \= method for such objects, but already \< cannot be expected. GAP knows neither clever dictionaries for these objects nor fancy lists of them with support for the magic of PositionCanonical (which I find anyhow quite unnatural).

Nevertheless, it would make sense to apply Orbit, Permutation, or Action to such objects, without wrapping them in other objects and providing the necessary methods for these new objects, and without implementing new kinds of lists.

A natural way would be to enter the relevant functions for \= or for hashing directly as arguments. Does this make sense?

[hulpke]

I'll leave the \= business aside as I'm not sure what would prevent implementing a \= method for such objects. (Or do I misunderstand and you actually act on equivalence classes given by representatives?) Otherwise:

All the orbit-type algorithms basically just use two functions:

• Add element to orbit
• Test whether an element is in the orbit (and if so at what place).

The intention of dictionaries was to have a uniform interface for this than encompasses sorting, hashing etc. with filters on the family (CanEasilyCompareElements) or the given domain indicating what approach is appropriate. The same could be done for objects that come from externally, and even could use a call to the external program to calculate e.g. hash values.

[ThomasBreuer]

@hulpke Thanks for your comment.

Concerning \=, yes, I think this is the natural place for specifying the intended equivalence relation in situations where either GAP's \= would not do the right thing for the given objects or normalization is not appropriate.

Concerning dictionaries, NewDictionary decides which kind of dictionary object gets created. In the situation which I had sketched (objects that live in Julia, without special functionality in GAP), the objects do not have filters which could help GAP. In the case that one knows a hash function, the recommended solution seems to be that one enters a domain argument D such that UnderlyingCollection( D ) is a record which stores the hash function.

Perhaps the answer to my question is that one should better not try to use GAP's Orbit, Permutation, etc., and write the code in question directly in Julia.

[hulpke]

@ThomasBreuer Yes, if the objects have basically no relevant properties, it is probably easier to write the orbit algorithm in Julia (with teh appropriate equality test) than to hope that GAP's generic machinery will handle it properly. I would be happy however, for suggestions to extend the functionality of dictionaries to make the built-in methods behave better for a broader set of objects.