<html><head><title>[ref] 22 Boolean Lists</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP021.htm">Previous</a>] [<a href ="CHAP023.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>22 Boolean Lists</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP022.htm#SECT001">Boolean Lists Representing Subsets</a> <li> <A HREF="CHAP022.htm#SECT002">Set Operations via Boolean Lists</a> <li> <A HREF="CHAP022.htm#SECT003">Function that Modify Boolean Lists</a> <li> <A HREF="CHAP022.htm#SECT004">More about Boolean Lists</a> </ol><p> <p> This chapter describes boolean lists. A <strong>boolean list</strong> is a list that has no holes and contains only the boolean values <code>true</code> and <code>false</code> (see Chapter <a href="CHAP020.htm">Booleans</a>). In function names we call boolean lists <strong>blist</strong> for brevity. <p> <a name = ""></a> <li><code>IsBlist( </code><var>obj</var><code> ) C</code> <p> A boolean list (``blist'') is a list that has no holes and contains only <code>true</code> and <code>false</code>. If a list is known to be a boolean list by a test with <code>IsBlist</code> it is stored in a compact form. See <a href="CHAP022.htm#SECT004">More about Boolean Lists</a>. <p> <pre> gap> IsBlist( [ true, true, false, false ] ); true gap> IsBlist( [] ); true gap> IsBlist( [false,,true] ); # has holes false gap> IsBlist( [1,1,0,0] ); # contains not only boolean values false gap> IsBlist( 17 ); # is not even a list false </pre> <p> Boolean lists are lists and all operations for lists are therefore applicable to boolean lists. <p> Boolean lists can be used in various ways, but maybe the most important application is their use for the description of <strong>subsets</strong> of finite sets. Suppose <var>set</var> is a finite set, represented as a list. Then a subset <var>sub</var> of <var>set</var> is represented by a boolean list <var>blist</var> of the same length as <var>set</var> such that <code></code><var>blist</var><code>[</code><var>i</var><code>]</code> is <code>true</code> if <code></code><var>set</var><code>[</code><var>i</var><code>]</code> is in <var>sub</var> and <code>false</code> otherwise. <p> <p> <h2><a name="SECT001">22.1 Boolean Lists Representing Subsets</a></h2> <p><p> <a name = "SSEC001.1"></a> <li><code>BlistList( </code><var>list</var><code>, </code><var>sub</var><code> ) F</code> <p> returns a new boolean list that describes the list <var>sub</var> as a sublist of the dense list <var>list</var>. That is <code>BlistList</code> returns a boolean list <var>blist</var> of the same length as <var>list</var> such that <code></code><var>blist</var><code>[</code><var>i</var><code>]</code> is <code>true</code> if <code></code><var>list</var><code>[</code><var>i</var><code>]</code> is in <var>sub</var> and <code>false</code> otherwise. <p> <var>list</var> need not be a proper set (see <a href="CHAP021.htm#SECT019">Sorted Lists and Sets</a>), even though in this case <code>BlistList</code> is most efficient. In particular <var>list</var> may contain duplicates. <var>sub</var> need not be a proper sublist of <var>list</var>, i.e., <var>sub</var> may contain elements that are not in <var>list</var>. Those elements of course have no influence on the result of <code>BlistList</code>. <p> <pre> gap> BlistList( [1..10], [2,3,5,7] ); [ false, true, true, false, true, false, true, false, false, false ] gap> BlistList( [1,2,3,4,5,2,8,6,4,10], [4,8,9,16] ); [ false, false, false, true, false, false, true, false, true, false ] </pre> <p> See also <a href="CHAP022.htm#SSEC003.2">UniteBlistList</a>. <p> <a name = "SSEC001.2"></a> <li><code>ListBlist( </code><var>list</var><code>, </code><var>blist</var><code> ) O</code> <p> returns the sublist <var>sub</var> of the list <var>list</var>, which must have no holes, represented by the boolean list <var>blist</var>, which must have the same length as <var>list</var>. <var>sub</var> contains the element <code></code><var>list</var><code>[</code><var>i</var><code>]</code> if <code></code><var>blist</var><code>[</code><var>i</var><code>]</code> is <code>true</code> and does not contain the element if <code></code><var>blist</var><code>[</code><var>i</var><code>]</code> is <code>false</code>. The order of the elements in <var>sub</var> is the same as the order of the corresponding elements in <var>list</var>. <p> <pre> gap> ListBlist([1..8],[false,true,true,true,true,false,true,true]); [ 2, 3, 4, 5, 7, 8 ] gap> ListBlist( [1,2,3,4,5,2,8,6,4,10], > [false,false,false,true,false,false,true,false,true,false] ); [ 4, 8, 4 ] </pre> <p> <a name = "SSEC001.3"></a> <li><code>SizeBlist( </code><var>blist</var><code> ) F</code> <p> returns the number of entries of the boolean list <var>blist</var> that are <code>true</code>. This is the size of the subset represented by the boolean list <var>blist</var>. <p> <pre> gap> SizeBlist( [ false, true, false, true, false ] ); 2 </pre> <p> <a name = "SSEC001.4"></a> <li><code>IsSubsetBlist( </code><var>blist1</var><code>, </code><var>blist2</var><code> ) F</code> <p> returns <code>true</code> if the boolean list <var>blist2</var> is a subset of the boolean list <var>list1</var>, which must have equal length, and <code>false</code> otherwise. <var>blist2</var> is a subset of <var>blist1</var> if <code></code><var>blist1</var><code>[</code><var>i</var><code>] = </code><var>blist1</var><code>[</code><var>i</var><code>] or </code><var>blist2</var><code>[</code><var>i</var><code>]</code> for all <var>i</var>. <p> <pre> gap> blist1 := [ true, true, false, false ];; gap> blist2 := [ true, false, true, false ];; gap> IsSubsetBlist( blist1, blist2 ); false gap> blist2 := [ true, false, false, false ];; gap> IsSubsetBlist( blist1, blist2 ); true </pre> <p> <p> <h2><a name="SECT002">22.2 Set Operations via Boolean Lists</a></h2> <p><p> <a name = "SSEC002.1"></a> <li><code>UnionBlist( </code><var>blist1</var><code>, </code><var>blist2</var><code>[, ...] ) F</code> <li><code>UnionBlist( </code><var>list</var><code> ) F</code> <p> In the first form <code>UnionBlist</code> returns the union of the boolean lists <var>blist1</var>, <var>blist2</var>, etc., which must have equal length. The <strong>union</strong> is a new boolean list such that <code></code><var>union</var><code>[</code><var>i</var><code>] = </code><var>blist1</var><code>[</code><var>i</var><code>] or </code><var>blist2</var><code>[</code><var>i</var><code>] or ...</code>. <p> The second form takes the union of all blists (which as for the first form must have equal length) in the list <var>list</var>. <p> <a name = "SSEC002.2"></a> <li><code>IntersectionBlist( </code><var>blist1</var><code>, </code><var>blist2</var><code>[, ...] ) F</code> <li><code>IntersectionBlist( </code><var>list</var><code> ) F</code> <p> In the first form <code>IntersectionBlist</code> returns the intersection of the boolean lists <var>blist1</var>, <var>blist2</var>, etc., which must have equal length. The <strong>intersection</strong> is a new blist such that <code></code><var>inter</var><code>[</code><var>i</var><code>] = </code><var>blist1</var><code>[</code><var>i</var><code>] and </code><var>blist2</var><code>[</code><var>i</var><code>] and ...</code>. <p> In the second form <var>list</var> must be a list of boolean lists <var>blist1</var>, <var>blist2</var>, etc., which must have equal length, and <code>IntersectionBlist</code> returns the intersection of those boolean lists. <p> <a name = "SSEC002.3"></a> <li><code>DifferenceBlist( </code><var>blist1</var><code>, </code><var>blist2</var><code> ) F</code> <p> returns the asymmetric set difference (exclusive or) of the two boolean lists <var>blist1</var> and <var>blist2</var>, which must have equal length. The <strong>asymmetric set difference</strong> is a new boolean list such that <code></code><var>union</var><code>[</code><var>i</var><code>] = </code><var>blist1</var><code>[</code><var>i</var><code>] and not </code><var>blist2</var><code>[</code><var>i</var><code>]</code>. <p> <pre> gap> blist1 := [ true, true, false, false ];; gap> blist2 := [ true, false, true, false ];; gap> UnionBlist( blist1, blist2 ); [ true, true, true, false ] gap> IntersectionBlist( blist1, blist2 ); [ true, false, false, false ] gap> DifferenceBlist( blist1, blist2 ); [ false, true, false, false ] </pre> <p> <p> <h2><a name="SECT003">22.3 Function that Modify Boolean Lists</a></h2> <p><p> <a name = "SSEC003.1"></a> <li><code>UniteBlist( </code><var>blist1</var><code>, </code><var>blist2</var><code> ) F</code> <p> <code>UniteBlist</code> unites the boolean list <var>blist1</var> with the boolean list <var>blist2</var>, which must have the same length. This is equivalent to assigning <code></code><var>blist1</var><code>[</code><var>i</var><code>] := </code><var>blist1</var><code>[</code><var>i</var><code>] or </code><var>blist2</var><code>[</code><var>i</var><code>]</code> for all <var>i</var>. <code>UniteBlist</code> returns nothing, it is only called to change <var>blist1</var>. <p> <pre> gap> blist1 := [ true, true, false, false ];; gap> blist2 := [ true, false, true, false ];; gap> UniteBlist( blist1, blist2 ); gap> blist1; [ true, true, true, false ] </pre> <p> <a name = "SSEC003.2"></a> <li><code>UniteBlistList( </code><var>list</var><code>, </code><var>blist</var><code>, </code><var>sub</var><code> ) F</code> <p> works like <code>UniteBlist(</code><var>blist</var><code>,BlistList(</code><var>list</var><code>,</code><var>sub</var><code>))</code>. As no intermediate blist is created, the performance is better than the separate function calls. <p> The function <code>UnionBlist</code> (see <a href="CHAP022.htm#SSEC002.1">UnionBlist</a>) is the nondestructive counterpart to the procedure <code>UniteBlist</code>. <p> <a name = "SSEC003.3"></a> <li><code>IntersectBlist( </code><var>blist1</var><code>, </code><var>blist2</var><code> ) F</code> <p> intersects the boolean list <var>blist1</var> with the boolean list <var>blist2</var>, which must have the same length. This is equivalent to assigning <code></code><var>blist1</var><code>[</code><var>i</var><code>]:= </code><var>blist1</var><code>[</code><var>i</var><code>] and </code><var>blist2</var><code>[</code><var>i</var><code>]</code> for all <var>i</var>. <code>IntersectBlist</code> returns nothing, it is only called to change <var>blist1</var>. <p> <pre> gap> blist1 := [ true, true, false, false ];; gap> blist2 := [ true, false, true, false ];; gap> IntersectBlist( blist1, blist2 ); gap> blist1; [ true, false, false, false ] </pre> <p> The function <code>IntersectionBlist</code> (see <a href="CHAP022.htm#SSEC002.2">IntersectionBlist</a>) is the nondestructive counterpart to the procedure <code>IntersectBlist</code>. <p> <a name = "SSEC003.4"></a> <li><code>SubtractBlist( </code><var>blist1</var><code>, </code><var>blist2</var><code> ) F</code> <p> subtracts the boolean list <var>blist2</var> from the boolean list <var>blist1</var>, which must have equal length. This is equivalent to assigning <code></code><var>blist1</var><code>[</code><var>i</var><code>] := </code><var>blist1</var><code>[</code><var>i</var><code>] and not </code><var>blist2</var><code>[</code><var>i</var><code>]</code> for all <var>i</var>. <code>SubtractBlist</code> returns nothing, it is only called to change <var>blist1</var>. <p> <pre> gap> blist1 := [ true, true, false, false ];; gap> blist2 := [ true, false, true, false ];; gap> SubtractBlist( blist1, blist2 ); gap> blist1; [ false, true, false, false ] </pre> <p> The function <code>DifferenceBlist</code> (see <a href="CHAP022.htm#SSEC002.3">DifferenceBlist</a>) is the nondestructive counterpart to the procedure <code>SubtractBlist</code>. <p> <p> <h2><a name="SECT004">22.4 More about Boolean Lists</a></h2> <p><p> We defined a boolean list as a list that has no holes and contains only <code>true</code> and <code>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>true</code> and reset if the entry is <code>false</code>. This representation is of course much more compact than the ordinary representation of lists, which needs (at least) 32 bits per entry. <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> The results of <code>BlistList</code>, <code>UnionBlist</code>, <code>IntersectionBlist</code> and <code>DifferenceBlist</code> are known to be boolean lists by construction, and thus are represented in the compact representation upon creation. <p> If an argument of <code>IsBlist</code>, <code>IsSubsetBlist</code>, <code>ListBlist</code>, <code>UnionBlist</code>, <code>IntersectionBlist</code>, <code>DifferenceBlist</code>, <code>UniteBlist</code>, <code>IntersectBlist</code> and <code>SubtractBlist</code> 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, <code>IsBlist</code> returns <code>false</code> and the other functions signal an error. If it is, the representation of the list is changed to the compact representation. <p> If you change a boolean list that is represented in the compact representation by assignment (see <a href="CHAP021.htm#SECT004">List Assignment</a>) or <code>Add</code> (see <a href="CHAP021.htm#SSEC004.4">Add</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> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP021.htm">Previous</a>] [<a href ="CHAP023.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008 </font></body></html>
