<p>This chapter describes boolean lists. A <em>boolean list</em> is a list that has no holes and contains only the boolean values <code class="keyw">true</code> and <code class="keyw">false</code> (see Chapter <a href="chap20_mj.html#X787B4AB77A2F5E14"><span class="RefLink">20</span></a>). In function names we call boolean lists <em>blists</em> for brevity.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBlist</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>A boolean list (<q>blist</q>) is a list that has no holes and contains only <code class="keyw">true</code> and <code class="keyw">false</code>. Boolean lists can be represented in an efficient compact form, see <a href="chap22_mj.html#X7C71B225841DFC0F"><span class="RefLink">22.5</span></a> for details.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBlist( [ true, true, false, false ] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBlist( [] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBlist( [false,,true] ); # has holes</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBlist( [1,1,0,0] ); # contains not only boolean values</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBlist( 17 ); # is not even a list</span>
false
</pre></div>
<p>Boolean lists are lists and all operations for lists are therefore applicable to boolean lists.</p>
<p>Boolean lists can be used in various ways, but maybe the most important application is their use for the description of <em>subsets</em> of finite sets. Suppose <span class="SimpleMath">\(set\)</span> is a finite set, represented as a list. Then a subset <span class="SimpleMath">\(sub\)</span> of <span class="SimpleMath">\(set\)</span> is represented by a boolean list <span class="SimpleMath">\(blist\)</span> of the same length as <span class="SimpleMath">\(set\)</span> such that <span class="SimpleMath">\(blist[i]\)</span> is <code class="keyw">true</code> if <span class="SimpleMath">\(set[i]\)</span> is in <span class="SimpleMath">\(sub\)</span>, and <code class="keyw">false</code> otherwise.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlistList</code>( <var class="Arg">list</var>, <var class="Arg">sub</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a new boolean list that describes the list <var class="Arg">sub</var> as a sublist of the dense list <var class="Arg">list</var>. That is <code class="func">BlistList</code> returns a boolean list <span class="SimpleMath">\(blist\)</span> of the same length as <var class="Arg">list</var> such that <span class="SimpleMath">\(blist[i]\)</span> is <code class="keyw">true</code> if <var class="Arg">list</var><span class="SimpleMath">\([i]\)</span> is in <var class="Arg">sub</var> and <code class="keyw">false</code> otherwise.</p>
<p><var class="Arg">list</var> need not be a proper set (see <a href="chap21_mj.html#X80ABC25582343910"><span class="RefLink">21.19</span></a>), even though in this case <code class="func">BlistList</code> is most efficient. In particular <var class="Arg">list</var> may contain duplicates. <var class="Arg">sub</var> need not be a proper sublist of <var class="Arg">list</var>, i.e., <var class="Arg">sub</var> may contain elements that are not in <var class="Arg">list</var>. Those elements of course have no influence on the result of <code class="func">BlistList</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ListBlist</code>( <var class="Arg">list</var>, <var class="Arg">blist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the sublist <span class="SimpleMath">\(sub\)</span> of the list <var class="Arg">list</var>, which must have no holes, represented by the boolean list <var class="Arg">blist</var>, which must have the same length as <var class="Arg">list</var>.</p>
<p><span class="SimpleMath">\(sub\)</span> contains the element <var class="Arg">list</var><span class="SimpleMath">\([i]\)</span> if <var class="Arg">blist</var><span class="SimpleMath">\([i]\)</span> is <code class="keyw">true</code> and does not contain the element if <var class="Arg">blist</var><span class="SimpleMath">\([i]\)</span> is <code class="keyw">false</code>. The order of the elements in <span class="SimpleMath">\(sub\)</span> is the same as the order of the corresponding elements in <var class="Arg">list</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SizeBlist</code>( <var class="Arg">blist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the number of entries of the boolean list <var class="Arg">blist</var> that are <code class="keyw">true</code>. This is the size of the subset represented by the boolean list <var class="Arg">blist</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubsetBlist</code>( <var class="Arg">blist1</var>, <var class="Arg">blist2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns <code class="keyw">true</code> if the boolean list <var class="Arg">blist2</var> is a subset of the boolean list <var class="Arg">blist1</var>, which must have equal length, and <code class="keyw">false</code> otherwise. <var class="Arg">blist2</var> is a subset of <var class="Arg">blist1</var> if <var class="Arg">blist1</var><span class="SimpleMath">\([i] =\)</span> <var class="Arg">blist1</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">or</code> <var class="Arg">blist2</var><span class="SimpleMath">\([i]\)</span> for all <span class="SimpleMath">\(i\)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UnionBlist</code>( <var class="Arg">blist1</var>, <var class="Arg">blist2</var>[, <var class="Arg">...</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">‣ UnionBlist</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form <code class="func">UnionBlist</code> returns the union of the boolean lists <var class="Arg">blist1</var>, <var class="Arg">blist2</var>, etc., which must have equal length. The <em>union</em> is a new boolean list that contains at position <span class="SimpleMath">\(i\)</span> the value <var class="Arg">blist1</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">or</code> <var class="Arg">blist2</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">or</code> <span class="SimpleMath">\(\ldots\)</span>.</p>
<p>The second form takes the union of all blists (which as for the first form must have equal length) in the list <var class="Arg">list</var>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IntersectionBlist</code>( <var class="Arg">blist1</var>, <var class="Arg">blist2</var>[, <var class="Arg">...</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">‣ IntersectionBlist</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form <code class="func">IntersectionBlist</code> returns the intersection of the boolean lists <var class="Arg">blist1</var>, <var class="Arg">blist2</var>, etc., which must have equal length. The <em>intersection</em> is a new blist that contains at position <span class="SimpleMath">\(i\)</span> the value <var class="Arg">blist1</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">and</code> <var class="Arg">blist2</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">and</code> <span class="SimpleMath">\(\ldots\)</span>.</p>
<p>In the second form <var class="Arg">list</var> must be a list of boolean lists <var class="Arg">blist1</var>, <var class="Arg">blist2</var>, etc., which must have equal length, and <code class="func">IntersectionBlist</code> returns the intersection of those boolean lists.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DifferenceBlist</code>( <var class="Arg">blist1</var>, <var class="Arg">blist2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the asymmetric set difference of the two boolean lists <var class="Arg">blist1</var> and <var class="Arg">blist2</var>, which must have equal length. The <em>asymmetric set difference</em> is a new boolean list that contains at position <span class="SimpleMath">\(i\)</span> the value <var class="Arg">blist1</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">and</code> <code class="keyw">not</code> <var class="Arg">blist2</var><span class="SimpleMath">\([i]\)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UniteBlist</code>( <var class="Arg">blist1</var>, <var class="Arg">blist2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">UniteBlist</code> unites the boolean list <var class="Arg">blist1</var> with the boolean list <var class="Arg">blist2</var>, which must have the same length. This is equivalent to assigning <var class="Arg">blist1</var><span class="SimpleMath">\([i] :=\)</span> <var class="Arg">blist1</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">or</code> <var class="Arg">blist2</var><span class="SimpleMath">\([i]\)</span> for all <span class="SimpleMath">\(i\)</span>.</p>
<p><code class="func">UniteBlist</code> returns nothing, it is only called to change <var class="Arg">blist1</var>.</p>
<p>The function <code class="func">UnionBlist</code> (<a href="chap22_mj.html#X7970BD3883C42D91"><span class="RefLink">22.3-1</span></a>) is the nondestructive counterpart to <code class="func">UniteBlist</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UniteBlistList</code>( <var class="Arg">list</var>, <var class="Arg">blist</var>, <var class="Arg">sub</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>works like <code class="code">UniteBlist(<var class="Arg">blist</var>,BlistList(<var class="Arg">list</var>,<var class="Arg">sub</var>))</code>. As no intermediate blist is created, the performance is better than the separate function calls.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IntersectBlist</code>( <var class="Arg">blist1</var>, <var class="Arg">blist2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>intersects the boolean list <var class="Arg">blist1</var> with the boolean list <var class="Arg">blist2</var>, which must have the same length. This is equivalent to assigning <var class="Arg">blist1</var><span class="SimpleMath">\([i]:=\)</span> <var class="Arg">blist1</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">and</code> <var class="Arg">blist2</var><span class="SimpleMath">\([i]\)</span> for all <span class="SimpleMath">\(i\)</span>.</p>
<p><code class="func">IntersectBlist</code> returns nothing, it is only called to change <var class="Arg">blist1</var>.</p>
<p>The function <code class="func">IntersectionBlist</code> (<a href="chap22_mj.html#X86E1F8DE85E1EE1E"><span class="RefLink">22.3-2</span></a>) is the nondestructive counterpart to <code class="func">IntersectBlist</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubtractBlist</code>( <var class="Arg">blist1</var>, <var class="Arg">blist2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>subtracts the boolean list <var class="Arg">blist2</var> from the boolean list <var class="Arg">blist1</var>, which must have equal length. This is equivalent to assigning <var class="Arg">blist1</var><span class="SimpleMath">\([i]:=\)</span> <var class="Arg">blist1</var><span class="SimpleMath">\([i]\)</span> <code class="keyw">and</code> <code class="keyw">not</code> <var class="Arg">blist2</var><span class="SimpleMath">\([i]\)</span> for all <span class="SimpleMath">\(i\)</span>.</p>
<p><code class="func">SubtractBlist</code> returns nothing, it is only called to change <var class="Arg">blist1</var>.</p>
<p>The function <code class="func">DifferenceBlist</code> (<a href="chap22_mj.html#X7D6FC2C58725708C"><span class="RefLink">22.3-3</span></a>) is the nondestructive counterpart to <code class="func">SubtractBlist</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MeetBlist</code>( <var class="Arg">blist1</var>, <var class="Arg">blist2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns <code class="keyw">true</code> if there is a position at which both <var class="Arg">blist1</var> and <var class="Arg">blist2</var> contain <code class="keyw">true</code>, and <code class="keyw">false</code> otherwise. It is equivalent to, but faster than <code class="code">SizeBlist(IntersectionBlist(blist1, blist2)) <> 0</code>. An error is thrown if the lists do not have the same length.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FlipBlist</code>( <var class="Arg">blist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Changes every entry in <var class="Arg">blist</var> that equals <code class="keyw">true</code> to <code class="keyw">false</code> and vice versa. If <code class="code">blist1</code> and <code class="code">blist2</code> are boolean lists with equal length and every value in <code class="code">blist2</code> is <code class="keyw">true</code>, then <code class="code">FlipBlist( blist1 )</code> is equivalent to <code class="code">SubtractBlist( blist2, blist1 ); blist1 := blist2;</code> but <code class="code">FlipBlist</code> is faster, and simpler to type.</p>
<p><code class="func">FlipBlist</code> returns nothing, it is only called to change <var class="Arg">blist</var> in-place.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetAllBlist</code>( <var class="Arg">blist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Changes every entry in <var class="Arg">blist</var> to <code class="keyw">true</code>. If <code class="code">blist1</code> and <code class="code">blist2</code> are boolean lists with equal length and every value in <code class="code">blist2</code> is <code class="keyw">true</code>, then <code class="code">SetAllBlist( blist1 )</code> is equivalent to <code class="code">UniteBlist( blist1, blist2 );</code> but is faster, and simpler to type.</p>
<p><code class="func">SetAllBlist</code> returns nothing, it is only called to change <var class="Arg">blist</var> in-place.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClearAllBlist</code>( <var class="Arg">blist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Changes every entry in <var class="Arg">blist</var> to <code class="keyw">false</code>. If <code class="code">blist1</code> and <code class="code">blist2</code> are boolean lists with equal length and every value in <code class="code">blist2</code> is <code class="keyw">false</code>, then <code class="code">ClearAllBlist( blist1 )</code> is equivalent to <code class="code">IntersectBlist( blist1, blist2 );</code> but is faster, and simpler to type.</p>
<p><code class="func">ClearAllBlist</code> returns nothing, it is only called to change <var class="Arg">blist</var> in-place.</p>
<h4>22.5 <span class="Heading">More about Boolean Lists</span></h4>
<p>We defined a boolean list as a list that has no holes and contains only <code class="keyw">true</code> and <code class="keyw">false</code>. There is a special internal representation for boolean lists that needs only 1 bit for each entry. This bit is set if the entry is <code class="keyw">true</code> and reset if the entry is <code class="keyw">false</code>. This representation is of course much more compact than the ordinary representation of lists, which needs 32 or 64 bits per entry.</p>
<p>Not every boolean list is represented in this compact representation. It would be too much work to test every time a list is changed, whether this list has become a boolean list. This section tells you under which circumstances a boolean list is represented in the compact representation, so you can write your functions in such a way that you make best use of the compact representation.</p>
<p>If a dense list containing only <code class="keyw">true</code> and <code class="keyw">false</code> is read, it is stored in the compact representation. Furthermore, the results of <code class="func">BlistList</code> (<a href="chap22_mj.html#X7C597B2D87CA2E6E"><span class="RefLink">22.2-1</span></a>), <code class="func">UnionBlist</code> (<a href="chap22_mj.html#X7970BD3883C42D91"><span class="RefLink">22.3-1</span></a>), <code class="func">IntersectionBlist</code> (<a href="chap22_mj.html#X86E1F8DE85E1EE1E"><span class="RefLink">22.3-2</span></a>) and <code class="func">DifferenceBlist</code> (<a href="chap22_mj.html#X7D6FC2C58725708C"><span class="RefLink">22.3-3</span></a>) are known to be boolean lists by construction, and thus are represented in the compact representation upon creation.</p>
<p>If an argument of <code class="func">IsSubsetBlist</code> (<a href="chap22_mj.html#X7BA42D03796ED4B3"><span class="RefLink">22.2-4</span></a>), <code class="func">ListBlist</code> (<a href="chap22_mj.html#X874BEF63785AB439"><span class="RefLink">22.2-2</span></a>), <code class="func">UnionBlist</code> (<a href="chap22_mj.html#X7970BD3883C42D91"><span class="RefLink">22.3-1</span></a>), <code class="func">IntersectionBlist</code> (<a href="chap22_mj.html#X86E1F8DE85E1EE1E"><span class="RefLink">22.3-2</span></a>), <code class="func">DifferenceBlist</code> (<a href="chap22_mj.html#X7D6FC2C58725708C"><span class="RefLink">22.3-3</span></a>), <code class="func">UniteBlist</code> (<a href="chap22_mj.html#X79815EB77CC8A389"><span class="RefLink">22.4-1</span></a>), <code class="func">IntersectBlist</code> (<a href="chap22_mj.html#X84EB70D37EB275DF"><span class="RefLink">22.4-3</span></a>) and <code class="func">SubtractBlist</code> (<a href="chap22_mj.html#X7AA138407D5A3BAC"><span class="RefLink">22.4-4</span></a>) is a list represented in the ordinary representation, it is tested to see if it is in fact a boolean list. If it is not, an error is signalled. If it is, the representation of the list is changed to the compact representation.</p>
<p>If you change a boolean list that is represented in the compact representation by assignment (see <a href="chap21_mj.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>) or <code class="func">Add</code> (<a href="chap21_mj.html#X795EC9D67E34DAB0"><span class="RefLink">21.4-2</span></a>) in such a way that the list remains a boolean list it will remain represented in the compact representation. Note that changing a list that is not represented in the compact representation, whether it is a boolean list or not, in such a way that the resulting list becomes a boolean list, will never change the representation of the list.</p>
<p>The first function is a filter that returns <code class="keyw">true</code> if the object <var class="Arg">obj</var> is a boolean list in compact representation and <code class="keyw">false</code> otherwise, see <a href="chap22_mj.html#X7C71B225841DFC0F"><span class="RefLink">22.5</span></a>.</p>
<p>The second function converts the object <var class="Arg">blist</var> to a boolean list in compact representation and returns <code class="keyw">true</code> if this is possible. Otherwise <var class="Arg">blist</var> is unchanged and <code class="keyw">false</code> is returned.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
