|
|
|
|
Quelle chap30.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/doc/ref/chap30.html |
 |
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (ref) - Chapter 30: Collections</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap30" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chap19.html">19</a> <a href="chap20.html">20</a> <a href="chap21.html">21</a> <a href="chap22.html">22</a> <a href="chap23.html">23</a> <a href="chap24.html">24</a> <a href="chap25.html">25</a> <a href="chap26.html">26</a> <a href="chap27.html">27</a> <a href="chap28.html">28</a> <a href="chap29.html">29</a> <a href="chap30.html">30</a> <a href="chap31.html">31</a> <a href="chap32.html">32</a> <a href="chap33.html">33</a> <a href="chap34.html">34</a> <a href="chap35.html">35</a> <a href="chap36.html">36</a> <a href="chap37.html">37</a> <a href="chap38.html">38</a> <a href="chap39.html">39</a> <a href="chap40.html">40</a> <a href="chap41.html">41</a> <a href="chap42.html">42</a> <a href="chap43.html">43</a> <a href="chap44.html">44</a> <a href="chap45.html">45</a> <a href="chap46.html">46</a> <a href="chap47.html">47</a> <a href="chap48.html">48</a> <a href="chap49.html">49</a> <a href="chap50.html">50</a> <a href="chap51.html">51</a> <a href="chap52.html">52</a> <a href="chap53.html">53</a> <a href="chap54.html">54</a> <a href="chap55.html">55</a> <a href="chap56.html">56</a> <a href="chap57.html">57</a> <a href="chap58.html">58</a> <a href="chap59.html">59</a> <a href="chap60.html">60</a> <a href="chap61.html">61</a> <a href="chap62.html">62</a> <a href="chap63.html">63</a> <a href="chap64.html">64</a> <a href="chap65.html">65</a> <a href="chap66.html">66</a> <a href="chap67.html">67</a> <a href="chap68.html">68</a> <a href="chap69.html">69</a> <a href="chap70.html">70</a> <a href="chap71.html">71</a> <a href="chap72.html">72</a> <a href="chap73.html">73</a> <a href="chap74.html">74</a> <a href="chap75.html">75</a> <a href="chap76.html">76</a> <a href="chap77.html">77</a> <a href="chap78.html">78</a> <a href="chap79.html">79</a> <a href="chap80.html">80</a> <a href="chap81.html">81</a> <a href="chap82.html">82</a> <a href="chap83.html">83</a> <a href="chap84.html">84</a> <a href="chap85.html">85</a> <a href="chap86.html">86</a> <a href="chap87.html">87</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap29.html">[Previous Chapter]</a> <a href="chap31.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap30_mj.html">[MathJax on]</a></p>
<p><a id="X8050A8037984E5B6" name="X8050A8037984E5B6"></a></p>
<div class="ChapSects"><a href="chap30.html#X8050A8037984E5B6">30 <span class="Heading">Collections</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap30.html#X8084F03A78ABD4F8">30.1 <span class="Heading">IsCollection (Filter)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X79C9FC7F86E2738C">30.1-1 IsCollection</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap30.html#X85D8D8F684B02DDF">30.2 <span class="Heading">Collection Families</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X84E5A67E87D8DD66">30.2-1 CollectionsFamily</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X856AC2DF7F7CBAAF">30.2-2 IsCollectionFamily</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X864BB3748546F63F">30.2-3 ElementsFamily</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X78C38017804B2EA7">30.2-4 CategoryCollections</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X85ABC1B4829778C7">30.2-5 DeclareCategoryCollections</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap30.html#X7C3722DF8736FFDB">30.3 <span class="Heading">Lists and Collections</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X877128A77826DD69">30.3-1 IsListOrCollection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7EF8910F82B45EC7">30.3-2 Enumerator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X80CD7DDC7D0C60D5">30.3-3 EnumeratorSorted</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X85E149177AC547C3">30.3-4 EnumeratorByFunctions</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7F12F40E87F3C3A7">30.3-5 List</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X82CE157A7FAD8036">30.3-6 SortedList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7E399AC97FD98217">30.3-7 SSortedList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X8289FCCC8274C89D">30.3-8 AsList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7BCA5C6181391007">30.3-9 AsSortedList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X856D927378C33548">30.3-10 AsSSortedList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X79B130FC7906FB4C">30.3-11 Elements</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap30.html#X79AD18737E70B414">30.4 <span class="Heading">Attributes and Properties for Collections</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7969C48780C5C1BC">30.4-1 IsEmpty</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X808A4061809A6E67">30.4-2 IsFinite</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7E3402D6799D3C24">30.4-3 IsTrivial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7F192373850B85B9">30.4-4 IsNonTrivial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X78EF6A137E8F66B0">30.4-5 IsWholeFamily</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X858ADA3B7A684421">30.4-6 Size</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X865507568182424E">30.4-7 Representative</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X8026085680270D37">30.4-8 RepresentativeSmallest</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap30.html#X7F8FEA3278239ADE">30.5 <span class="Heading">Operations for Collections</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X79CA175481F8105F">30.5-1 IsSubset</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X851069107CACF98E">30.5-2 <span class="Heading">Intersection</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X799F0E2F7A502DBA">30.5-3 <span class="Heading">Union</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X825AC0F07E010B07">30.5-4 Difference</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap30.html#X82D39CF980FDBFFA">30.6 <span class="Heading">Membership Test for Collections</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X84B7FA8C7C94400F"><code>30.6-1 \in</code></a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap30.html#X8151A51884B7EE2C">30.7 <span class="Heading">Random Elements</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7FF906E57D6936F8">30.7-1 Random</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X811B5BD47DC5356B">30.7-2 PseudoRandom</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7EBA01EB83BC65A9">30.7-3 RandomList</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap30.html#X85A3F00985453F95">30.8 <span class="Heading">Iterators</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X83ADF8287ED0668E">30.8-1 Iterator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X8688C20B828FC129">30.8-2 IteratorSorted</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X87168A827E5B28E4">30.8-3 IsIterator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X8055FC557B5D899E">30.8-4 IsDoneIterator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X879F62F77D1D1179">30.8-5 NextIterator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X858A28667D137C4B">30.8-6 IteratorList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X7DB80BE68271247E">30.8-7 TrivialIterator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap30.html#X82677D8F817D6701">30.8-8 IteratorByFunctions</a></span>
</div></div>
</div>
<h3>30 <span class="Heading">Collections</span></h3>
<p>A <em>collection</em> in <strong class="pkg">GAP</strong> consists of elements in the same family (see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>). The most important kinds of collections are <em>homogeneous lists</em> (see <a href="chap21.html#X7B256AE5780F140A"><span class="RefLink">21</span></a>) and <em>domains</em> (see <a href="chap12.html#X7BAF69417BB925F6"><span class="RefLink">12.4</span></a>). 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>
<p>Basic operations for collections are <code class="func">Size</code> (<a href="chap30.html#X858ADA3B7A684421"><span class="RefLink">30.4-6</span></a>) and <code class="func">Enumerator</code> (<a href="chap30.html#X7EF8910F82B45EC7"><span class="RefLink">30.3-2</span></a>); for <em>finite</em> collections, <code class="func">Enumerator</code> (<a href="chap30.html#X7EF8910F82B45EC7"><span class="RefLink">30.3-2</span></a>) admits to delegate the other operations for collections (see <a href="chap30.html#X79AD18737E70B414"><span class="RefLink">30.4</span></a> and <a href="chap30.html#X7F8FEA3278239ADE"><span class="RefLink">30.5</span></a>) to functions for lists (see <a href="chap21.html#X7B256AE5780F140A"><span class="RefLink">21</span></a>). Obviously, special methods depending on the arguments are needed for the computation of e.g. the intersection of two <em>infinite</em> domains.</p>
<p><a id="X8084F03A78ABD4F8" name="X8084F03A78ABD4F8"></a></p>
<h4>30.1 <span class="Heading">IsCollection (Filter)</span></h4>
<p><a id="X79C9FC7F86E2738C" name="X79C9FC7F86E2738C"></a></p>
<h5>30.1-1 IsCollection</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCollection</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>tests whether an object is a collection.</p>
<p>Some of the functions for lists and collections are described in the chapter about lists, mainly in Section <a href="chap21.html#X7DF510F7848CBBFD"><span class="RefLink">21.20</span></a>. 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>.</p>
<p><a id="X85D8D8F684B02DDF" name="X85D8D8F684B02DDF"></a></p>
<h4>30.2 <span class="Heading">Collection Families</span></h4>
<p><a id="X84E5A67E87D8DD66" name="X84E5A67E87D8DD66"></a></p>
<h5>30.2-1 CollectionsFamily</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CollectionsFamily</code>( <var class="Arg">Fam</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>For a family <var class="Arg">Fam</var>, <code class="func">CollectionsFamily</code> returns the family of all collections over <var class="Arg">Fam</var>, that is, of all dense lists and domains that consist of objects in <var class="Arg">Fam</var>.</p>
<p>The <code class="func">NewFamily</code> (<a href="chap13.html#X7FB4123E7E22137D"><span class="RefLink">13.1-2</span></a>) call in the standard method of <code class="func">CollectionsFamily</code> is executed with second argument <code class="func">IsCollection</code> (<a href="chap30.html#X79C9FC7F86E2738C"><span class="RefLink">30.1-1</span></a>), 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 <var class="Arg">Fam</var>.</p>
<p>Note that families (see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>) are used to describe relations between objects. Important such relations are that between an element <span class="SimpleMath">e</span> and each collection of elements that lie in the same family as <span class="SimpleMath">e</span>, and that between two collections whose elements lie in the same family. Therefore, all collections of elements in the family <var class="Arg">Fam</var> form the new family <code class="code">CollectionsFamily( <var class="Arg">Fam</var> )</code>.</p>
<p><a id="X856AC2DF7F7CBAAF" name="X856AC2DF7F7CBAAF"></a></p>
<h5>30.2-2 IsCollectionFamily</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCollectionFamily</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>is <code class="keyw">true</code> if <var class="Arg">Fam</var> is a family of collections, and <code class="keyw">false</code> otherwise.</p>
<p><a id="X864BB3748546F63F" name="X864BB3748546F63F"></a></p>
<h5>30.2-3 ElementsFamily</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ElementsFamily</code>( <var class="Arg">Fam</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>If <var class="Arg">Fam</var> is a collections family (see <code class="func">IsCollectionFamily</code> (<a href="chap30.html#X856AC2DF7F7CBAAF"><span class="RefLink">30.2-2</span></a>)) then <code class="func">ElementsFamily</code> returns the family from which <var class="Arg">Fam</var> was created by <code class="func">CollectionsFamily</code> (<a href="chap30.html#X84E5A67E87D8DD66"><span class="RefLink">30.2-1</span></a>). The way a collections family is created, it always has its elements family stored. If <var class="Arg">Fam</var> is not a collections family then an error is signalled.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">fam:= FamilyObj( (1,2) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">collfam:= CollectionsFamily( fam );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fam = collfam; fam = ElementsFamily( collfam );</span>
false
true
<span class="GAPprompt">gap></span> <span class="GAPinput">collfam = FamilyObj( [ (1,2,3) ] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">collfam = FamilyObj( Group( () ) );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">collfam = CollectionsFamily( collfam );</span>
false
</pre></div>
<p><a id="X78C38017804B2EA7" name="X78C38017804B2EA7"></a></p>
<h5>30.2-4 CategoryCollections</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CategoryCollections</code>( <var class="Arg">filter</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">filter</var> be a filter that is <code class="keyw">true</code> for all elements of a family <var class="Arg">Fam</var>, by the construction of <var class="Arg">Fam</var>. Then <code class="func">CategoryCollections</code> returns the <em>collections category</em> of <var class="Arg">filter</var>. This is a category that is <code class="keyw">true</code> for all elements in <code class="code">CollectionsFamily( <var class="Arg">Fam</var> )</code>.</p>
<p>For example, the construction of <code class="func">PermutationsFamily</code> (<a href="chap42.html#X819628B083B3939B"><span class="RefLink">42.1-3</span></a>) guarantees that each of its elements lies in the filter <code class="func">IsPerm</code> (<a href="chap42.html#X7AA69C6686FC49EA"><span class="RefLink">42.1-1</span></a>), and each collection of permutations (permutation group or dense list of permutations) lies in the category <code class="code">CategoryCollections( IsPerm )</code>. <code class="code">CategoryCollections( IsPerm )</code>. Note that this works only if the collections category is created <em>before</em> the collections family. So it is necessary to construct interesting collections categories immediately after the underlying category has been created.</p>
<p><a id="X85ABC1B4829778C7" name="X85ABC1B4829778C7"></a></p>
<h5>30.2-5 DeclareCategoryCollections</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DeclareCategoryCollections</code>( <var class="Arg">name</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Calls <code class="func">CategoryCollections</code> (<a href="chap30.html#X78C38017804B2EA7"><span class="RefLink">30.2-4</span></a>) on the category that is bound to the global variable with name <var class="Arg">name</var> to obtain its collections category, and binds the latter to the global variable with name <code class="code">nname</code>. This name is defined as follows: If <var class="Arg">name</var> is of the form <code class="code"><var class="Arg">Something</var>Collection</code> then <code class="code">nname</code> is set to <code class="code"><var class="Arg">Something</var>CollColl</code>, if <var class="Arg">name</var> is of the form <code class="code"><var class="Arg">Something</var>Coll</code> then <code class="code">nname</code> is set to <code class="code"><var class="Arg">Something</var>CollColl</code>, otherwise we set <code class="code">nname</code> to <code class="code"><var class="Arg">name</var>Collection</code>.</p>
<p><a id="X7C3722DF8736FFDB" name="X7C3722DF8736FFDB"></a></p>
<h4>30.3 <span class="Heading">Lists and Collections</span></h4>
<p>The following functions take a <em>list or collection</em> as argument, and return a corresponding <em>list</em>. They differ in whether or not the result is mutable or immutable (see <a href="chap12.html#X7F0C119682196D65"><span class="RefLink">12.6</span></a>), guaranteed to be sorted, or guaranteed to admit list access in constant time (see <code class="func">IsConstantTimeAccessList</code> (<a href="chap21.html#X7C84E16A85C99C8C"><span class="RefLink">21.1-6</span></a>)).</p>
<p><a id="X877128A77826DD69" name="X877128A77826DD69"></a></p>
<h5>30.3-1 IsListOrCollection</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsListOrCollection</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Several functions are defined for both lists and collections, for example <code class="func">Intersection</code> (<a href="chap30.html#X851069107CACF98E"><span class="RefLink">30.5-2</span></a>), <code class="func">Iterator</code> (<a href="chap30.html#X83ADF8287ED0668E"><span class="RefLink">30.8-1</span></a>), and <code class="func">Random</code> (<a href="chap30.html#X7FF906E57D6936F8"><span class="RefLink">30.7-1</span></a>). <code class="func">IsListOrCollection</code> is a supercategory of <code class="func">IsList</code> (<a href="chap21.html#X7C4CC4EA8299701E"><span class="RefLink">21.1-1</span></a>) and <code class="func">IsCollection</code> (<a href="chap30.html#X79C9FC7F86E2738C"><span class="RefLink">30.1-1</span></a>) (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.</p>
<p><a id="X7EF8910F82B45EC7" name="X7EF8910F82B45EC7"></a></p>
<h5>30.3-2 Enumerator</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Enumerator</code>( <var class="Arg">listorcoll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">Enumerator</code> returns an immutable list <span class="SimpleMath">enum</span>. If the argument is a list (which may contain holes), then <code class="code">Length( </code><span class="SimpleMath">enum</span><code class="code"> )</code> is the length of this list, and <span class="SimpleMath">enum</span> contains the elements (and holes) of this list in the same order. If the argument is a collection that is not a list, then <code class="code">Length( </code><span class="SimpleMath">enum</span><code class="code"> )</code> is the number of different elements of <var class="Arg">C</var>, and <span class="SimpleMath">enum</span> contains the different elements of the collection in an unspecified order, which may change for repeated calls of <code class="func">Enumerator</code>. <span class="SimpleMath">enum[pos]</span> may not execute in constant time (see <code class="func">IsConstantTimeAccessList</code> (<a href="chap21.html#X7C84E16A85C99C8C"><span class="RefLink">21.1-6</span></a>)), and the size of <span class="SimpleMath">enum</span> in memory is as small as is feasible.</p>
<p>For lists, the default method is <code class="func">Immutable</code> (<a href="chap12.html#X7F0ABF2C870B0CBB"><span class="RefLink">12.6-3</span></a>). For collections that are not lists, there is no default method.</p>
<p><a id="X80CD7DDC7D0C60D5" name="X80CD7DDC7D0C60D5"></a></p>
<h5>30.3-3 EnumeratorSorted</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnumeratorSorted</code>( <var class="Arg">listorcoll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">EnumeratorSorted</code> returns an immutable list <span class="SimpleMath">enum</span>. The argument must be a collection or a list <var class="Arg">listorcoll</var> which may contain holes but whose elements lie in the same family (see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>). <code class="code">Length( </code><span class="SimpleMath">enum</span><code class="code"> )</code> is the number of different elements of the argument, and <span class="SimpleMath">enum</span> contains the different elements in sorted order, w.r.t. <code class="code"><</code>. <span class="SimpleMath">enum[pos]</span> may not execute in constant time (see <code class="func">IsConstantTimeAccessList</code> (<a href="chap21.html#X7C84E16A85C99C8C"><span class="RefLink">21.1-6</span></a>)), and the size of <span class="SimpleMath">enum</span> in memory is as small as is feasible.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Enumerator( [ 1, 3,, 2 ] );</span>
[ 1, 3,, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">enum:= Enumerator( Rationals );; elm:= enum[ 10^6 ];</span>
-69/907
<span class="GAPprompt">gap></span> <span class="GAPinput">Position( enum, elm );</span>
1000000
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable( enum ); IsSortedList( enum );</span>
false
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsConstantTimeAccessList( enum );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">EnumeratorSorted( [ 1, 3,, 2 ] );</span>
[ 1, 2, 3 ]
</pre></div>
<p><a id="X85E149177AC547C3" name="X85E149177AC547C3"></a></p>
<h5>30.3-4 EnumeratorByFunctions</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnumeratorByFunctions</code>( <var class="Arg">D</var>, <var class="Arg">record</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnumeratorByFunctions</code>( <var class="Arg">Fam</var>, <var class="Arg">record</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">EnumeratorByFunctions</code> returns an immutable, dense, and duplicate-free list <span class="SimpleMath">enum</span> for which <code class="func">IsBound</code> (<a href="chap21.html#X79EC565A7DCEC938"><span class="RefLink">21.5-1</span></a>), element access via <code class="func"><span>\</span>[<span>\</span>]</code> (<a href="chap21.html#X8297BBCD79642BE6"><span class="RefLink">21.2-1</span></a>), <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>), and <code class="func">Position</code> (<a href="chap21.html#X79975EC6783B4293"><span class="RefLink">21.16-1</span></a>) are computed via prescribed functions.</p>
<p>Let <var class="Arg">record</var> be a record with at least the following components.</p>
<dl>
<dt><strong class="Mark"><code class="code">ElementNumber</code></strong></dt>
<dd><p>a function taking two arguments <var class="Arg">enum</var> and <var class="Arg">pos</var>, which returns <code class="code"><var class="Arg">enum</var>[ <var class="Arg">pos</var> ]</code> (see <a href="chap21.html#X7B202D147A5C2884"><span class="RefLink">21.2</span></a>); it can be assumed that the argument <var class="Arg">pos</var> is a positive integer, but <var class="Arg">pos</var> may be larger than the length of <var class="Arg">enum</var> (in which case an error must be signalled); note that the result must be immutable since <var class="Arg">enum</var> itself is immutable,</p>
</dd>
<dt><strong class="Mark"><code class="code">NumberElement</code></strong></dt>
<dd><p>a function taking two arguments <var class="Arg">enum</var> and <var class="Arg">elm</var>, which returns <code class="code">Position( <var class="Arg">enum</var>, <var class="Arg">elm</var> )</code> (see <code class="func">Position</code> (<a href="chap21.html#X79975EC6783B4293"><span class="RefLink">21.16-1</span></a>)); it cannot be assumed that <var class="Arg">elm</var> is really contained in <var class="Arg">enum</var> (and <code class="keyw">fail</code> must be returned if not); note that for the three argument version of <code class="func">Position</code> (<a href="chap21.html#X79975EC6783B4293"><span class="RefLink">21.16-1</span></a>), the method that is available for duplicate-free lists suffices.</p>
</dd>
</dl>
<p>Further (data) components may be contained in <var class="Arg">record</var> which can be used by these function.</p>
<p>If the first argument is a domain <var class="Arg">D</var> then <var class="Arg">enum</var> lists the elements of <var class="Arg">D</var> (in general <var class="Arg">enum</var> is <em>not</em> sorted), and methods for <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>), <code class="func">IsBound</code> (<a href="chap21.html#X79EC565A7DCEC938"><span class="RefLink">21.5-1</span></a>), and <code class="func">PrintObj</code> (<a href="chap6.html#X815BF22186FD43C9"><span class="RefLink">6.3-5</span></a>) may use <var class="Arg">D</var>.</p>
<p>If one wants to describe the result without creating a domain then the elements are given implicitly by the functions in <var class="Arg">record</var>, and the first argument must be a family <var class="Arg">Fam</var> which will become the family of <var class="Arg">enum</var>; if <var class="Arg">enum</var> is not homogeneous then <var class="Arg">Fam</var> must be <code class="code">ListsFamily</code>, otherwise it must be the collections family of any element in <var class="Arg">enum</var>. In this case, additionally the following component in <var class="Arg">record</var> is needed.</p>
<dl>
<dt><strong class="Mark"><code class="code">Length</code></strong></dt>
<dd><p>a function taking the argument <var class="Arg">enum</var>, which returns the length of <var class="Arg">enum</var> (see <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>)).</p>
</dd>
</dl>
<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.</p>
<dl>
<dt><strong class="Mark"><code class="code">IsBound\[\]</code></strong></dt>
<dd><p>a function taking two arguments <var class="Arg">enum</var> and <var class="Arg">k</var>, which returns <code class="code">IsBound( <var class="Arg">enum</var>[ <var class="Arg">k</var> ] )</code> (see <a href="chap21.html#X7B202D147A5C2884"><span class="RefLink">21.2</span></a>); if this component is missing then <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>) is used for computing the result,</p>
</dd>
<dt><strong class="Mark"><code class="code">Membership</code></strong></dt>
<dd><p>a function taking two arguments <var class="Arg">elm</var> and <var class="Arg">enum</var>, which returns <code class="keyw">true</code> is <var class="Arg">elm</var> is an element of <var class="Arg">enum</var>, and <code class="keyw">false</code> otherwise (see <a href="chap21.html#X7B202D147A5C2884"><span class="RefLink">21.2</span></a>); if this component is missing then <code class="code">NumberElement</code> is used for computing the result,</p>
</dd>
<dt><strong class="Mark"><code class="code">AsList</code></strong></dt>
<dd><p>a function taking one argument <var class="Arg">enum</var>, which returns a list with the property that the access to each of its elements will take roughly the same time (see <code class="func">IsConstantTimeAccessList</code> (<a href="chap21.html#X7C84E16A85C99C8C"><span class="RefLink">21.1-6</span></a>)); if this component is missing then <code class="func">ConstantTimeAccessList</code> (<a href="chap21.html#X7B55FB967CDEF468"><span class="RefLink">21.17-6</span></a>) is used for computing the result,</p>
</dd>
<dt><strong class="Mark"><code class="code">ViewObj</code> and <code class="code">PrintObj</code></strong></dt>
<dd><p>two functions that print what one wants to be printed when <code class="code">View( <var class="Arg">enum</var> )</code> or <code class="code">Print( <var class="Arg">enum</var> )</code> is called (see <a href="chap6.html#X8074A8387C9DB9A8"><span class="RefLink">6.3</span></a>), if the <code class="code">ViewObj</code> component is missing then the <code class="code">PrintObj</code> method is used as a default.</p>
</dd>
</dl>
<p>If the result is known to have additional properties such as being strictly sorted (see <code class="func">IsSSortedList</code> (<a href="chap21.html#X80CDAF45782E8DCB"><span class="RefLink">21.17-4</span></a>)) 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 <code class="func">EnumeratorByFunctions</code>, and this construction is installed as a method for the operation <code class="func">Enumerator</code> (<a href="chap30.html#X7EF8910F82B45EC7"><span class="RefLink">30.3-2</span></a>), then it should be installed also as a method for <code class="func">EnumeratorSorted</code> (<a href="chap30.html#X80CD7DDC7D0C60D5"><span class="RefLink">30.3-3</span></a>).</p>
<p>Note that it is <em>not</em> checked that <code class="func">EnumeratorByFunctions</code> really returns a dense and duplicate-free list. <code class="func">EnumeratorByFunctions</code> does <em>not</em> make a shallow copy of <var class="Arg">record</var>, this record is changed in place, see <a href="chap79.html#X82E86CF37B123FD4"><span class="RefLink">79.1</span></a>.</p>
<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 <code class="func">Position</code> (<a href="chap21.html#X79975EC6783B4293"><span class="RefLink">21.16-1</span></a>) is supported), but the resulting overhead for the methods seems not to be justified.</p>
<p><a id="X7F12F40E87F3C3A7" name="X7F12F40E87F3C3A7"></a></p>
<h5>30.3-5 List</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ List</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For a collection <var class="Arg">C</var> (see <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a>) that is not a list, <code class="func">List</code> returns a new mutable list <var class="Arg">new</var> such that <code class="code">Length( <var class="Arg">new</var> )</code> is the number of different elements of <var class="Arg">C</var>, and <var class="Arg">new</var> contains the different elements of <var class="Arg">C</var> in an unspecified order which may change for repeated calls. <code class="code"><var class="Arg">new</var>[<var class="Arg">pos</var>]</code> executes in constant time (see <code class="func">IsConstantTimeAccessList</code> (<a href="chap21.html#X7C84E16A85C99C8C"><span class="RefLink">21.1-6</span></a>)), and the size of <var class="Arg">new</var> is proportional to its length. The generic method for this case is <code class="code">ShallowCopy( Enumerator( <var class="Arg">C</var> ) )</code>.</p>
<p>Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation <code class="code">ListOp</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= List( Group( (1,2,3) ) );</span>
[ (), (1,3,2), (1,2,3) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );</span>
true
false
true
</pre></div>
<p>(See also <code class="func">List</code> (<a href="chap21.html#X86CB7DCE8510F977"><span class="RefLink">21.20-18</span></a>).)</p>
<p><a id="X82CE157A7FAD8036" name="X82CE157A7FAD8036"></a></p>
<h5>30.3-6 SortedList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SortedList</code>( <var class="Arg">listorcoll</var>[, <var class="Arg">func</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SortedListBy</code>( <var class="Arg">listorcoll</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">SortedList</code> returns a new mutable and dense list <var class="Arg">new</var>. The argument must be a collection or list <var class="Arg">listorcoll</var> which may contain holes but whose elements lie in the same family (see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>). <code class="code">Length( <var class="Arg">new</var> )</code> is the number of elements of <var class="Arg">listorcoll</var>, and <var class="Arg">new</var> contains the elements in sorted order, w.r.t. <code class="code"><</code> or <var class="Arg">func</var> if it is specified. For details, please refer to <code class="func">Sort</code> (<a href="chap21.html#X7FE4975F8166884D"><span class="RefLink">21.18-1</span></a>).</p>
<p><code class="func">SortedListBy</code> also returns a new mutable and dense list <var class="Arg">new</var>. The first argument must be a collection or list <var class="Arg">listorcoll</var> which may contain holes but whose elements lie in the same family (see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>). <code class="code">Length( <var class="Arg">new</var> )</code> is the number of elements of <var class="Arg">listorcoll</var>, and <var class="Arg">new</var> has elements in an order such that <code class="code">func(new[i]) <= func(new[i+1])</code> for all relevant <var class="Arg">i</var>. <var class="Arg">func</var> must thus be a function on one argument which returns values that can be compared. Each <code class="code">func(listorcoll[i])</code> is computed just once and stored, making this more efficient than using the two-argument version of <code class="func">SortedList</code> in many cases.</p>
<p>In both cases, <code class="code"><var class="Arg">new</var>[<var class="Arg">pos</var>]</code> executes in constant time (see <code class="func">IsConstantTimeAccessList</code> (<a href="chap21.html#X7C84E16A85C99C8C"><span class="RefLink">21.1-6</span></a>)), and the size of <var class="Arg">new</var> in memory is proportional to its length.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= SortedList( Group( (1,2,3) ) );</span>
[ (), (1,2,3), (1,3,2) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );</span>
true
true
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SortedList( [ 1, 2, 1,, 3, 2 ] );</span>
[ 1, 1, 2, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SortedListBy(SymmetricGroup(3), Order);</span>
[ (), (1,3), (2,3), (1,2), (1,2,3), (1,3,2) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SortedListBy( [ 3, 1,,, -6, 5, -2,, -5, 3, 3,,, -1 ], x -> x^2 );</span>
[ 1, -1, -2, 3, 3, 3, 5, -5, -6 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l:=SortedListBy( [ 2, 1,, 1, -5,, 3, -5 ], x -> x^3);</span>
[ -5, -5, 1, 1, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );</span>
true
true
true
</pre></div>
<p><a id="X7E399AC97FD98217" name="X7E399AC97FD98217"></a></p>
<h5>30.3-7 SSortedList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SSortedList</code>( <var class="Arg">listorcoll</var>[, <var class="Arg">fun</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Set</code>( <var class="Arg">C</var>[, <var class="Arg">fun</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">SSortedList</code> (<q>strictly sorted list</q>) returns a new dense, mutable, and duplicate free list <var class="Arg">new</var>. The argument must be a collection or list <var class="Arg">listorcoll</var> which may contain holes.</p>
<p>If the optional argument <var class="Arg">fun</var> is not given then <code class="code">Length( <var class="Arg">new</var> )</code> is the number of different elements of <var class="Arg">listorcoll</var>, and <var class="Arg">new</var> contains the different elements in strictly sorted order, w.r.t. <code class="func">\<</code> (<a href="chap31.html#X7EF67D047F03CA6F"><span class="RefLink">31.11-1</span></a>). For that, any two entries of <var class="Arg">listorcoll</var> must be comparable via <code class="func">\<</code> (<a href="chap31.html#X7EF67D047F03CA6F"><span class="RefLink">31.11-1</span></a>). (Typically, the entries lie in the same family, see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>.)</p>
<p>If <var class="Arg">fun</var> is given then it must be a unary function. In this case, <var class="Arg">fun</var> is applied to all elements of <var class="Arg">listorcoll</var>, <var class="Arg">new</var> contains the different return values in strictly sorted order, and <code class="code">Length( <var class="Arg">new</var> )</code> is the number of different such values. For that, any two return values must be comparable via <code class="func">\<</code> (<a href="chap31.html#X7EF67D047F03CA6F"><span class="RefLink">31.11-1</span></a>).</p>
<p><code class="code"><var class="Arg">new</var>[<var class="Arg">pos</var>]</code> executes in constant time (see <code class="func">IsConstantTimeAccessList</code> (<a href="chap21.html#X7C84E16A85C99C8C"><span class="RefLink">21.1-6</span></a>)), and the size of <var class="Arg">new</var> in memory is proportional to its length.</p>
<p><code class="func">Set</code> is simply a synonym for <code class="func">SSortedList</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= SSortedList( Group( (1,2,3) ) );</span>
[ (), (1,2,3), (1,3,2) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable( l ); IsSSortedList( l ); IsConstantTimeAccessList( l );</span>
true
true
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SSortedList( Group( (1,2,3) ), Order );</span>
[ 1, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SSortedList( [ 1, 2, 1,, 3, 2 ] );</span>
[ 1, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SSortedList( [ 1, 2, 1,, 3, 2 ], x -> x^2 );</span>
[ 1, 4, 9 ]
</pre></div>
<p><a id="X8289FCCC8274C89D" name="X8289FCCC8274C89D"></a></p>
<h5>30.3-8 AsList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsList</code>( <var class="Arg">listorcoll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">AsList</code> returns a immutable list <var class="Arg">imm</var>. If the argument is a list (which may contain holes), then <code class="code">Length( <var class="Arg">imm</var> )</code> is the <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>) value of this list, and <var class="Arg">imm</var> contains the elements (and holes) of the list in the same order. If the argument is a collection that is not a list, then <code class="code">Length( <var class="Arg">imm</var> )</code> is the number of different elements of this collection, and <var class="Arg">imm</var> contains the different elements of the collection in an unspecified order, which may change for repeated calls of <code class="func">AsList</code>. <code class="code"><var class="Arg">imm</var>[<var class="Arg">pos</var>]</code> executes in constant time (see <code class="func">IsConstantTimeAccessList</code> (<a href="chap21.html#X7C84E16A85C99C8C"><span class="RefLink">21.1-6</span></a>)), and the size of <var class="Arg">imm</var> in memory is proportional to its length.</p>
<p>If you expect to do many element tests in the resulting list, it might be worth to use a sorted list instead, using <code class="func">AsSSortedList</code> (<a href="chap30.html#X856D927378C33548"><span class="RefLink">30.3-10</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= AsList( [ 1, 3, 3,, 2 ] );</span>
[ 1, 3, 3,, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );</span>
false
false
true
<span class="GAPprompt">gap></span> <span class="GAPinput">AsList( Group( (1,2,3), (1,2) ) );</span>
[ (), (2,3), (1,3,2), (1,3), (1,2,3), (1,2) ]
</pre></div>
<p><a id="X7BCA5C6181391007" name="X7BCA5C6181391007"></a></p>
<h5>30.3-9 AsSortedList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSortedList</code>( <var class="Arg">listorcoll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">AsSortedList</code> returns a dense and immutable list <var class="Arg">imm</var>. The argument must be a collection or list <var class="Arg">listorcoll</var> which may contain holes but whose elements lie in the same family (see <a href= | | |
