In this chapter, we document some additional functionalities that have been implemented in SBStrips but which, really, can stand independently of it. Others may find these useful without caring a jot about SB algebras.
Sometimes it is important to know where in a list an element appears. Sometimes, all that matters is how often it does. (In mathematical terms, these two ideas respectively correspond to a sequence of elements and the multiset of values it takes.) One can of course move from knowing the positions of elements to just knowing their frequency. This is a strict loss of information, but usually not a loss of very important information.
GAP implements this functionality using Collected (Reference: Collected). Calls to this operation yield lists that store information in a more economical, if slightly less informative, fashion, of which SBStrips makes great use. Using Collected on a list list returns another list, detailing the different elements appearing in list and their multiplicity (ie, number of instances) in list.
gap> list := [ "s", "b", "s", "t", "r", "i", "p", "s" ]; [ "s", "b", "s", "t", "r", "i", "p", "s" ] gap> clist := Collected( list ); [ [ "b", 1 ], [ "i", 1 ], [ "p", 1 ], [ "r", 1 ], [ "s", 3 ], [ "t", 1 ] ] gap> entry := clist[5]; [ "s", 3 ]
In the above example, the entry [ "s", 3 ] in clist tells us that the element "s" appears 3 times in list. In other words, "s has multitplicity 3 (in list).
In this documentation, we will use the terms elements and multiplicities respectively to mean the first and second entries of entries of a collected list. So, in the above example, the elements of clist are "b", "i", "p", "r", "s" and "t" and their respective multiplicities are 1, 1, 1, 1, 3 and 1.
What characterises a collected list is that all of its entries are lists of length 2, the second being a positive integer. Elements may be repeated. This doesn't happen from simple uses of Collected, but can result from combining several collected lists, for instance with Collected (Reference: Collected) or Append (Reference: Append).
gap> hello := Collected( [ "h", "e", "l", "l", "o" ] ); [ [ "e", 1 ], [ "h", 1 ], [ "l", 2 ], [ "o", 1 ] ] gap> world := Collected( [ "w", "o", "r", "l", "d" ] ); [ [ "d", 1 ], [ "l", 1 ], [ "o", 1 ], [ "r", 1 ], [ "w", 1 ] ] gap> hello_world := Concatenation( hello, world ); [ [ "e", 1 ], [ "h", 1 ], [ "l", 2 ], [ "o", 1 ], [ "d", 1 ], [ "l", 1 ], [ "o", 1 ], [ "r", 1 ], [ "w", 1 ] ] gap> IsCollectedList( hello_world ); true
Here, the element "l" appears twice in hello_world, first with multiplicity 2 and then again with multiplicity 1. The element "o" also appears twice with multiplicity 1 each time. Despite this repetition, hello_world is still a collected list. It may be "tidied up" using Recollected (6.1-6).
gap> Recollected( hello_world ); [ [ "e", 1 ], [ "h", 1 ], [ "l", 3 ], [ "o", 2 ], [ "d", 1 ], [ "r", 1 ], [ "w", 1 ] ]
‣ IsCollectedList( list ) | ( property ) |
Argument: list, a list
Returns: true if all entries of list are lists of length 2 having a positive integer in their second entry, and false otherwise.
This property will return true on lists returned from the GAP operation Collected (Reference: Collected), as well as on combinations of such lists using Concatenation (Reference: concatenation of lists) or Append (Reference: Append). This is the principal intended use of this property.
When this document refers to a collected list, it means a list for which IsCollectedList returns true.
‣ IsCollectedDuplicateFreeList( clist ) | ( property ) |
Argument: clist
Returns: true if clist is a collected list with no repeated elements
In particular, if clist was created by applying Collected (Reference: Collected) to a duplicate-free list (see IsDuplicateFreeList (Reference: IsDuplicateFreeList)), then this property will return true. This is the principal intended use of this property.
‣ IsCollectedHomogeneousList( clist ) | ( property ) |
Argument: clist, a collected list
Returns: true if the elements of clist form a homogeneous list, and false otherwise
If obj is the result of applying Collected (Reference: Collected) to a homogeneous list, then this property returns true. This is the principal intended use of this property.
‣ ElementsOfCollectedList( clist ) | ( operation ) |
Argument: clist, a collected list.
Returns: the elements of clist.
‣ MultiplicityOfElementInCollectedList( obj, clist ) | ( operation ) |
Arguments: obj, an object; clist, a collected list.
Returns: a nonnegative integer, namely the (total) multiplicity of obj in clist.
‣ Recollected( clist ) | ( operation ) |
Argument: clist, a collected list
Returns: a collected list, removing repeated elements in clist and totalling their multiplicities.
If clist contains entries with matching first entries, say [ obj, n ] and [ obj, m ], then it will combine them into a single entry [ obj, n+m ] with totalised multiplicity. This can be necessary when dealing with concatenations (see Concatenation (Reference: concatenation of lists)) of collected lists.
‣ Uncollected( clist ) | ( operation ) |
Argument: clist, a collected list
Returns: a (flat) list, where each element in clist appears with the appropriate multiplicity
‣ CollectedLength( clist ) | ( attribute ) |
Argument: clist, a collected list
Returns: the sum of the multiplicities in clist
‣ IsCollectedSublist( sublist, superlist ) | ( operation ) |
Arguments: sublist and superlist, two collected lists
Returns: true if each element of sublist occurs in superlist with multiplicity as least that in sublist, and false otherwise.
‣ CollectedListElementwiseFunction( clist, func ) | ( operation ) |
Arguments: clist, a collected list; func, a function
Returns: a new collected list, obtained from clist by applying func to each element.
If func returns lists (perhaps because it implements a "many-valued function"), consider using CollectedListElementwiseListValuedFunction (6.1-11) instead.
‣ CollectedListElementwiseListValuedFunction( clist, func ) | ( operation ) |
Arguments: clist, a collected list; func, a function (presumed to return lists of objects).
Returns: a new collected list.
Imagine clist were unpacked into a flat list, func were applied to each element of the flat list in turn and the result concatenated then collected. That is what this operation returns (although it determines the result more efficiently than the procedure just described).
‣ CollectedFiltered( clist, bool_func ) | ( operation ) |
Arguments: clist, a collected list; bool_func, a function that returns either true or false.
Returns: the collected sublist of clist featuring only those elements for which prop returns true. (Those elements appear in the sublist with the same multiplicity as in clist.)
This should be considered the analogue of Filtered (Reference: Filtered) for collected lists.
generated by GAPDoc2HTML