List vs. Filtered

[alexdegt-ops]

I have discovered a somewhat unexpected behavior. If I create a vector space with an immutable (as in ImmutableMatrix) basis, e.g., via GF(2)^5, and apply List to the result, I get a list of ImmutableVector's. However, if I apply Filtered, I get plain lists instead, which makes life difficult. Is this a feature or a bug? Currently, I'm using version 4.12.2pre on Win 11.

[fingolfin]

If I create a vector space with an immutable (as in ImmutableMatrix) basis, e.g., via GF(2)^5, and apply List to the result, I get a list of ImmutableVector's

I am not actually sure what you mean by that; please consider posting actual code (snippets) along with your questions, that will clarify what you mean and avoid confusion.

So here are some general remarks:

In GAP, historically matrices were implemented as lists-of-lists. This is why functions like List and Filtered can even be applied to them at all: these functions take a list (or iterable) and return a list.

This list-of-lists approach at first seems neat and elegant, but it has many serious downsides. To address this for finite fields, "compressed matrices" were invented which try to be better matrices than plain lists of lists -- but at heart they still are lists of (row) vectors.

Some tools then recognize their input is a compressed matrix and try to produce an output that is, too, but not all do (and not for all would it even make sense). The Filtered operationsi among them which don't try to preserve this "compressed matrix" status.

It is not clear to me how yo uget from "a basis of GF(2)^5" to an "immutable matrix". E.g.

Fgap> V:=GF(2)^5;
( GF(2)^5 )
gap> B:=Basis(V);
CanonicalBasis( ( GF(2)^5 ) )
gap> C:=Filtered(B, v -> IsZero(v[1]));
[ <an immutable GF2 vector of length 5>, <an immutable GF2 vector of length 5>,
  <an immutable GF2 vector of length 5>, <an immutable GF2 vector of length 5> ]

This does not involve any immutable matrices.

Though if I really wanted to, I could turn list list of four vectors into a "compressed matrix" (which after all is just a special kind of lists anyway):

gap> ConvertToMatrixRep(C);
2
gap> C;
<a 4x5 matrix over GF2>

[alexdegt-ops]

Apparently, my installation is either way too outdated or broken. What I get is

gap> V := GF(2)^3;
( GF(2)^3 )
gap> list := List(V);; last[1];
<an immutable GF2 vector of length 3>
gap> Filtered(V, ReturnTrue);; last[1];
[ 0*Z(2), 0*Z(2), 0*Z(2) ]
gap> Filtered(list, ReturnTrue);; last[1];
<an immutable GF2 vector of length 3>
gap> GAPInfo.Version;
"4.12.2pre"

and it is this behavior that I reported as inconsistent. In fact, it took me quite a while to figure out why one approach is much slower than the other. Accidentally, do I take it right from the manual that ImmutableVector and ImmutableMatrix are ultimately the fastest representations for linear algebra over Z/2?

[fingolfin]

I am not sure why you think any of this implies your installation is outdated or broken? I get the exact same output. Also note that nothing in that example involves immutable matrices either.

The root cause is that the code which implements iteration over vector spaces does not bother to return compressed vectors (possibly because it predates their invention). The function Filtered uses the iteration interface -- as does List(coll, func). But there is a special method List(vecspace) it seems. Hence:

gap> List(V);
[ <an immutable GF2 vector of length 3>, <an immutable GF2 vector of length 3>,
  <an immutable GF2 vector of length 3>, <an immutable GF2 vector of length 3>,
  <an immutable GF2 vector of length 3>, <an immutable GF2 vector of length 3>,
  <an immutable GF2 vector of length 3>, <an immutable GF2 vector of length 3> ]

but using the general List(coll, func) gives this:

gap> List(V, x->x);
[ [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ], [ 0*Z(2), Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, Z(2)^0 ],
  [ Z(2)^0, 0*Z(2), 0*Z(2) ], [ Z(2)^0, 0*Z(2), Z(2)^0 ], [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ] ]

The code implementing these two are in EnumeratorByBasis resp. IteratorByBasis. The former has a special case for "small fields" (with less than 256 elements), which is why you see those immutable compressed vectors. The latter does not have this

[alexdegt-ops]

OK, thanks. I agree that GAP never guarantees a particular representation of the output (unless it's a representation conversion function), and this makes perfect sense and increases the flexibility, but still it's a bit inconsistent.