/usr/share/gap/doc/ref/chap21.html is in gap-doc 4r6p5-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 | <?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 21: Lists</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="chap21" 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="chap20.html">[Previous Chapter]</a> <a href="chap22.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap21_mj.html">[MathJax on]</a></p>
<p><a id="X7B256AE5780F140A" name="X7B256AE5780F140A"></a></p>
<div class="ChapSects"><a href="chap21.html#X7B256AE5780F140A">21 <span class="Heading">Lists</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X86B28F5B781FFD31">21.1 <span class="Heading">List Categories</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7C4CC4EA8299701E">21.1-1 IsList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X870AA9D8798C93DD">21.1-2 IsDenseList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7C71596C82B6EF35">21.1-3 IsHomogeneousList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X80872FAF80EB5DF9">21.1-4 IsTable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X79581E0387F7F7A9">21.1-5 IsRectangularTable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7C84E16A85C99C8C">21.1-6 IsConstantTimeAccessList</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7B202D147A5C2884">21.2 <span class="Heading">Basic Operations for Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8297BBCD79642BE6">21.2-1 \[\]</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7921047F83F5FA28">21.3 <span class="Heading">List Elements</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X78791B8B838A8BA0">21.3-1 \{\}</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X8611EF768210625B">21.4 <span class="Heading">List Assignment</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X813FF1637F8D2B7F">21.4-1 \{\}\:\=</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X795EC9D67E34DAB0">21.4-2 Add</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7E98B11B79BA9167">21.4-3 Remove</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X79D7E96F80A2D7C0">21.4-4 CopyListEntries</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X79E31DB27C82D6E1">21.4-5 Append</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7963C8E17EFF86DB">21.5 <span class="Heading">IsBound and Unbind for Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X876EAD64820B2405">21.5-1 IsBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X78B72FDF7BD63C0B">21.5-2 Unbind</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7DD65BEA7EDB0CD7">21.6 <span class="Heading">Identical Lists</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7ED7C0738495556F">21.7 <span class="Heading">Duplication of Lists</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X808A207182B2F84F">21.8 <span class="Heading">Membership Test for Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7B914A287F88ED0A">21.8-1 \in</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X84D6FC7E7E39ED33">21.9 <span class="Heading">Enlarging Internally Represented Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X78BF67A5802E93AD">21.9-1 EmptyPlist</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X8016D50F85147A77">21.10 <span class="Heading">Comparisons of Lists</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X845EEAF083D43CCE">21.11 <span class="Heading">Arithmetic for Lists</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X84D642967B8546B7">21.12 <span class="Heading">Filters Controlling the Arithmetic Behaviour of Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X87ABCEE9809585A0">21.12-1 IsGeneralizedRowVector</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7FBCA5B58308C158">21.12-2 IsMultiplicativeGeneralizedRowVector</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7BAD12E67BFC90DE">21.12-3 IsListDefault</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8428E77B86722D52">21.12-4 NestingDepthA</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X84B383B97FD986CD">21.12-5 NestingDepthM</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7E6A1F66781BE923">21.13 <span class="Heading">Additive Arithmetic for Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X86A85ADC85C451DC">21.13-1 <span class="Heading">Zero for lists</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7B91CE4D814C2D08">21.13-2 <span class="Heading">AdditiveInverse for lists</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X842D123E7EE5E3DB">21.13-3 <span class="Heading">Addition of lists</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7C3DC8BE78DEECDE">21.13-4 <span class="Heading">Subtraction of lists</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X782ED7F27D8C7FC1">21.14 <span class="Heading">Multiplicative Arithmetic for Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X79A8A5627FD42FA5">21.14-1 <span class="Heading">One for lists</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X78C6C1E2849D303A">21.14-2 <span class="Heading">Inverse for lists</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X84FDB95179BFE4CD">21.14-3 <span class="Heading">Multiplication of lists</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X82EA2A5B786181C7">21.14-4 <span class="Heading">Division of lists</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7A0FD70C80B95C00">21.14-5 <span class="Heading">mod for lists</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X84BB2DFB8432A1A4">21.14-6 <span class="Heading">Left quotients of lists</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X8676EFE67972FD06">21.15 <span class="Heading">Mutability Status and List Arithmetic</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X80FDB1457FF582E7">21.15-1 ListWithIdenticalEntries</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X8196FD4779BCCA0C">21.16 <span class="Heading">Finding Positions in Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X79975EC6783B4293">21.16-1 Position</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7FA9648883AE1B88">21.16-2 Positions</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7B4B10AE81602D4E">21.16-3 PositionCanonical</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7D2B25B484591506">21.16-4 PositionNthOccurrence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7A122E848464E534">21.16-5 PositionSorted</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X78BFE9D78347C0DA">21.16-6 PositionSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7E6C763A82C6153B">21.16-7 PositionProperty</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7DA94D278304EC3D">21.16-8 PositionsProperty</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X86C9E5C3863B3C03">21.16-9 PositionBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X865EF45D87ED1384">21.16-10 PositionNot</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7F42E5AD87EC9D5A">21.16-11 PositionNonZero</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X87A8C62A867D6DA4">21.16-12 PositionSublist</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8132A2F5823F0CC0">21.16-13 PositionFirstComponent</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7865747A7CCF5812">21.17 <span class="Heading">Properties and Attributes for Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X83F8EC7C7BF27EFC">21.17-1 IsMatchingSublist</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7FA892828252BB3B">21.17-2 IsDuplicateFree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7BAA9B0E81D4A884">21.17-3 IsSortedList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X80CDAF45782E8DCB">21.17-4 IsSSortedList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X780769238600AFD1">21.17-5 Length</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7B55FB967CDEF468">21.17-6 ConstantTimeAccessList</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X83E558E37D1B44D4">21.18 <span class="Heading">Sorting Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7FE4975F8166884D">21.18-1 Sort</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X791F2B2C7E9B9A46">21.18-2 SortParallel</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X87287FCA81E2B06A">21.18-3 Sortex</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X800209E881E7CECB">21.18-4 SortingPerm</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X80ABC25582343910">21.19 <span class="Heading">Sorted Lists and Sets</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7B16AD597CB12305">21.19-1 \in</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7B4C0FEE7CDF6F2A">21.19-2 IsEqualSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X79B940567A849216">21.19-3 IsSubsetSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X832C23CC7FCD8892">21.19-4 AddSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7FCA282E789A4F4B">21.19-5 RemoveSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7B3469CD7EFC1A87">21.19-6 UniteSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8473AA657FEC3D4D">21.19-7 IntersectSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X80B427537EB07D09">21.19-8 SubtractSet</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7DF510F7848CBBFD">21.20 <span class="Heading">Operations for Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X840C55A77D1BB2E1">21.20-1 Concatenation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7CB0A6AF87C7FAF7">21.20-2 Compacted</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7ECE9056792F28BA">21.20-3 Collected</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8727F2928467C2F9">21.20-4 DuplicateFreeList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7F5D4DD87E4378AC">21.20-5 AsDuplicateFreeList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7FA272D984EF82ED">21.20-6 Flat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7C4FDB007C3F54A1">21.20-7 Reversed</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8057372F83374193">21.20-8 Shuffle</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7BA5EF2181DD78D7">21.20-9 IsLexicographicallyLess</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8075FBDE7B81B4C8">21.20-10 Apply</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7EF6E2BC81DBF6FB">21.20-11 Perform</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8763882A7D65F979">21.20-12 PermListList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X82CE0DE8828E4303">21.20-13 <span class="Heading">Maximum</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X82F133EC7F89665F">21.20-14 <span class="Heading">Minimum</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X842851EB7E0969F7">21.20-15 <span class="Heading">MaximumList and MinimumList</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7E1593B979BDF2CD">21.20-16 <span class="Heading">Cartesian</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7E76F5A782184823">21.20-17 <span class="Heading">IteratorOfCartesianProduct</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7B5A19098406347A">21.20-18 Permuted</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X86CB7DCE8510F977">21.20-19 List</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7C86D7F7795125F0">21.20-20 Filtered</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8179B13D80E935FC">21.20-21 Number</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X82801DFA84E11272">21.20-22 First</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7F06961278166671">21.20-23 ForAll</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7AF82E747A8BDA75">21.20-24 ForAny</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7E5C72F27B657948">21.20-25 Product</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7A04B71C84CFCC2D">21.20-26 Sum</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X834E4DF57F3A20F0">21.20-27 Iterated</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7D150C2881881139">21.20-28 ListN</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X805CA0B68029B47A">21.21 <span class="Heading">Advanced List Manipulations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X8258477D7F72171B">21.21-1 ListX</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7AC321B87A2DCAF5">21.21-2 SetX</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X82B1411E7FBE925F">21.21-3 SumX</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7FB318B47D8783DA">21.21-4 ProductX</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X79596BDE7CAF8491">21.22 <span class="Heading">Ranges</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X86DDC2FF7A50FBEE">21.22-1 IsRange</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7D22B2298167A58F">21.22-2 ConvertToRangeRep</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap21.html#X7EA3ACE27E43D174">21.23 <span class="Heading">Enumerators</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap21.html#X7BB462C17962647F">21.23-1 IsQuickPositionList</a></span>
</div></div>
</div>
<h3>21 <span class="Heading">Lists</span></h3>
<p>Lists are the most important way to treat objects together. A <em>list</em> arranges objects in a definite order. So each list implies a partial mapping from the integers to the elements of the list. I.e., there is a first element of a list, a second, a third, and so on. Lists can occur in mutable or immutable form, see <a href="chap12.html#X7F0C119682196D65"><span class="RefLink">12.6</span></a> for the concept of mutability, and <a href="chap21.html#X7ED7C0738495556F"><span class="RefLink">21.7</span></a> for the case of lists.</p>
<p>This chapter deals mainly with the aspect of lists in <strong class="pkg">GAP</strong> as <em>data structures</em>. Chapter <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a> tells more about the <em>collection</em> aspect of certain lists, and more about lists as <em>arithmetic objects</em> can be found in the chapters <a href="chap23.html#X82C7E6CF7BA03391"><span class="RefLink">23</span></a> and <a href="chap24.html#X812CCAB278643A59"><span class="RefLink">24</span></a>.</p>
<p>Lists are used to implement ranges (see <a href="chap21.html#X79596BDE7CAF8491"><span class="RefLink">21.22</span></a>), sets (see <a href="chap21.html#X80ABC25582343910"><span class="RefLink">21.19</span></a>), strings (see <a href="chap27.html#X7D28329B7EDB8F47"><span class="RefLink">27</span></a>), row vectors (see <a href="chap23.html#X82C7E6CF7BA03391"><span class="RefLink">23</span></a>), and matrices (see <a href="chap24.html#X812CCAB278643A59"><span class="RefLink">24</span></a>); Boolean lists (see <a href="chap22.html#X7AC531DD79B6938E"><span class="RefLink">22</span></a>) are a further special kind of lists.</p>
<p>Several operations for lists, such as <code class="func">Intersection</code> (<a href="chap30.html#X851069107CACF98E"><span class="RefLink">30.5-2</span></a>) and <code class="func">Random</code> (<a href="chap30.html#X7FF906E57D6936F8"><span class="RefLink">30.7-1</span></a>), will be described in Chapter <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a>, in particular see <a href="chap30.html#X7C3722DF8736FFDB"><span class="RefLink">30.3</span></a>.</p>
<p><a id="X86B28F5B781FFD31" name="X86B28F5B781FFD31"></a></p>
<h4>21.1 <span class="Heading">List Categories</span></h4>
<p>A list can be written by writing down the elements in order between square brackets <code class="code">[</code>, <code class="code">]</code>, and separating them with commas <code class="code">,</code>. An <em>empty list</em>, i.e., a list with no elements, is written as <code class="code">[]</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, 2, 3 ]; # a list with three elements</span>
[ 1, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">[ [], [ 1 ], [ 1, 2 ] ]; # a list may contain other lists</span>
[ [ ], [ 1 ], [ 1, 2 ] ]
</pre></div>
<p>Each list constructed this way is mutable (see <a href="chap12.html#X7F0C119682196D65"><span class="RefLink">12.6</span></a>).</p>
<p><a id="X7C4CC4EA8299701E" name="X7C4CC4EA8299701E"></a></p>
<h5>21.1-1 IsList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsList</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>tests whether <var class="Arg">obj</var> is a list.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsList( [ 1, 3, 5, 7 ] ); IsList( 1 );</span>
true
false
</pre></div>
<p><a id="X870AA9D8798C93DD" name="X870AA9D8798C93DD"></a></p>
<h5>21.1-2 IsDenseList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDenseList</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>A list is <em>dense</em> if it has no holes, i.e., contains an element at every position up to the length. It is absolutely legal to have lists with holes. They are created by leaving the entry between the commas empty. Holes at the end of a list are ignored. Lists with holes are sometimes convenient when the list represents a mapping from a finite, but not consecutive, subset of the positive integers.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDenseList( [ 1, 2, 3 ] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ , 4, 9,, 25,, 49,,,, 121 ];; IsDenseList( l );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">l[3];</span>
9
<span class="GAPprompt">gap></span> <span class="GAPinput">l[4];</span>
List Element: <list>[4] must have an assigned value
not in any function
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' after assigning a value to continue
<span class="GAPbrkprompt">brk></span> <span class="GAPinput">l[4] := 16;; # assigning a value</span>
<span class="GAPbrkprompt">brk></span> <span class="GAPinput">return; # to escape the break-loop</span>
16
<span class="GAPprompt">gap></span> <span class="GAPinput"></span>
</pre></div>
<p>Observe that requesting the value of <code class="code">l[4]</code>, which was not assigned, caused the entry of a <code class="keyw">break</code>-loop (see Section <a href="chap6.html#X8593B49F8705B486"><span class="RefLink">6.4</span></a>). After assigning a value and typing <code class="code">return;</code>, <strong class="pkg">GAP</strong> is finally able to comply with our request (by responding with <code class="code">16</code>).</p>
<p><a id="X7C71596C82B6EF35" name="X7C71596C82B6EF35"></a></p>
<h5>21.1-3 IsHomogeneousList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsHomogeneousList</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>returns <code class="keyw">true</code> if <var class="Arg">obj</var> is a list and it is homogeneous, and <code class="keyw">false</code> otherwise.</p>
<p>A <em>homogeneous</em> list is a dense list whose elements lie in the same family (see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>). The empty list is homogeneous but not a collection (see <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a>), a nonempty homogeneous list is also a collection.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsHomogeneousList( [ 1, 2, 3 ] ); IsHomogeneousList( [] );</span>
true
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsHomogeneousList( [ 1, false, () ] );</span>
false
</pre></div>
<p><a id="X80872FAF80EB5DF9" name="X80872FAF80EB5DF9"></a></p>
<h5>21.1-4 IsTable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsTable</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>A <em>table</em> is a nonempty list of homogeneous lists which lie in the same family. Typical examples of tables are matrices (see <a href="chap24.html#X812CCAB278643A59"><span class="RefLink">24</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTable( [ [ 1, 2 ], [ 3, 4 ] ] ); # in fact a matrix</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTable( [ [ 1 ], [ 2, 3 ] ] ); # not rectangular but a table</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTable( [ [ 1, 2 ], [ () , (1,2) ] ] ); # not homogeneous</span>
false
</pre></div>
<p><a id="X79581E0387F7F7A9" name="X79581E0387F7F7A9"></a></p>
<h5>21.1-5 IsRectangularTable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRectangularTable</code>( <var class="Arg">list</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>A list lies in <code class="code">IsRectangularTable</code> when it is nonempty and its elements are all homogeneous lists of the same family and the same length.</p>
<p><a id="X7C84E16A85C99C8C" name="X7C84E16A85C99C8C"></a></p>
<h5>21.1-6 IsConstantTimeAccessList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsConstantTimeAccessList</code>( <var class="Arg">list</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>This category indicates whether the access to each element of the list <var class="Arg">list</var> will take roughly the same time. This is implied for example by <code class="code">IsList and IsInternalRep</code>, so all strings, Boolean lists, ranges, and internally represented plain lists are in this category.</p>
<p>But also other enumerators (see <a href="chap21.html#X7EA3ACE27E43D174"><span class="RefLink">21.23</span></a>) can lie in this category if they guarantee constant time access to their elements.</p>
<p><a id="X7B202D147A5C2884" name="X7B202D147A5C2884"></a></p>
<h4>21.2 <span class="Heading">Basic Operations for Lists</span></h4>
<p>The basic operations for lists are element access (see <a href="chap21.html#X7921047F83F5FA28"><span class="RefLink">21.3</span></a>), assignment of elements to a list (see <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>), fetching the length of a list (see <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>)), the test for a hole at a given position, and unbinding an element at a given position (see <a href="chap21.html#X7963C8E17EFF86DB"><span class="RefLink">21.5</span></a>).</p>
<p>The term basic operation means that each other list operation can be formulated in terms of the basic operations. (But note that usually a more efficient method than this one is implemented.)</p>
<p>Any <strong class="pkg">GAP</strong> object <var class="Arg">list</var> in the category <code class="func">IsList</code> (<a href="chap21.html#X7C4CC4EA8299701E"><span class="RefLink">21.1-1</span></a>) is regarded as a list, and if methods for the basic list operations are installed for <var class="Arg">list</var> then <var class="Arg">list</var> can be used also for the other list operations.</p>
<p>For internally represented lists, kernel methods are provided for the basic list operations. For other lists, it is possible to install appropriate methods for these operations. This permits the implementation of lists that do not need to store all list elements (see also <a href="chap21.html#X7EA3ACE27E43D174"><span class="RefLink">21.23</span></a>); for example, the elements might be described by an algorithm, such as the elements list of a group. For this reduction of space requirements, however, a price in access time may have to be paid (see <code class="func">ConstantTimeAccessList</code> (<a href="chap21.html#X7B55FB967CDEF468"><span class="RefLink">21.17-6</span></a>)).</p>
<p><a id="X8297BBCD79642BE6" name="X8297BBCD79642BE6"></a></p>
<h5>21.2-1 \[\]</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \[\]</code>( <var class="Arg">list</var>, <var class="Arg">pos</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">‣ IsBound\[\]</code>( <var class="Arg">list</var>, <var class="Arg">pos</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">‣ \[\]\:\=</code>( <var class="Arg">list</var>, <var class="Arg">pos</var>, <var class="Arg">val</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">‣ Unbind\[\]</code>( <var class="Arg">list</var>, <var class="Arg">pos</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>These operations implement element access, test for element boundedness, list element assignment, and removal of the element at position <var class="Arg">pos</var>. In all cases, the index <var class="Arg">pos</var> must be a positive integer.</p>
<p>Note that the special characters <code class="code">[</code>, <code class="code">]</code>, <code class="code">:</code>, and <code class="code">=</code> must be escaped with a backslash <code class="code">\</code> (see <a href="chap4.html#X7E90E6607F4E4943"><span class="RefLink">4.3</span></a>); so <code class="func">\[\]</code> denotes the operation for element access in a list, whereas <code class="code">[]</code> denotes an empty list. (Maybe the variable names involving special characters look strange, but nevertheless they are quite suggestive.)</p>
<p><code class="code">\[\]( <var class="Arg">list</var>, <var class="Arg">pos</var> )</code> is equivalent to <code class="code"><var class="Arg">list</var>[ <var class="Arg">pos</var> ]</code>, which clearly will usually be preferred; the former is useful mainly if one wants to access the operation itself, for example if one wants to install a method for element access in a special kind of lists.</p>
<p>Similarly, <code class="func">IsBound\[\]</code> is used explicitly mainly in method installations. In other situations, one can simply call <code class="func">IsBound</code> (<a href="chap21.html#X876EAD64820B2405"><span class="RefLink">21.5-1</span></a>), which then delegates to <code class="func">IsBound\[\]</code> if the first argument is a list, and to <code class="func">IsBound\.</code> (<a href="chap29.html#X7821AC097821AC09"><span class="RefLink">29.7-3</span></a>) if the first argument is a record.</p>
<p>Analogous statements hold for <code class="func">\[\]\:\=</code> and <code class="func">Unbind\[\]</code>.</p>
<p><a id="X7921047F83F5FA28" name="X7921047F83F5FA28"></a></p>
<h4>21.3 <span class="Heading">List Elements</span></h4>
<p><code class="code"><var class="Arg">list</var>[ <var class="Arg">pos</var> ]</code></p>
<p>The above construct evaluates to the <var class="Arg">pos</var>-th element of the list <var class="Arg">list</var>, where <var class="Arg">pos</var> must be a positive integer. List indexing is done with origin 1, i.e., the first element of the list is the element at position 1.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ 2, 3, 5, 7, 11, 13 ];; l[1]; l[2]; l[6];</span>
2
3
13
</pre></div>
<p>If <var class="Arg">list</var> is not a list, or <var class="Arg">pos</var> does not evaluate to a positive integer, or <code class="code"><var class="Arg">list</var>[<var class="Arg">pos</var>]</code> is unbound an error is signalled.</p>
<p><code class="code"><var class="Arg">list</var>{ <var class="Arg">poss</var> }</code></p>
<p>The above construct evaluates to a new list <var class="Arg">new</var> whose first element is <code class="code"><var class="Arg">list</var>[<var class="Arg">poss</var>[1]]</code>, whose second element is <code class="code"><var class="Arg">list</var>[<var class="Arg">poss</var>[2]]</code>, and so on. <var class="Arg">poss</var> must be a dense list of positive integers. However, it does not need to be sorted and may contain duplicate elements. If for any <span class="SimpleMath">i</span>, <code class="code"><var class="Arg">list</var>[ <var class="Arg">poss</var>[</code><span class="SimpleMath">i</span><code class="code">] ]</code> is unbound, an error is signalled.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ 2, 3, 5, 7, 11, 13, 17, 19 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">l{[4..6]}; l{[1,7,1,8]};</span>
[ 7, 11, 13 ]
[ 2, 17, 2, 19 ]
</pre></div>
<p>The result is a <em>new</em> list, that is not identical to any other list. The elements of that list, however, are identical to the corresponding elements of the left operand (see <a href="chap21.html#X7DD65BEA7EDB0CD7"><span class="RefLink">21.6</span></a>).</p>
<p>It is possible to nest such <em>sublist extractions</em>, as can be seen in the example below.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := [ [1,2,3], [4,5,6], [7,8,9], [10,11,12] ];; m{[1,2,3]}{[3,2]};</span>
[ [ 3, 2 ], [ 6, 5 ], [ 9, 8 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l := m{[1,2,3]};; l{[3,2]};</span>
[ [ 7, 8, 9 ], [ 4, 5, 6 ] ]
</pre></div>
<p>Note the difference between the two examples. The latter extracts elements 1, 2, and 3 from <var class="Arg">m</var> and then extracts the elements 3 and 2 from <em>this list</em>. The former extracts elements 1, 2, and 3 from <var class="Arg">m</var> and then extracts the elements 3 and 2 from <em>each of those element lists</em>.</p>
<p>To be precise: With each selector <code class="code">[<var class="Arg">pos</var>]</code> or <code class="code">{<var class="Arg">poss</var>}</code> we associate a <em>level</em> that is defined as the number of selectors of the form <code class="code">{<var class="Arg">poss</var>}</code> to its left in the same expression. For example</p>
<div class="example"><pre>
l[pos1]{poss2}{poss3}[pos4]{poss5}[pos6]
level 0 0 1 2 2 3
</pre></div>
<p>Then a selector <code class="code"><var class="Arg">list</var>[<var class="Arg">pos</var>]</code> of level <var class="Arg">level</var> is computed as <code class="code">ListElement(<var class="Arg">list</var>,<var class="Arg">pos</var>,<var class="Arg">level</var>)</code>, where <code class="code">ListElement</code> is defined as follows. (Note that <code class="code">ListElement</code> is <em>not</em> a <strong class="pkg">GAP</strong> function.)</p>
<div class="example"><pre>
ListElement := function ( list, pos, level )
if level = 0 then
return list[pos];
else
return List( list, elm -> ListElement(elm,pos,level-1) );
fi;
end;
</pre></div>
<p>and a selector <code class="code"><var class="Arg">list</var>{<var class="Arg">poss</var>}</code> of level <var class="Arg">level</var> is computed as <code class="code">ListElements(<var class="Arg">list</var>,<var class="Arg">poss</var>,<var class="Arg">level</var>)</code>, where <code class="code">ListElements</code> is defined as follows. (Note that <code class="code">ListElements</code> is <em>not</em> a <strong class="pkg">GAP</strong> function.)</p>
<div class="example"><pre>
ListElements := function ( list, poss, level )
if level = 0 then
return list{poss};
else
return List( list, elm -> ListElements(elm,poss,level-1) );
fi;
end;
</pre></div>
<p><a id="X78791B8B838A8BA0" name="X78791B8B838A8BA0"></a></p>
<h5>21.3-1 \{\}</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \{\}</code>( <var class="Arg">list</var>, <var class="Arg">poss</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation implements <em>sublist access</em>. For any list, the default method is to loop over the entries in the list <var class="Arg">poss</var>, and to delegate to the element access operation. (For the somewhat strange variable name, cf. <a href="chap21.html#X7B202D147A5C2884"><span class="RefLink">21.2</span></a>.)</p>
<p><a id="X8611EF768210625B" name="X8611EF768210625B"></a></p>
<h4>21.4 <span class="Heading">List Assignment</span></h4>
<p><code class="code"><var class="Arg">list</var>[ <var class="Arg">pos</var> ] := <var class="Arg">object</var>;</code></p>
<p>The list element assignment assigns the object <var class="Arg">object</var>, which can be of any type, to the list entry at the position <var class="Arg">pos</var>, which must be a positive integer, in the mutable (see <a href="chap12.html#X7F0C119682196D65"><span class="RefLink">12.6</span></a>) list <var class="Arg">list</var>. That means that accessing the <var class="Arg">pos</var>-th element of the list <var class="Arg">list</var> will return <var class="Arg">object</var> after this assignment.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ 1, 2, 3 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">l[1] := 3;; l; # assign a new object</span>
[ 3, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l[2] := [ 4, 5, 6 ];; l; # <object> may be of any type</span>
[ 3, [ 4, 5, 6 ], 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l[ l[1] ] := 10;; l; # <index> may be an expression</span>
[ 3, [ 4, 5, 6 ], 10 ]
</pre></div>
<p>If the index <var class="Arg">pos</var> is larger than the length of the list <var class="Arg">list</var> (see <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>)), the list is automatically enlarged to make room for the new element. Note that it is possible to generate lists with holes that way.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l[4] := "another entry";; l; # <list> is enlarged</span>
[ 3, [ 4, 5, 6 ], 10, "another entry" ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l[ 10 ] := 1;; l; # now <list> has a hole</span>
[ 3, [ 4, 5, 6 ], 10, "another entry",,,,,, 1 ]
</pre></div>
<p>The function <code class="func">Add</code> (<a href="chap21.html#X795EC9D67E34DAB0"><span class="RefLink">21.4-2</span></a>) should be used if you want to add an element to the end of the list.</p>
<p>Note that assigning to a list changes the list, thus this list must be mutable (see <a href="chap12.html#X7F0C119682196D65"><span class="RefLink">12.6</span></a>). See <a href="chap21.html#X7DD65BEA7EDB0CD7"><span class="RefLink">21.6</span></a> for subtleties of changing lists.</p>
<p>If <var class="Arg">list</var> does not evaluate to a list, <var class="Arg">pos</var> does not evaluate to a positive integer or <var class="Arg">object</var> is a call to a function which does not return a value (for example <code class="code">Print</code>) an error is signalled.</p>
<p><code class="code"><var class="Arg">list</var>{ <var class="Arg">poss</var> } := <var class="Arg">objects</var>;</code></p>
<p>The sublist assignment assigns the object <code class="code"><var class="Arg">objects</var>[1]</code>, which can be of any type, to the list <var class="Arg">list</var> at the position <code class="code"><var class="Arg">poss</var>[1]</code>, the object <code class="code"><var class="Arg">objects</var>[2]</code> to <code class="code"><var class="Arg">list</var>[<var class="Arg">poss</var>[2]]</code>, and so on. <var class="Arg">poss</var> must be a dense list of positive integers, it need, however, not be sorted and may contain duplicate elements. <var class="Arg">objects</var> must be a dense list and must have the same length as <var class="Arg">poss</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ 2, 3, 5, 7, 11, 13, 17, 19 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">l{[1..4]} := [10..13];; l;</span>
[ 10, 11, 12, 13, 11, 13, 17, 19 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l{[1,7,1,10]} := [ 1, 2, 3, 4 ];; l;</span>
[ 3, 11, 12, 13, 11, 13, 2, 19,, 4 ]
</pre></div>
<p>The next example shows that it is possible to nest such sublist assignments.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := [ [1,2,3], [4,5,6], [7,8,9], [10,11,12] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">m{[1,2,3]}{[3,2]} := [ [11,12], [13,14], [15,16] ];; m;</span>
[ [ 1, 12, 11 ], [ 4, 14, 13 ], [ 7, 16, 15 ], [ 10, 11, 12 ] ]
</pre></div>
<p>The exact behaviour is defined in the same way as for list extractions (see <a href="chap21.html#X7921047F83F5FA28"><span class="RefLink">21.3</span></a>). Namely, with each selector <code class="code">[<var class="Arg">pos</var>]</code> or <code class="code">{<var class="Arg">poss</var>}</code> we associate a <em>level</em> that is defined as the number of selectors of the form <code class="code">{<var class="Arg">poss</var>}</code> to its left in the same expression. For example</p>
<div class="example"><pre>
l[pos1]{poss2}{poss3}[pos4]{poss5}[pos6]
level 0 0 1 1 1 2
</pre></div>
<p>Then a list assignment <code class="code"><var class="Arg">list</var>[<var class="Arg">pos</var>] := <var class="Arg">vals</var>;</code> of level <var class="Arg">level</var> is computed as <code class="code">ListAssignment( <var class="Arg">list</var>, <var class="Arg">pos</var>, <var class="Arg">vals</var>, <var class="Arg">level</var> )</code>, where <code class="code">ListAssignment</code> is defined as follows. (Note that <code class="code">ListAssignment</code> is <em>not</em> a <strong class="pkg">GAP</strong> function.)</p>
<div class="example"><pre>
ListAssignment := function ( list, pos, vals, level )
local i;
if level = 0 then
list[pos] := vals;
else
for i in [1..Length(list)] do
ListAssignment( list[i], pos, vals[i], level-1 );
od;
fi;
end;
</pre></div>
<p>and a list assignment <code class="code"><var class="Arg">list</var>{<var class="Arg">poss</var>} := <var class="Arg">vals</var></code> of level <var class="Arg">level</var> is computed as <code class="code">ListAssignments( <var class="Arg">list</var>, <var class="Arg">poss</var>, <var class="Arg">vals</var>, <var class="Arg">level</var> )</code>, where <code class="code">ListAssignments</code> is defined as follows. (Note that <code class="code">ListAssignments</code> is <em>not</em> a <strong class="pkg">GAP</strong> function.)</p>
<div class="example"><pre>
ListAssignments := function ( list, poss, vals, level )
local i;
if level = 0 then
list{poss} := vals;
else
for i in [1..Length(list)] do
ListAssignments( list[i], poss, vals[i], level-1 );
od;
fi;
end;
</pre></div>
<p><a id="X813FF1637F8D2B7F" name="X813FF1637F8D2B7F"></a></p>
<h5>21.4-1 \{\}\:\=</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \{\}\:\=</code>( <var class="Arg">list</var>, <var class="Arg">poss</var>, <var class="Arg">val</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation implements sublist assignment. For any list, the default method is to loop over the entries in the list <var class="Arg">poss</var>, and to delegate to the element assignment operation. (For the somewhat strange variable name, cf. <a href="chap21.html#X7B202D147A5C2884"><span class="RefLink">21.2</span></a>.)</p>
<p><a id="X795EC9D67E34DAB0" name="X795EC9D67E34DAB0"></a></p>
<h5>21.4-2 Add</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Add</code>( <var class="Arg">list</var>, <var class="Arg">obj</var>[, <var class="Arg">pos</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>adds the element <var class="Arg">obj</var> to the mutable list <var class="Arg">list</var>. The two argument version adds <var class="Arg">obj</var> at the end of <var class="Arg">list</var>, i.e., it is equivalent to the assignment <code class="code"><var class="Arg">list</var>[ Length(<var class="Arg">list</var>) + 1 ] := <var class="Arg">obj</var></code>, see <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>.</p>
<p>The three argument version adds <var class="Arg">obj</var> in position <var class="Arg">pos</var>, moving all later elements of the list (if any) up by one position. Any holes at or after position <var class="Arg">pos</var> are also moved up by one position, and new holes are created before <var class="Arg">pos</var> if they are needed.</p>
<p>Nothing is returned by <code class="func">Add</code>, the function is only called for its side effect.</p>
<p><a id="X7E98B11B79BA9167" name="X7E98B11B79BA9167"></a></p>
<h5>21.4-3 Remove</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Remove</code>( <var class="Arg">list</var>[, <var class="Arg">pos</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>removes an element from <var class="Arg">list</var>. The one argument form removes the last element. The two argument form removes the element in position <var class="Arg">pos</var>, moving all subsequent elements down one position. Any holes after position <var class="Arg">pos</var> are also moved down by one position.</p>
<p>The one argument form always returns the removed element. In this case <var class="Arg">list</var> must be non-empty.</p>
<p>The two argument form returns the old value of <var class="Arg">list</var>[<var class="Arg">pos</var>] if it was bound, and nothing if it was not. Note that accessing or assigning the return value of this form of the <code class="func">Remove</code> operation is only safe when you <em>know</em> that there will be a value, otherwise it will cause an error.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ 2, 3, 5 ];; Add( l, 7 ); l;</span>
[ 2, 3, 5, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Add(l,4,2); l;</span>
[ 2, 4, 3, 5, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Remove(l,2); l;</span>
4
[ 2, 3, 5, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Remove(l); l;</span>
7
[ 2, 3, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Remove(l,5); l;</span>
[ 2, 3, 5 ]
</pre></div>
<p><a id="X79D7E96F80A2D7C0" name="X79D7E96F80A2D7C0"></a></p>
<h5>21.4-4 CopyListEntries</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CopyListEntries</code>( <var class="Arg">fromlst</var>, <var class="Arg">fromind</var>, <var class="Arg">fromstep</var>, <var class="Arg">tolst</var>, <var class="Arg">toind</var>, <var class="Arg">tostep</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function copies <var class="Arg">n</var> elements from <var class="Arg">fromlst</var>, starting at position <var class="Arg">fromind</var> and incrementing the position by <var class="Arg">fromstep</var> each time, into <var class="Arg">tolst</var> starting at position <var class="Arg">toind</var> and incrementing the position by <var class="Arg">tostep</var> each time. <var class="Arg">fromlst</var> and <var class="Arg">tolst</var> must be plain lists. <var class="Arg">fromstep</var> and/or <var class="Arg">tostep</var> can be negative. Unbound positions of <var class="Arg">fromlst</var> are simply copied to <var class="Arg">tolst</var>.</p>
<p><code class="func">CopyListEntries</code> is used in methods for the operations <code class="func">Add</code> (<a href="chap21.html#X795EC9D67E34DAB0"><span class="RefLink">21.4-2</span></a>) and <code class="func">Remove</code> (<a href="chap21.html#X7E98B11B79BA9167"><span class="RefLink">21.4-3</span></a>).</p>
<p><a id="X79E31DB27C82D6E1" name="X79E31DB27C82D6E1"></a></p>
<h5>21.4-5 Append</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Append</code>( <var class="Arg">list1</var>, <var class="Arg">list2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>adds the elements of the list <var class="Arg">list2</var> to the end of the mutable list <var class="Arg">list1</var>, see <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>. <var class="Arg">list2</var> may contain holes, in which case the corresponding entries in <var class="Arg">list1</var> will be left unbound. <code class="func">Append</code> returns nothing, it is only called for its side effect.</p>
<p>Note that <code class="func">Append</code> changes its first argument, while <code class="func">Concatenation</code> (<a href="chap21.html#X840C55A77D1BB2E1"><span class="RefLink">21.20-1</span></a>) creates a new list and leaves its arguments unchanged.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ 2, 3, 5 ];; Append( l, [ 7, 11, 13 ] ); l;</span>
[ 2, 3, 5, 7, 11, 13 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Append( l, [ 17,, 23 ] ); l;</span>
[ 2, 3, 5, 7, 11, 13, 17,, 23 ]
</pre></div>
<p><a id="X7963C8E17EFF86DB" name="X7963C8E17EFF86DB"></a></p>
<h4>21.5 <span class="Heading">IsBound and Unbind for Lists</span></h4>
<p><a id="X876EAD64820B2405" name="X876EAD64820B2405"></a></p>
<h5>21.5-1 IsBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBound</code>( <var class="Arg">list</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">IsBound</code> returns <code class="keyw">true</code> if the list <var class="Arg">list</var> has a element at the position <var class="Arg">n</var>, and <code class="keyw">false</code> otherwise. <var class="Arg">list</var> must evaluate to a list, otherwise an error is signalled.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ , 2, 3, , 5, , 7, , , , 11 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBound( l[7] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBound( l[4] );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBound( l[101] );</span>
false
</pre></div>
<p><a id="X78B72FDF7BD63C0B" name="X78B72FDF7BD63C0B"></a></p>
<h5>21.5-2 Unbind</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Unbind</code>( <var class="Arg">list</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">Unbind</code> deletes the element at the position <var class="Arg">n</var> in the mutable list <var class="Arg">list</var>. That is, after execution of <code class="func">Unbind</code>, <var class="Arg">list</var> no longer has an assigned value at the position <var class="Arg">n</var>. Thus <code class="func">Unbind</code> can be used to produce holes in a list. Note that it is not an error to unbind a nonexisting list element. <var class="Arg">list</var> must evaluate to a list, otherwise an error is signalled.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [ , 2, 3, 5, , 7, , , , 11 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Unbind( l[3] ); l;</span>
[ , 2,, 5,, 7,,,, 11 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Unbind( l[4] ); l;</span>
[ , 2,,,, 7,,,, 11 ]
</pre></div>
<p>Note that <code class="func">IsBound</code> (<a href="chap21.html#X876EAD64820B2405"><span class="RefLink">21.5-1</span></a>) and <code class="func">Unbind</code> are special in that they do not evaluate their argument, otherwise <code class="func">IsBound</code> (<a href="chap21.html#X876EAD64820B2405"><span class="RefLink">21.5-1</span></a>) would always signal an error when it is supposed to return <code class="keyw">false</code> and there would be no way to tell <code class="func">Unbind</code> which component to remove.</p>
<p><a id="X7DD65BEA7EDB0CD7" name="X7DD65BEA7EDB0CD7"></a></p>
<h4>21.6 <span class="Heading">Identical Lists</span></h4>
<p>With the list assignment (see <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>) it is possible to change a mutable list. This section describes the semantic consequences of this fact. (See also <a href="chap12.html#X84545F3985C60F5B"><span class="RefLink">12.5</span></a>.)</p>
<p>First we define what it means when we say that "an object is changed". You may think that in the following example the second assignment changes the integer.</p>
<div class="example"><pre>
i := 3;
i := i + 1;
</pre></div>
<p>But in this example it is not the <em>integer</em> <code class="code">3</code> which is changed, by adding one to it. Instead the <em>variable</em> <code class="code">i</code> is changed by assigning the value of <code class="code">i+1</code>, which happens to be <code class="code">4</code>, to <code class="code">i</code>. The same thing happens in the example below.</p>
<div class="example"><pre>
l := [ 1, 2 ];
l := [ 1, 2, 3 ];
</pre></div>
<p>The second assignment does not change the first list, instead it assigns a new list to the variable <code class="code">l</code>. On the other hand, in the following example the list <em>is</em> changed by the second assignment.</p>
<div class="example"><pre>
l := [ 1, 2 ];
l[3] := 3;
</pre></div>
<p>To understand the difference, think of a variable as a name for an object. The important point is that a list can have several names at the same time. An assignment <code class="code"><var class="Arg">var</var>:= <var class="Arg">list</var>;</code> means in this interpretation that <var class="Arg">var</var> is a name for the object <var class="Arg">list</var>. At the end of the following example <code class="code">l2</code> still has the value <code class="code">[ 1, 2 ]</code> as this list has not been changed and nothing else has been assigned to it.</p>
<div class="example"><pre>
l1 := [ 1, 2 ];
l2 := l1;
l1 := [ 1, 2, 3 ];
</pre></div>
<p>But after the following example the list for which <code class="code">l2</code> is a name has been changed and thus the value of <code class="code">l2</code> is now <code class="code">[ 1, 2, 3 ]</code>.</p>
<div class="example"><pre>
l1 := [ 1, 2 ];
l2 := l1;
l1[3] := 3;
</pre></div>
<p>We say that two lists are <em>identical</em> if changing one of them by a list assignment also changes the other one. This is slightly incorrect, because if <em>two</em> lists are identical, there are actually only two names for <em>one</em> list. However, the correct usage would be very awkward and would only add to the confusion. Note that two identical lists must be equal, because there is only one list with two different names. Thus identity is an equivalence relation that is a refinement of equality. Identity of objects can be detected using <code class="func">IsIdenticalObj</code> (<a href="chap12.html#X7961183378DFB902"><span class="RefLink">12.5-1</span></a>).</p>
<p>Let us now consider under which circumstances two lists are identical.</p>
<p>If you enter a list literal then the list denoted by this literal is a new list that is not identical to any other list. Thus in the following example <code class="code">l1</code> and <code class="code">l2</code> are not identical, though they are equal of course.</p>
<div class="example"><pre>
l1 := [ 1, 2 ];
l2 := [ 1, 2 ];
</pre></div>
<p>Also in the following example, no lists in the list <code class="code">l</code> are identical.</p>
<div class="example"><pre>
l := [];
for i in [1..10] do l[i] := [ 1, 2 ]; od;
</pre></div>
<p>If you assign a list to a variable no new list is created. Thus the list value of the variable on the left hand side and the list on the right hand side of the assignment are identical. So in the following example <code class="code">l1</code> and <code class="code">l2</code> are identical lists.</p>
<div class="example"><pre>
l1 := [ 1, 2 ];
l2 := l1;
</pre></div>
<p>If you pass a list as an argument, the old list and the argument of the function are identical. Also if you return a list from a function, the old list and the value of the function call are identical. So in the following example <code class="code">l1</code> and <code class="code">l2</code> are identical lists:</p>
<div class="example"><pre>
l1 := [ 1, 2 ];
f := function ( l ) return l; end;
l2 := f( l1 );
</pre></div>
<p>If you change a list it keeps its identity. Thus if two lists are identical and you change one of them, you also change the other, and they are still identical afterwards. On the other hand, two lists that are not identical will never become identical if you change one of them. So in the following example both <code class="code">l1</code> and <code class="code">l2</code> are changed, and are still identical.</p>
<div class="example"><pre>
l1 := [ 1, 2 ];
l2 := l1;
l1[1] := 2;
</pre></div>
<p><a id="X7ED7C0738495556F" name="X7ED7C0738495556F"></a></p>
<h4>21.7 <span class="Heading">Duplication of Lists</span></h4>
<p>Here we describe the meaning of <code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>) and <code class="func">StructuralCopy</code> (<a href="chap12.html#X7C1E70587EBDD2CB"><span class="RefLink">12.7-2</span></a>) for lists. For the general definition of these functions, see <a href="chap12.html#X786B942B82D684BD"><span class="RefLink">12.7</span></a>.</p>
<p>The subobjects (see <code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>)) of a list are exactly its elements.</p>
<p>This means that for any list <var class="Arg">list</var>, <code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>) returns a mutable <em>new</em> list <var class="Arg">new</var> that is <em>not identical</em> to any other list (see <a href="chap21.html#X7DD65BEA7EDB0CD7"><span class="RefLink">21.6</span></a>), and whose elements are identical to the elements of <var class="Arg">list</var>.</p>
<p>Analogously, for a <em>mutable</em> list <var class="Arg">list</var>, <code class="func">StructuralCopy</code> (<a href="chap12.html#X7C1E70587EBDD2CB"><span class="RefLink">12.7-2</span></a>) returns a mutable <em>new</em> list <var class="Arg">scp</var> that is <em>not identical</em> to any other list, and whose elements are structural copies (defined recursively) of the elements of <var class="Arg">list</var>; an element of <var class="Arg">scp</var> is mutable (and then a <em>new</em> list) if and only if the corresponding element of <var class="Arg">list</var> is mutable.</p>
<p>In both cases, modifying the copy <var class="Arg">new</var> resp. <var class="Arg">scp</var> by assignments (see <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>) does not modify the original object <var class="Arg">list</var>.</p>
<p><code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>) basically executes the following code for lists.</p>
<div class="example"><pre>
new := [];
for i in [ 1 .. Length( list ) ] do
if IsBound( list[i] ) then
new[i] := list[i];
fi;
od;
</pre></div>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">list1 := [ [ 1, 2 ], [ 3, 4 ] ];; list2 := ShallowCopy( list1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdenticalObj( list1, list2 );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdenticalObj( list1[1], list2[1] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">list2[1] := 0;; list1; list2;</span>
[ [ 1, 2 ], [ 3, 4 ] ]
[ 0, [ 3, 4 ] ]
</pre></div>
<p><code class="func">StructuralCopy</code> (<a href="chap12.html#X7C1E70587EBDD2CB"><span class="RefLink">12.7-2</span></a>) basically executes the following code for lists.</p>
<div class="example"><pre>
new := [];
for i in [ 1 .. Length( list ) ] do
if IsBound( list[i] ) then
new[i] := StructuralCopy( list[i] );
fi;
od;
</pre></div>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">list1 := [ [ 1, 2 ], [ 3, 4 ] ];; list2 := StructuralCopy( list1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdenticalObj( list1, list2 );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdenticalObj( list1[1], list2[1] );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">list2[1][1] := 0;; list1; list2;</span>
[ [ 1, 2 ], [ 3, 4 ] ]
[ [ 0, 2 ], [ 3, 4 ] ]
</pre></div>
<p>The above code is not entirely correct. If the object <var class="Arg">list</var> contains a mutable object twice this object is not copied twice, as would happen with the above definition, but only once. This means that the copy <var class="Arg">new</var> and the object <var class="Arg">list</var> have exactly the same structure when viewed as a general graph.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">sub := [ 1, 2 ];; list1 := [ sub, sub ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">list2 := StructuralCopy( list1 );</span>
[ [ 1, 2 ], [ 1, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">list2[1][1] := 0;; list2;</span>
[ [ 0, 2 ], [ 0, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">list1;</span>
[ [ 1, 2 ], [ 1, 2 ] ]
</pre></div>
<p><a id="X808A207182B2F84F" name="X808A207182B2F84F"></a></p>
<h4>21.8 <span class="Heading">Membership Test for Lists</span></h4>
<p><a id="X7B914A287F88ED0A" name="X7B914A287F88ED0A"></a></p>
<h5>21.8-1 \in</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \in</code>( <var class="Arg">obj</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This function call or the infix variant <var class="Arg">obj</var> <code class="keyw">in</code> <var class="Arg">list</var> tests whether there is a positive integer <span class="SimpleMath">i</span> such that <var class="Arg">list</var><span class="SimpleMath">[i] =</span> <var class="Arg">obj</var> holds.</p>
<p>If the list <var class="Arg">list</var> knows that it is strictly sorted (see <code class="func">IsSSortedList</code> (<a href="chap21.html#X80CDAF45782E8DCB"><span class="RefLink">21.17-4</span></a>)), the membership test is much quicker, because a binary search can be used instead of the linear search used for arbitrary lists, see <code class="func">\in</code> (<a href="chap21.html#X7B16AD597CB12305"><span class="RefLink">21.19-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">1 in [ 2, 2, 1, 3 ]; 1 in [ 4, -1, 0, 3 ];</span>
true
false
<span class="GAPprompt">gap></span> <span class="GAPinput">s := SSortedList( [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">17 in s; # uses binary search and only 4 comparisons</span>
false
</pre></div>
<p>For finding the position of an element in a list, see <a href="chap21.html#X8196FD4779BCCA0C"><span class="RefLink">21.16</span></a>.</p>
<p><a id="X84D6FC7E7E39ED33" name="X84D6FC7E7E39ED33"></a></p>
<h4>21.9 <span class="Heading">Enlarging Internally Represented Lists</span></h4>
<p>Section <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a> told you (among other things) that it is possible to assign beyond the logical end of a mutable list, automatically enlarging the list. This section tells you how this is done for internally represented lists.</p>
<p>It would be extremely wasteful to make all lists large enough so that there is room for all assignments, because some lists may have more than 100000 elements, while most lists have less than 10 elements.</p>
<p>On the other hand suppose every assignment beyond the end of a list would be done by allocating new space for the list and copying all entries to the new space. Then creating a list of 1000 elements by assigning them in order, would take half a million copy operations and also create a lot of garbage that the garbage collector would have to reclaim.</p>
<p>So the following strategy is used. If a list is created it is created with exactly the correct size. If a list is enlarged, because of an assignment beyond the end of the list, it is enlarged by at least <code class="code"><var class="Arg">length</var>/8 + 4</code> entries. Therefore the next assignments beyond the end of the list do not need to enlarge the list. For example creating a list of 1000 elements by assigning them in order, would now take only 32 enlargements.</p>
<p>The result of this is of course that the <em>physical length</em> of a list may be larger than the <em>logical length</em>, which is usually called simply the length of the list. Aside from the implications for the performance you need not be aware of the physical length. In fact all you can ever observe, for example by calling <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>), is the logical length.</p>
<p>Suppose that <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>) would have to take the physical length and then test how many entries at the end of a list are unassigned, to compute the logical length of the list. That would take too much time. In order to make <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>), and other functions that need to know the logical length, more efficient, the length of a list is stored along with the list.</p>
<p>For fine tuning code dealing with plain lists we provide the following two functions.</p>
<p><a id="X78BF67A5802E93AD" name="X78BF67A5802E93AD"></a></p>
<h5>21.9-1 EmptyPlist</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EmptyPlist</code>( <var class="Arg">len</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a plain list</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShrinkAllocationPlist</code>( <var class="Arg">l</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: nothing</p>
<p>The function <code class="func">EmptyPlist</code> returns an empty plain list which has enough memory allocated for <var class="Arg">len</var> entries. This can be useful for creating and filling a plain list with a known number of entries.</p>
<p>The function <code class="func">ShrinkAllocationPlist</code> gives back to <strong class="pkg">GAP</strong>'s memory manager the physical memory which is allocated for the plain list <var class="Arg">l</var> but not needed by the current number of entries.</p>
<p>Note that there are similar functions <code class="func">EmptyString</code> (<a href="chap27.html#X836078DC829A8221"><span class="RefLink">27.3-4</span></a>) and <code class="func">ShrinkAllocationString</code> (<a href="chap27.html#X836078DC829A8221"><span class="RefLink">27.3-4</span></a>) for strings instead of plain lists.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:=[]; for i in [1..160] do Add(l, i^2); od; </span>
[ ]
<span class="GAPprompt">gap></span> <span class="GAPinput">m:=EmptyPlist(160); for i in [1..160] do Add(m, i^2); od;</span>
[ ]
<span class="GAPprompt">gap></span> <span class="GAPinput"># now l uses about 25% more memory than the equal list m</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ShrinkAllocationPlist(l);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"># now l and m use the same amount of memory</span>
</pre></div>
<p><a id="X8016D50F85147A77" name="X8016D50F85147A77"></a></p>
<h4>21.10 <span class="Heading">Comparisons of Lists</span></h4>
<p><code class="code"><var class="Arg">list1</var> = <var class="Arg">list2</var></code></p>
<p><code class="code"><var class="Arg">list1</var> <> <var class="Arg">list2</var></code></p>
<p>Two lists <var class="Arg">list1</var> and <var class="Arg">list2</var> are equal if and only if for every index <span class="SimpleMath">i</span>, either both entries <var class="Arg">list1</var><span class="SimpleMath">[i]</span> and <var class="Arg">list2</var><span class="SimpleMath">[i]</span> are unbound, or both are bound and are equal, i.e., <var class="Arg">list1</var><span class="SimpleMath">[i] =</span> <var class="Arg">list2</var><span class="SimpleMath">[i]</span> is <code class="keyw">true</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, 2, 3 ] = [ 1, 2, 3 ];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">[ , 2, 3 ] = [ 1, 2, ];</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, 2, 3 ] = [ 3, 2, 1 ];</span>
false
</pre></div>
<p>This definition will cause problems with lists which are their own entries. Comparing two such lists for equality may lead to an infinite recursion in the kernel if the list comparison has to compare the list entries which are in fact the lists themselves, and then <strong class="pkg">GAP</strong> crashes.</p>
<p><code class="code"><var class="Arg">list1</var> < <var class="Arg">list2</var></code></p>
<p><code class="code"><var class="Arg">list1</var> <= <var class="Arg">list2</var></code></p>
<p>Lists are ordered <em>lexicographically</em>. Unbound entries are smaller than any bound entry. That implies the following behaviour. Let <span class="SimpleMath">i</span> be the smallest positive integer <span class="SimpleMath">i</span> such that <var class="Arg">list1</var> and <var class="Arg">list2</var> at position <span class="SimpleMath">i</span> differ, i.e., either exactly one of <var class="Arg">list1</var><span class="SimpleMath">[i]</span>, <var class="Arg">list2</var><span class="SimpleMath">[i]</span> is bound or both entries are bound and differ. Then <var class="Arg">list1</var> is less than <var class="Arg">list2</var> if either <var class="Arg">list1</var><span class="SimpleMath">[i]</span> is unbound (and <var class="Arg">list2</var><span class="SimpleMath">[i]</span> is not) or both are bound and <var class="Arg">list1</var><span class="SimpleMath">[i]</span> < <var class="Arg">list2</var><span class="SimpleMath">[i]</span> is <code class="keyw">true</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, 2, 3, 4 ] < [ 1, 2, 4, 8 ]; # <list1>[3] < <list2>[3]</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, 2, 3 ] < [ 1, 2, 3, 5 ]; # <list1>[4] is unbound and thus < 5</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, , 3, 4 ] < [ 1, -1, 3 ]; # <list1>[2] is unbound and thus < -1</span>
true
</pre></div>
<p>Note that for comparing two lists with <code class="code"><</code> or <code class="code"><=</code>, the (relevant) list elements must be comparable with <code class="code"><</code>, which is usually <em>not</em> the case for objects in different families, see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>. Also for the possibility to compare lists with other objects, see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>.</p>
<p><a id="X845EEAF083D43CCE" name="X845EEAF083D43CCE"></a></p>
<h4>21.11 <span class="Heading">Arithmetic for Lists</span></h4>
<p>It is convenient to have arithmetic operations for lists, in particular because in <strong class="pkg">GAP</strong> row vectors and matrices are special kinds of lists. However, it is the wide variety of list objects because of which we prescribe arithmetic operations <em>not for all</em> of them. (Keep in mind that "list" means just an object in the category <code class="func">IsList</code> (<a href="chap21.html#X7C4CC4EA8299701E"><span class="RefLink">21.1-1</span></a>).)</p>
<p>(Due to the intended generality and flexibility, the definitions given in the following sections are quite technical. But for not too complicated cases such as matrices (see <a href="chap24.html#X7899335779A39A95"><span class="RefLink">24.3</span></a>) and row vectors (see <a href="chap23.html#X85516C3179C229DB"><span class="RefLink">23.2</span></a>) whose entries aren't lists, the resulting behaviour should be intuitive.)</p>
<p>For example, we want to deal with matrices which can be added and multiplied in the usual way, via the infix operators <code class="code">+</code> and <code class="code">*</code>; and we want also Lie matrices, with the same additive behaviour but with the multiplication defined by the Lie bracket. Both kinds of matrices shall be lists, with the usual access to their rows, with <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>) returning the number of rows etc.</p>
<p>For the categories and attributes that control the arithmetic behaviour of lists, see <a href="chap21.html#X84D642967B8546B7"><span class="RefLink">21.12</span></a>.</p>
<p>For the definition of return values of additive and multiplicative operations whose arguments are lists in these filters, see <a href="chap21.html#X7E6A1F66781BE923"><span class="RefLink">21.13</span></a> and <a href="chap21.html#X782ED7F27D8C7FC1"><span class="RefLink">21.14</span></a>, respectively. It should be emphasized that these sections describe only what the return values are, and not how they are computed.</p>
<p>For the mutability status of the return values, see <a href="chap21.html#X8676EFE67972FD06"><span class="RefLink">21.15</span></a>. (Note that this is not dealt with in the sections about the result values.)</p>
<p>Further details about the special cases of row vectors and matrices can be found in <a href="chap23.html#X85516C3179C229DB"><span class="RefLink">23.2</span></a> and in <a href="chap24.html#X7899335779A39A95"><span class="RefLink">24.3</span></a>, the compression status is dealt with in <a href="chap23.html#X8679F7DD7DFCBD9C"><span class="RefLink">23.3</span></a> and <a href="chap24.html#X873822B6830CE367"><span class="RefLink">24.14</span></a>.</p>
<p><a id="X84D642967B8546B7" name="X84D642967B8546B7"></a></p>
<h4>21.12 <span class="Heading">Filters Controlling the Arithmetic Behaviour of Lists</span></h4>
<p>The arithmetic behaviour of lists is controlled by their types. The following categories and attributes are used for that.</p>
<p>Note that we distinguish additive and multiplicative behaviour. For example, Lie matrices have the usual additive behaviour but not the usual multiplicative behaviour.</p>
<p><a id="X87ABCEE9809585A0" name="X87ABCEE9809585A0"></a></p>
<h5>21.12-1 IsGeneralizedRowVector</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsGeneralizedRowVector</code>( <var class="Arg">list</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>For a list <var class="Arg">list</var>, the value <code class="keyw">true</code> for <code class="func">IsGeneralizedRowVector</code> indicates that the additive arithmetic behaviour of <var class="Arg">list</var> is as defined in <a href="chap21.html#X7E6A1F66781BE923"><span class="RefLink">21.13</span></a>, and that the attribute <code class="func">NestingDepthA</code> (<a href="chap21.html#X8428E77B86722D52"><span class="RefLink">21.12-4</span></a>) will return a nonzero value when called with <var class="Arg">list</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsList( "abc" ); IsGeneralizedRowVector( "abc" );</span>
true
false
<span class="GAPprompt">gap></span> <span class="GAPinput">liemat:= LieObject( [ [ 1, 2 ], [ 3, 4 ] ] );</span>
LieObject( [ [ 1, 2 ], [ 3, 4 ] ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGeneralizedRowVector( liemat );</span>
true
</pre></div>
<p><a id="X7FBCA5B58308C158" name="X7FBCA5B58308C158"></a></p>
<h5>21.12-2 IsMultiplicativeGeneralizedRowVector</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMultiplicativeGeneralizedRowVector</code>( <var class="Arg">list</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>For a list <var class="Arg">list</var>, the value <code class="keyw">true</code> for <code class="func">IsMultiplicativeGeneralizedRowVector</code> indicates that the multiplicative arithmetic behaviour of <var class="Arg">list</var> is as defined in <a href="chap21.html#X782ED7F27D8C7FC1"><span class="RefLink">21.14</span></a>, and that the attribute <code class="func">NestingDepthM</code> (<a href="chap21.html#X84B383B97FD986CD"><span class="RefLink">21.12-5</span></a>) will return a nonzero value when called with <var class="Arg">list</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMultiplicativeGeneralizedRowVector( liemat );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">bas:= CanonicalBasis( FullRowSpace( Rationals, 3 ) );</span>
CanonicalBasis( ( Rationals^3 ) )
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMultiplicativeGeneralizedRowVector( bas );</span>
true
</pre></div>
<p>Note that the filters <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>), <code class="func">IsMultiplicativeGeneralizedRowVector</code> do <em>not</em> enable default methods for addition or multiplication (cf. <code class="func">IsListDefault</code> (<a href="chap21.html#X7BAD12E67BFC90DE"><span class="RefLink">21.12-3</span></a>)).</p>
<p><a id="X7BAD12E67BFC90DE" name="X7BAD12E67BFC90DE"></a></p>
<h5>21.12-3 IsListDefault</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsListDefault</code>( <var class="Arg">list</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>For a list <var class="Arg">list</var>, <code class="func">IsListDefault</code> indicates that the default methods for arithmetic operations of lists, such as pointwise addition and multiplication as inner product or matrix product, shall be applicable to <var class="Arg">list</var>.</p>
<p><code class="func">IsListDefault</code> implies <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>) and <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>).</p>
<p>All internally represented lists are in this category, and also all lists in the representations <code class="code">IsGF2VectorRep</code>, <code class="code">Is8BitVectorRep</code>, <code class="code">IsGF2MatrixRep</code>, and <code class="code">Is8BitMatrixRep</code> (see <a href="chap23.html#X8679F7DD7DFCBD9C"><span class="RefLink">23.3</span></a> and <a href="chap24.html#X873822B6830CE367"><span class="RefLink">24.14</span></a>). Note that the result of an arithmetic operation with lists in <code class="func">IsListDefault</code> will in general be an internally represented list, so most "wrapped list objects" will not lie in <code class="func">IsListDefault</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">v:= [ 1, 2 ];; m:= [ v, 2*v ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsListDefault( v ); IsListDefault( m );</span>
true
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsListDefault( bas ); IsListDefault( liemat );</span>
true
false
</pre></div>
<p><a id="X8428E77B86722D52" name="X8428E77B86722D52"></a></p>
<h5>21.12-4 NestingDepthA</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NestingDepthA</code>( <var class="Arg">obj</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>For a <strong class="pkg">GAP</strong> object <var class="Arg">obj</var>, <code class="func">NestingDepthA</code> returns the <em>additive nesting depth</em> of <var class="Arg">obj</var>. This is defined recursively as the integer <span class="SimpleMath">0</span> if <var class="Arg">obj</var> is not in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>), as the integer <span class="SimpleMath">1</span> if <var class="Arg">obj</var> is an empty list in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>), and as <span class="SimpleMath">1</span> plus the additive nesting depth of the first bound entry in <var class="Arg">obj</var> otherwise.</p>
<p><a id="X84B383B97FD986CD" name="X84B383B97FD986CD"></a></p>
<h5>21.12-5 NestingDepthM</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NestingDepthM</code>( <var class="Arg">obj</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>For a <strong class="pkg">GAP</strong> object <var class="Arg">obj</var>, <code class="func">NestingDepthM</code> returns the <em>multiplicative nesting depth</em> of <var class="Arg">obj</var>. This is defined recursively as the integer <span class="SimpleMath">0</span> if <var class="Arg">obj</var> is not in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>), as the integer <span class="SimpleMath">1</span> if <var class="Arg">obj</var> is an empty list in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>), and as <span class="SimpleMath">1</span> plus the multiplicative nesting depth of the first bound entry in <var class="Arg">obj</var> otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NestingDepthA( v ); NestingDepthM( v );</span>
1
1
<span class="GAPprompt">gap></span> <span class="GAPinput">NestingDepthA( m ); NestingDepthM( m );</span>
2
2
<span class="GAPprompt">gap></span> <span class="GAPinput">NestingDepthA( liemat ); NestingDepthM( liemat );</span>
2
0
<span class="GAPprompt">gap></span> <span class="GAPinput">l1:= [ [ 1, 2 ], 3 ];; l2:= [ 1, [ 2, 3 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NestingDepthA( l1 ); NestingDepthM( l1 );</span>
2
2
<span class="GAPprompt">gap></span> <span class="GAPinput">NestingDepthA( l2 ); NestingDepthM( l2 );</span>
1
1
</pre></div>
<p><a id="X7E6A1F66781BE923" name="X7E6A1F66781BE923"></a></p>
<h4>21.13 <span class="Heading">Additive Arithmetic for Lists</span></h4>
<p>In this general context, we define the results of additive operations only in the following situations. For unary operations (zero and additive inverse), the unique argument must be in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>); for binary operations (addition and subtraction), at least one argument must be in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>), and the other either is not a list or also in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>).</p>
<p>(For non-list <strong class="pkg">GAP</strong> objects, defining the results of unary operations is not an issue here, and if at least one argument is a list not in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>), it shall be left to this argument whether the result in question is defined and what it is.)</p>
<p><a id="X86A85ADC85C451DC" name="X86A85ADC85C451DC"></a></p>
<h5>21.13-1 <span class="Heading">Zero for lists</span></h5>
<p>The zero (see <code class="func">Zero</code> (<a href="chap31.html#X8040AC7A79FFC442"><span class="RefLink">31.10-3</span></a>)) of a list <span class="SimpleMath">x</span> in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>) is defined as the list whose entry at position <span class="SimpleMath">i</span> is the zero of <span class="SimpleMath">x[i]</span> if this entry is bound, and is unbound otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Zero( [ 1, 2, 3 ] ); Zero( [ [ 1, 2 ], 3 ] ); Zero( liemat );</span>
[ 0, 0, 0 ]
[ [ 0, 0 ], 0 ]
LieObject( [ [ 0, 0 ], [ 0, 0 ] ] )
</pre></div>
<p><a id="X7B91CE4D814C2D08" name="X7B91CE4D814C2D08"></a></p>
<h5>21.13-2 <span class="Heading">AdditiveInverse for lists</span></h5>
<p>The additive inverse (see <code class="func">AdditiveInverse</code> (<a href="chap31.html#X84BB723C81D55D63"><span class="RefLink">31.10-9</span></a>)) of a list <span class="SimpleMath">x</span> in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>) is defined as the list whose entry at position <span class="SimpleMath">i</span> is the additive inverse of <span class="SimpleMath">x[i]</span> if this entry is bound, and is unbound otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AdditiveInverse( [ 1, 2, 3 ] ); AdditiveInverse( [ [ 1, 2 ], 3 ] );</span>
[ -1, -2, -3 ]
[ [ -1, -2 ], -3 ]
</pre></div>
<p><a id="X842D123E7EE5E3DB" name="X842D123E7EE5E3DB"></a></p>
<h5>21.13-3 <span class="Heading">Addition of lists</span></h5>
<p>If <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> are in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>) and have the same additive nesting depth (see <code class="func">NestingDepthA</code> (<a href="chap21.html#X8428E77B86722D52"><span class="RefLink">21.12-4</span></a>)), the sum <span class="SimpleMath">x + y</span> is defined <em>pointwise</em>, in the sense that the result is a list whose entry at position <span class="SimpleMath">i</span> is <span class="SimpleMath">x[i] + y[i]</span> if these entries are bound, is a shallow copy (see <code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>)) of <span class="SimpleMath">x[i]</span> or <span class="SimpleMath">y[i]</span> if the other argument is not bound at position <span class="SimpleMath">i</span>, and is unbound if both <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> are unbound at position <span class="SimpleMath">i</span>.</p>
<p>If <span class="SimpleMath">x</span> is in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>) and <span class="SimpleMath">y</span> is in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>) and has lower additive nesting depth, or is neither a list nor a domain, the sum <span class="SimpleMath">x + y</span> is defined as a list whose entry at position <span class="SimpleMath">i</span> is <span class="SimpleMath">x[i] + y</span> if <span class="SimpleMath">x</span> is bound at position <span class="SimpleMath">i</span>, and is unbound if not. The equivalent holds in the reversed case, where the order of the summands is kept, as addition is not always commutative.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">1 + [ 1, 2, 3 ]; [ 1, 2, 3 ] + [ 0, 2, 4 ]; [ 1, 2 ] + [ Z(2) ];</span>
[ 2, 3, 4 ]
[ 1, 4, 7 ]
[ 0*Z(2), 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l1:= [ 1, , 3, 4 ];; l2:= [ , 2, 3, 4, 5 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">l3:= [ [ 1, 2 ], , [ 5, 6 ] ];; l4:= [ , [ 3, 4 ], [ 5, 6 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NestingDepthA( l1 ); NestingDepthA( l2 );</span>
1
1
<span class="GAPprompt">gap></span> <span class="GAPinput">NestingDepthA( l3 ); NestingDepthA( l4 );</span>
2
2
<span class="GAPprompt">gap></span> <span class="GAPinput">l1 + l2;</span>
[ 1, 2, 6, 8, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l1 + l3;</span>
[ [ 2, 2, 3, 4 ],, [ 6, 6, 3, 4 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l2 + l4;</span>
[ , [ 3, 6, 3, 4, 5 ], [ 5, 8, 3, 4, 5 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l3 + l4;</span>
[ [ 1, 2 ], [ 3, 4 ], [ 10, 12 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l1 + [];</span>
[ 1,, 3, 4 ]
</pre></div>
<p><a id="X7C3DC8BE78DEECDE" name="X7C3DC8BE78DEECDE"></a></p>
<h5>21.13-4 <span class="Heading">Subtraction of lists</span></h5>
<p>For two <strong class="pkg">GAP</strong> objects <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> of which one is in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>) and the other is also in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>) or is neither a list nor a domain, <span class="SimpleMath">x - y</span> is defined as <span class="SimpleMath">x + (-y)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l1 - l2;</span>
[ 1, -2, 0, 0, -5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l1 - l3;</span>
[ [ 0, -2, 3, 4 ],, [ -4, -6, 3, 4 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l2 - l4;</span>
[ , [ -3, -2, 3, 4, 5 ], [ -5, -4, 3, 4, 5 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l3 - l4;</span>
[ [ 1, 2 ], [ -3, -4 ], [ 0, 0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l1 - [];</span>
[ 1,, 3, 4 ]
</pre></div>
<p><a id="X782ED7F27D8C7FC1" name="X782ED7F27D8C7FC1"></a></p>
<h4>21.14 <span class="Heading">Multiplicative Arithmetic for Lists</span></h4>
<p>In this general context, we define the results of multiplicative operations only in the following situations. For unary operations (one and inverse), the unique argument must be in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>); for binary operations (multiplication and division), at least one argument must be in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>), and the other either not a list or also in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>).</p>
<p>(For non-list <strong class="pkg">GAP</strong> objects, defining the results of unary operations is not an issue here, and if at least one argument is a list not in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>), it shall be left to this argument whether the result in question is defined and what it is.)</p>
<p><a id="X79A8A5627FD42FA5" name="X79A8A5627FD42FA5"></a></p>
<h5>21.14-1 <span class="Heading">One for lists</span></h5>
<p>The one (see <code class="func">One</code> (<a href="chap31.html#X8046262384895B2A"><span class="RefLink">31.10-2</span></a>)) of a dense list <var class="Arg">x</var> in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) such that <var class="Arg">x</var> has even multiplicative nesting depth and has the same length as each of its rows is defined as the usual identity matrix on the outer two levels, that is, an identity matrix of the same dimensions, with diagonal entries <code class="code">One( <var class="Arg">x</var>[1][1] )</code> and off-diagonal entries <code class="code">Zero( <var class="Arg">x</var>[1][1] )</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">One( [ [ 1, 2 ], [ 3, 4 ] ] );</span>
[ [ 1, 0 ], [ 0, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">One( [ [ [ [ 1 ] ], [ [ 2 ] ] ], [ [ [ 3 ] ], [ [ 4 ] ] ] ] );</span>
[ [ [ [ 1 ] ], [ [ 0 ] ] ], [ [ [ 0 ] ], [ [ 1 ] ] ] ]
</pre></div>
<p><a id="X78C6C1E2849D303A" name="X78C6C1E2849D303A"></a></p>
<h5>21.14-2 <span class="Heading">Inverse for lists</span></h5>
<p>The inverse (see <code class="func">Inverse</code> (<a href="chap31.html#X78EE524E83624057"><span class="RefLink">31.10-8</span></a>)) of an invertible square table <var class="Arg">x</var> in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) whose entries lie in a common field is defined as the usual inverse <span class="SimpleMath">y</span>, i.e., a square matrix over the same field such that <span class="SimpleMath"><var class="Arg">x</var> y</span> and <span class="SimpleMath">y <var class="Arg">x</var></span> is equal to <code class="code">One( <var class="Arg">x</var> )</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Inverse( [ [ 1, 2 ], [ 3, 4 ] ] );</span>
[ [ -2, 1 ], [ 3/2, -1/2 ] ]
</pre></div>
<p><a id="X84FDB95179BFE4CD" name="X84FDB95179BFE4CD"></a></p>
<h5>21.14-3 <span class="Heading">Multiplication of lists</span></h5>
<p>There are three possible computations that might be triggered by a multiplication involving a list in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>). Namely, <span class="SimpleMath">x * y</span> might be</p>
<dl>
<dt><strong class="Mark">(I)</strong></dt>
<dd><p>the inner product <span class="SimpleMath">x[1] * y[1] + x[2] * y[2] + ⋯ + x[n] * y[n]</span>, where summands are omitted for which the entry in <span class="SimpleMath">x</span> or <span class="SimpleMath">y</span> is unbound (if this leaves no summand then the multiplication is an error), or</p>
</dd>
<dt><strong class="Mark">(L)</strong></dt>
<dd><p>the left scalar multiple, i.e., a list whose entry at position <span class="SimpleMath">i</span> is <span class="SimpleMath">x * y[i]</span> if <span class="SimpleMath">y</span> is bound at position <span class="SimpleMath">i</span>, and is unbound if not, or</p>
</dd>
<dt><strong class="Mark">(R)</strong></dt>
<dd><p>the right scalar multiple, i.e., a list whose entry at position <span class="SimpleMath">i</span> is <span class="SimpleMath">x[i] * y</span> if <span class="SimpleMath">x</span> is bound at position <span class="SimpleMath">i</span>, and is unbound if not.</p>
</dd>
</dl>
<p>Our aim is to generalize the basic arithmetic of simple row vectors and matrices, so we first summarize the situations that shall be covered.</p>
<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter"></td>
<td class="tdcenter">scl</td>
<td class="tdcenter">vec</td>
<td class="tdcenter">mat</td>
</tr>
<tr>
<td class="tdcenter">scl</td>
<td class="tdcenter"></td>
<td class="tdcenter">(L)</td>
<td class="tdcenter">(L)</td>
</tr>
<tr>
<td class="tdcenter">vec</td>
<td class="tdcenter">(R)</td>
<td class="tdcenter">(I)</td>
<td class="tdcenter">(I)</td>
</tr>
<tr>
<td class="tdcenter">mat</td>
<td class="tdcenter">(R)</td>
<td class="tdcenter">(R)</td>
<td class="tdcenter">(R)</td>
</tr>
</table><br /><p> </p><br />
</div>
<p>This means for example that the product of a scalar (scl) with a vector (vec) or a matrix (mat) is computed according to (L). Note that this is asymmetric.</p>
<p>Now we can state the general multiplication rules.</p>
<p>If exactly one argument is in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) then we regard the other argument (which is then neither a list nor a domain) as a scalar, and specify result (L) or (R), depending on ordering.</p>
<p>In the remaining cases, both <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> are in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>), and we distinguish the possibilities by their multiplicative nesting depths. An argument with <em>odd</em> multiplicative nesting depth is regarded as a vector, and an argument with <em>even</em> multiplicative nesting depth is regarded as a scalar or a matrix.</p>
<p>So if both arguments have odd multiplicative nesting depth, we specify result (I).</p>
<p>If exactly one argument has odd nesting depth, the other is treated as a scalar if it has lower multiplicative nesting depth, and as a matrix otherwise. In the former case, we specify result (L) or (R), depending on ordering; in the latter case, we specify result (L) or (I), depending on ordering.</p>
<p>We are left with the case that each argument has even multiplicative nesting depth. If the two depths are equal, we treat the computation as a matrix product, and specify result (R). Otherwise, we treat the less deeply nested argument as a scalar and the other as a matrix, and specify result (L) or (R), depending on ordering.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ] * (1,4);</span>
[ (1,4), (1,4)(2,3), (1,2,4), (1,2,3,4), (1,3,2,4), (1,3,4) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, 2, , 4 ] * 2;</span>
[ 2, 4,, 8 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, 2, 3 ] * [ 1, 3, 5, 7 ];</span>
22
<span class="GAPprompt">gap></span> <span class="GAPinput">m:= [ [ 1, 2 ], 3 ];; m * m;</span>
[ [ 7, 8 ], [ [ 3, 6 ], 9 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">m * m = [ m[1] * m, m[2] * m ];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">n:= [ 1, [ 2, 3 ] ];; n * n;</span>
14
<span class="GAPprompt">gap></span> <span class="GAPinput">n * n = n[1] * n[1] + n[2] * n[2];</span>
true
</pre></div>
<p><a id="X82EA2A5B786181C7" name="X82EA2A5B786181C7"></a></p>
<h5>21.14-4 <span class="Heading">Division of lists</span></h5>
<p>For two <strong class="pkg">GAP</strong> objects <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> of which one is in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) and the other is also in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) or is neither a list nor a domain, <span class="SimpleMath">x / y</span> is defined as <span class="SimpleMath">x * y^{-1}</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 1, 2, 3 ] / 2; [ 1, 2 ] / [ [ 1, 2 ], [ 3, 4 ] ];</span>
[ 1/2, 1, 3/2 ]
[ 1, 0 ]
</pre></div>
<p><a id="X7A0FD70C80B95C00" name="X7A0FD70C80B95C00"></a></p>
<h5>21.14-5 <span class="Heading">mod for lists</span></h5>
<p>If <var class="Arg">x</var> and <var class="Arg">y</var> are in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) and have the same multiplicative nesting depth (see <code class="func">NestingDepthM</code> (<a href="chap21.html#X84B383B97FD986CD"><span class="RefLink">21.12-5</span></a>)), <code class="code"><var class="Arg">x</var> mod <var class="Arg">y</var></code> is defined <em>pointwise</em>, in the sense that the result is a list whose entry at position <span class="SimpleMath">i</span> is <code class="code"><var class="Arg">x</var>[i] mod <var class="Arg">y</var>[i]</code> if these entries are bound, is a shallow copy (see <code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>)) of <span class="SimpleMath">x[i]</span> or <span class="SimpleMath">y[i]</span> if the other argument is not bound at position <span class="SimpleMath">i</span>, and is unbound if both <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> are unbound at position <span class="SimpleMath">i</span>.</p>
<p>If <span class="SimpleMath">x</span> is in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) and <span class="SimpleMath">y</span> is in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) and has lower multiplicative nesting depth or is neither a list nor a domain, <code class="code"><var class="Arg">x</var> mod <var class="Arg">y</var></code> is defined as a list whose entry at position <span class="SimpleMath">i</span> is <code class="code"><var class="Arg">x</var>[i] mod <var class="Arg">y</var></code> if <var class="Arg">x</var> is bound at position <span class="SimpleMath">i</span>, and is unbound if not. The equivalent holds in the reversed case, where the order of the arguments is kept.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">4711 mod [ 2, 3,, 5, 7 ];</span>
[ 1, 1,, 1, 0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 2, 3, 4, 5, 6 ] mod 3;</span>
[ 2, 0, 1, 2, 0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 10, 12, 14, 16 ] mod [ 3, 5, 7 ];</span>
[ 1, 2, 0, 16 ]
</pre></div>
<p><a id="X84BB2DFB8432A1A4" name="X84BB2DFB8432A1A4"></a></p>
<h5>21.14-6 <span class="Heading">Left quotients of lists</span></h5>
<p>For two <strong class="pkg">GAP</strong> objects <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> of which one is in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) and the other is also in <code class="func">IsMultiplicativeGeneralizedRowVector</code> (<a href="chap21.html#X7FBCA5B58308C158"><span class="RefLink">21.12-2</span></a>) or is neither a list nor a domain, <code class="code">LeftQuotient( <var class="Arg">x</var>, <var class="Arg">y</var> )</code> is defined as <span class="SimpleMath">x^{-1} * y</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftQuotient( [ [ 1, 2 ], [ 3, 4 ] ], [ 1, 2 ] );</span>
[ 0, 1/2 ]
</pre></div>
<p><a id="X8676EFE67972FD06" name="X8676EFE67972FD06"></a></p>
<h4>21.15 <span class="Heading">Mutability Status and List Arithmetic</span></h4>
<p>Many results of arithmetic operations, when applied to lists, are again lists, and it is of interest whether their entries are mutable or not (if applicable). Note that the mutability status of the result itself is already defined by the general rule for any result of an arithmetic operation, not only for lists (see <a href="chap12.html#X7F0C119682196D65"><span class="RefLink">12.6</span></a>).</p>
<p>However, we do <em>not</em> define exactly the mutability status for each element on each level of a nested list returned by an arithmetic operation. (Of course it would be possible to define this recursively, but since the methods used are in general not recursive, in particular for efficient multiplication of compressed matrices, such a general definition would be a burden in these cases.) Instead we consider, for a list <span class="SimpleMath">x</span> in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>), the sequence <span class="SimpleMath">x = x_1, x_2, ... x_n</span> where <span class="SimpleMath">x_{i+1}</span> is the first bound entry in <span class="SimpleMath">x_i</span> if exists (that is, if <span class="SimpleMath">x_i</span> is a nonempty list), and <span class="SimpleMath">n</span> is the largest <span class="SimpleMath">i</span> such that <span class="SimpleMath">x_i</span> lies in <code class="func">IsGeneralizedRowVector</code> (<a href="chap21.html#X87ABCEE9809585A0"><span class="RefLink">21.12-1</span></a>). The <em>immutability level</em> of <span class="SimpleMath">x</span> is defined as infinity if <span class="SimpleMath">x</span> is immutable, and otherwise the number of <span class="SimpleMath">x_i</span> which are immutable. (So the immutability level of a mutable empty list is <span class="SimpleMath">0</span>.)</p>
<p>Thus a fully mutable matrix has immutability level <span class="SimpleMath">0</span>, and a mutable matrix with immutable first row has immutability level <span class="SimpleMath">1</span> (independent of the mutability of other rows).</p>
<p>The immutability level of the result of any of the binary operations discussed here is the minimum of the immutability levels of the arguments, provided that objects of the required mutability status exist in <strong class="pkg">GAP</strong>.</p>
<p>Moreover, the results have a "homogeneous" mutability status, that is, if the first bound entry at nesting depth <span class="SimpleMath">i</span> is immutable (mutable) then all entries at nesting depth <span class="SimpleMath">i</span> are immutable (mutable, provided that a mutable version of this entry exists in <strong class="pkg">GAP</strong>).</p>
<p>Thus the sum of two mutable matrices whose first rows are mutable is a matrix all of whose rows are mutable, and the product of two matrices whose first rows are immutable is a matrix all of whose rows are immutable, independent of the mutability status of the other rows of the arguments.</p>
<p>For example, the sum of a matrix (mutable or immutable, i.e., of immutability level one of <span class="SimpleMath">0</span>, <span class="SimpleMath">1</span>, or <span class="SimpleMath">2</span>) and a mutable row vector (i.e., immutability level <span class="SimpleMath">0</span>) is a fully mutable matrix. The product of two mutable row vectors of integers is an integer, and since <strong class="pkg">GAP</strong> does not support mutable integers, the result is immutable.</p>
<p>For unary arithmetic operations, there are three operations available, an attribute that returns an immutable result (<code class="func">Zero</code> (<a href="chap31.html#X8040AC7A79FFC442"><span class="RefLink">31.10-3</span></a>), <code class="func">AdditiveInverse</code> (<a href="chap31.html#X84BB723C81D55D63"><span class="RefLink">31.10-9</span></a>), <code class="func">One</code> (<a href="chap31.html#X8046262384895B2A"><span class="RefLink">31.10-2</span></a>), <code class="func">Inverse</code> (<a href="chap31.html#X78EE524E83624057"><span class="RefLink">31.10-8</span></a>)), an operation that returns a result that is mutable (<code class="func">ZeroOp</code> (<a href="chap31.html#X8040AC7A79FFC442"><span class="RefLink">31.10-3</span></a>), <code class="func">AdditiveInverseOp</code> (<a href="chap31.html#X84BB723C81D55D63"><span class="RefLink">31.10-9</span></a>), <code class="func">OneOp</code> (<a href="chap31.html#X8046262384895B2A"><span class="RefLink">31.10-2</span></a>), <code class="func">InverseOp</code> (<a href="chap31.html#X78EE524E83624057"><span class="RefLink">31.10-8</span></a>)), and an operation whose result has the same immutability level as the argument (<code class="func">ZeroSM</code> (<a href="chap31.html#X8040AC7A79FFC442"><span class="RefLink">31.10-3</span></a>), <code class="func">AdditiveInverseSM</code> (<a href="chap31.html#X84BB723C81D55D63"><span class="RefLink">31.10-9</span></a>), <code class="func">OneSM</code> (<a href="chap31.html#X8046262384895B2A"><span class="RefLink">31.10-2</span></a>), <code class="func">InverseSM</code> (<a href="chap31.html#X78EE524E83624057"><span class="RefLink">31.10-8</span></a>)). The last kind of operations is equivalent to the corresponding infix operations <code class="code">0 * <var class="Arg">list</var></code>, <code class="code">- <var class="Arg">list</var></code>, <code class="code"><var class="Arg">list</var>^0</code>, and <code class="code"><var class="Arg">list</var>^-1</code>. (This holds not only for lists, see <a href="chap12.html#X7F0C119682196D65"><span class="RefLink">12.6</span></a>.)</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable( l1 ); IsMutable( 2 * Immutable( [ 1, 2, 3 ] ) );</span>
true
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable( l2 ); IsMutable( l3 );</span>
true
true
</pre></div>
<p>An example motivating the mutability rule is the use of syntactic constructs such as <code class="code"><var class="Arg">obj</var> * <var class="Arg">list</var></code> and <code class="code">- <var class="Arg">list</var></code> as an elegant and efficient way to create mutable lists needed for further manipulations from mutable lists. In particular one can construct a mutable zero vector of length <span class="SimpleMath">n</span> by <code class="code">0 * [ 1 .. </code><span class="SimpleMath">n</span><code class="code"> ]</code>. The latter can be done also using <code class="func">ListWithIdenticalEntries</code> (<a href="chap21.html#X80FDB1457FF582E7"><span class="RefLink">21.15-1</span></a>).</p>
<p><a id="X80FDB1457FF582E7" name="X80FDB1457FF582E7"></a></p>
<h5>21.15-1 ListWithIdenticalEntries</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ListWithIdenticalEntries</code>( <var class="Arg">n</var>, <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>is a list <var class="Arg">list</var> of length <var class="Arg">n</var> that has the object <var class="Arg">obj</var> stored at each of the positions from <code class="code">1</code> to <var class="Arg">n</var>. Note that all elements of <var class="Arg">lists</var> are identical, see <a href="chap21.html#X7DD65BEA7EDB0CD7"><span class="RefLink">21.6</span></a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ListWithIdenticalEntries( 10, 0 );</span>
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
</pre></div>
<p><a id="X8196FD4779BCCA0C" name="X8196FD4779BCCA0C"></a></p>
<h4>21.16 <span class="Heading">Finding Positions in Lists</span></h4>
<p><a id="X79975EC6783B4293" name="X79975EC6783B4293"></a></p>
<h5>21.16-1 Position</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Position</code>( <var class="Arg">list</var>, <var class="Arg">obj</var>[, <var class="Arg">from</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the position of the first occurrence <var class="Arg">obj</var> in <var class="Arg">list</var>, or <code class="keyw">fail</code> if <var class="Arg">obj</var> is not contained in <var class="Arg">list</var>. If a starting index <var class="Arg">from</var> is given, it returns the position of the first occurrence starting the search <em>after</em> position <var class="Arg">from</var>.</p>
<p>Each call to the two argument version is translated into a call of the three argument version, with third argument the integer zero <code class="code">0</code>. (Methods for the two argument version must be installed as methods for the version with three arguments, the third being described by <code class="code">IsZeroCyc</code>.)</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Position( [ 2, 2, 1, 3 ], 1 );</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">Position( [ 2, 1, 1, 3 ], 1 );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">Position( [ 2, 1, 1, 3 ], 1, 2 );</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">Position( [ 2, 1, 1, 3 ], 1, 3 );</span>
fail
</pre></div>
<p><a id="X7FA9648883AE1B88" name="X7FA9648883AE1B88"></a></p>
<h5>21.16-2 Positions</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Positions</code>( <var class="Arg">list</var>, <var class="Arg">obj</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">‣ PositionsOp</code>( <var class="Arg">list</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the positions of <em>all</em> occurrences of <var class="Arg">obj</var> in <var class="Arg">list</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Positions([1,2,1,2,3,2,2],2);</span>
[ 2, 4, 6, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Positions([1,2,1,2,3,2,2],4);</span>
[ ]
</pre></div>
<p><a id="X7B4B10AE81602D4E" name="X7B4B10AE81602D4E"></a></p>
<h5>21.16-3 PositionCanonical</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionCanonical</code>( <var class="Arg">list</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the position of the canonical associate of <var class="Arg">obj</var> in <var class="Arg">list</var>. The definition of this associate depends on <var class="Arg">list</var>. For internally represented lists it is defined as the element itself (and <code class="func">PositionCanonical</code> thus defaults to <code class="func">Position</code> (<a href="chap21.html#X79975EC6783B4293"><span class="RefLink">21.16-1</span></a>), but for example for certain enumerators (see <a href="chap21.html#X7EA3ACE27E43D174"><span class="RefLink">21.23</span></a>) other canonical associates can be defined.</p>
<p>For example <code class="func">RightTransversal</code> (<a href="chap39.html#X85C65D06822E716F"><span class="RefLink">39.8-1</span></a>) defines the canonical associate to be the element in the transversal defining the same coset of a subgroup in a group.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:=Group((1,2,3,4),(1,2));;u:=Subgroup(g,[(1,2)(3,4),(1,3)(2,4)]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rt:=RightTransversal(g,u);;AsList(rt);</span>
[ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Position(rt,(1,2));</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionCanonical(rt,(1,2));</span>
2
</pre></div>
<p><a id="X7D2B25B484591506" name="X7D2B25B484591506"></a></p>
<h5>21.16-4 PositionNthOccurrence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionNthOccurrence</code>( <var class="Arg">list</var>, <var class="Arg">obj</var>, <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the position of the <var class="Arg">n</var>-th occurrence of <var class="Arg">obj</var> in <var class="Arg">list</var> and returns <code class="keyw">fail</code> if <var class="Arg">obj</var> does not occur <var class="Arg">n</var> times.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionNthOccurrence([1,2,3,2,4,2,1],1,1);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionNthOccurrence([1,2,3,2,4,2,1],1,2);</span>
7
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionNthOccurrence([1,2,3,2,4,2,1],2,3);</span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionNthOccurrence([1,2,3,2,4,2,1],2,4);</span>
fail
</pre></div>
<p><a id="X7A122E848464E534" name="X7A122E848464E534"></a></p>
<h5>21.16-5 PositionSorted</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionSorted</code>( <var class="Arg">list</var>, <var class="Arg">elm</var>[, <var class="Arg">func</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Called with two arguments, <code class="func">PositionSorted</code> returns the position of the element <var class="Arg">elm</var> in the sorted list <var class="Arg">list</var>.</p>
<p>Called with three arguments, <code class="func">PositionSorted</code> returns the position of the element <var class="Arg">elm</var> in the list <var class="Arg">list</var>, which must be sorted with respect to <var class="Arg">func</var>. <var class="Arg">func</var> must be a function of two arguments that returns <code class="keyw">true</code> if the first argument is less than the second argument, and <code class="keyw">false</code> otherwise.</p>
<p><code class="func">PositionSorted</code> returns <var class="Arg">pos</var> such that <span class="SimpleMath"><var class="Arg">list</var>[<var class="Arg">pos</var>-1] < <var class="Arg">elm</var></span> and <span class="SimpleMath"><var class="Arg">elm</var> ≤ <var class="Arg">list</var>[<var class="Arg">pos</var>]</span>. That means, if <var class="Arg">elm</var> appears once in <var class="Arg">list</var>, its position is returned. If <var class="Arg">elm</var> appears several times in <var class="Arg">list</var>, the position of the first occurrence is returned. If <var class="Arg">elm</var> is not an element of <var class="Arg">list</var>, the index where <var class="Arg">elm</var> must be inserted to keep the list sorted is returned.</p>
<p><code class="func">PositionSorted</code> uses binary search, whereas <code class="func">Position</code> (<a href="chap21.html#X79975EC6783B4293"><span class="RefLink">21.16-1</span></a>) can in general use only linear search, see the remark at the beginning of <a href="chap21.html#X80ABC25582343910"><span class="RefLink">21.19</span></a>. For sorting lists, see <a href="chap21.html#X83E558E37D1B44D4"><span class="RefLink">21.18</span></a>, for testing whether a list is sorted, see <code class="func">IsSortedList</code> (<a href="chap21.html#X7BAA9B0E81D4A884"><span class="RefLink">21.17-3</span></a>) and <code class="func">IsSSortedList</code> (<a href="chap21.html#X80CDAF45782E8DCB"><span class="RefLink">21.17-4</span></a>).</p>
<p>Specialized functions for certain kinds of lists must be installed as methods for the operation <code class="code">PositionSortedOp</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSorted( [1,4,5,5,6,7], 0 );</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSorted( [1,4,5,5,6,7], 2 );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSorted( [1,4,5,5,6,7], 4 );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSorted( [1,4,5,5,6,7], 5 );</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSorted( [1,4,5,5,6,7], 8 );</span>
7
</pre></div>
<p><a id="X78BFE9D78347C0DA" name="X78BFE9D78347C0DA"></a></p>
<h5>21.16-6 PositionSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionSet</code>( <var class="Arg">list</var>, <var class="Arg">obj</var>[, <var class="Arg">func</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">PositionSet</code> is a slight variation of <code class="func">PositionSorted</code> (<a href="chap21.html#X7A122E848464E534"><span class="RefLink">21.16-5</span></a>). The only difference to <code class="func">PositionSorted</code> (<a href="chap21.html#X7A122E848464E534"><span class="RefLink">21.16-5</span></a>) is that <code class="func">PositionSet</code> returns <code class="keyw">fail</code> if <var class="Arg">obj</var> is not in <var class="Arg">list</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSet( [1,4,5,5,6,7], 0 );</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSet( [1,4,5,5,6,7], 2 );</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSet( [1,4,5,5,6,7], 4 );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSet( [1,4,5,5,6,7], 5 );</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionSet( [1,4,5,5,6,7], 8 );</span>
fail
</pre></div>
<p><a id="X7E6C763A82C6153B" name="X7E6C763A82C6153B"></a></p>
<h5>21.16-7 PositionProperty</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionProperty</code>( <var class="Arg">list</var>, <var class="Arg">func</var>[, <var class="Arg">from</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the position of the first entry in the list <var class="Arg">list</var> for which the property tester function <var class="Arg">func</var> returns <code class="keyw">true</code>, or <code class="keyw">fail</code> if no such entry exists. If a starting index <var class="Arg">from</var> is given, it returns the position of the first entry satisfying <var class="Arg">func</var>, starting the search <em>after</em> position <var class="Arg">from</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionProperty( [10^7..10^8], IsPrime );</span>
20
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionProperty( [10^5..10^6],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> n -> not IsPrime(n) and IsPrimePowerInt(n) );</span>
490
</pre></div>
<p><code class="func">First</code> (<a href="chap21.html#X82801DFA84E11272"><span class="RefLink">21.20-22</span></a>) allows you to extract the first element of a list that satisfies a certain property.</p>
<p><a id="X7DA94D278304EC3D" name="X7DA94D278304EC3D"></a></p>
<h5>21.16-8 PositionsProperty</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionsProperty</code>( <var class="Arg">list</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the list of all those positions in the dense list <var class="Arg">list</var> for which the property tester function <var class="Arg">func</var> returns <code class="keyw">true</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= [ -5 .. 5 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionsProperty( l, IsPosInt );</span>
[ 7, 8, 9, 10, 11 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionsProperty( l, IsPrimeInt );</span>
[ 1, 3, 4, 8, 9, 11 ]
</pre></div>
<p><code class="func">PositionProperty</code> (<a href="chap21.html#X7E6C763A82C6153B"><span class="RefLink">21.16-7</span></a>) allows you to extract the position of the first element in a list that satisfies a certain property.</p>
<p><a id="X86C9E5C3863B3C03" name="X86C9E5C3863B3C03"></a></p>
<h5>21.16-9 PositionBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionBound</code>( <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the first index for which an element is bound in the list <var class="Arg">list</var>. For the empty list it returns <code class="keyw">fail</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionBound([1,2,3]);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionBound([,1,2,3]);</span>
2
</pre></div>
<p><a id="X865EF45D87ED1384" name="X865EF45D87ED1384"></a></p>
<h5>21.16-10 PositionNot</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionNot</code>( <var class="Arg">list</var>, <var class="Arg">val</var>[, <var class="Arg">from</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>For a list <var class="Arg">list</var> and an object <var class="Arg">val</var>, <code class="func">PositionNot</code> returns the smallest nonnegative integer <span class="SimpleMath">n</span> such that <span class="SimpleMath"><var class="Arg">list</var>[n]</span> is either unbound or not equal to <var class="Arg">val</var>. If a starting index <var class="Arg">from</var> is given, it returns the first position with this property starting the search <em>after</em> position <var class="Arg">from</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= [ 1, 1, 2, 3, 2 ];; PositionNot( l, 1 );</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionNot( l, 1, 4 ); PositionNot( l, 2, 4 );</span>
5
6
</pre></div>
<p><a id="X7F42E5AD87EC9D5A" name="X7F42E5AD87EC9D5A"></a></p>
<h5>21.16-11 PositionNonZero</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionNonZero</code>( <var class="Arg">vec</var>[, <var class="Arg">from</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>For a row vector <var class="Arg">vec</var>, <code class="func">PositionNonZero</code> returns the position of the first non-zero element of <var class="Arg">vec</var>, or <code class="code">Length(</code> <var class="Arg">vec</var> <code class="code">)+1</code> if all entries of <var class="Arg">vec</var> are zero.</p>
<p>If a starting index <var class="Arg">from</var> is given, it returns the position of the first occurrence starting the search <em>after</em> position <var class="Arg">from</var>.</p>
<p><code class="func">PositionNonZero</code> implements a special case of <code class="func">PositionNot</code> (<a href="chap21.html#X865EF45D87ED1384"><span class="RefLink">21.16-10</span></a>). Namely, the element to be avoided is the zero element, and the list must be (at least) homogeneous because otherwise the zero element cannot be specified implicitly.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionNonZero( [ 1, 1, 2, 3, 2 ] );</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionNonZero( [ 2, 3, 4, 5 ] * Z(2) );</span>
2
</pre></div>
<p><a id="X87A8C62A867D6DA4" name="X87A8C62A867D6DA4"></a></p>
<h5>21.16-12 PositionSublist</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionSublist</code>( <var class="Arg">list</var>, <var class="Arg">sub</var>[, <var class="Arg">from</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the smallest index in the list <var class="Arg">list</var> at which a sublist equal to <var class="Arg">sub</var> starts. If <var class="Arg">sub</var> does not occur the operation returns <code class="keyw">fail</code>. The version with given <var class="Arg">from</var> starts searching <em>after</em> position <var class="Arg">from</var>.</p>
<p>To determine whether <var class="Arg">sub</var> matches <var class="Arg">list</var> at a particular position, use <code class="func">IsMatchingSublist</code> (<a href="chap21.html#X83F8EC7C7BF27EFC"><span class="RefLink">21.17-1</span></a>) instead.</p>
<p><a id="X8132A2F5823F0CC0" name="X8132A2F5823F0CC0"></a></p>
<h5>21.16-13 PositionFirstComponent</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionFirstComponent</code>( <var class="Arg">list</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the index <var class="Arg">i</var> in <var class="Arg">list</var> such that <var class="Arg">list</var><code class="code">[</code><var class="Arg">i</var><code class="code">][1] = </code><var class="Arg">obj</var> or the place where such an entry should be added (cf. <code class="func">PositionSorted</code> (<a href="chap21.html#X7A122E848464E534"><span class="RefLink">21.16-5</span></a>)).</p>
<p><a id="X7865747A7CCF5812" name="X7865747A7CCF5812"></a></p>
<h4>21.17 <span class="Heading">Properties and Attributes for Lists</span></h4>
<p>A list that contains mutable objects (like lists or records) <em>cannot</em> store attribute values that depend on the values of its entries, such as whether it is homogeneous, sorted, or strictly sorted, as changes in any of its entries could change such property values, like the following example shows.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:=[[1],[2]];</span>
[ [ 1 ], [ 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSSortedList(l);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">l[1][1]:=3;</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSSortedList(l);</span>
false
</pre></div>
<p>For such lists these property values must be computed anew each time the property is asked for. For example, if <var class="Arg">list</var> is a list of mutable row vectors then the call of <code class="func">Position</code> (<a href="chap21.html#X79975EC6783B4293"><span class="RefLink">21.16-1</span></a>) with <var class="Arg">list</var> as first argument cannot take advantage of the fact that <var class="Arg">list</var> is in fact sorted. One solution is to call explicitly <code class="func">PositionSorted</code> (<a href="chap21.html#X7A122E848464E534"><span class="RefLink">21.16-5</span></a>) in such a situation, another solution is to replace <var class="Arg">list</var> by an immutable copy using <code class="func">Immutable</code> (<a href="chap12.html#X7F0ABF2C870B0CBB"><span class="RefLink">12.6-3</span></a>).</p>
<p><a id="X83F8EC7C7BF27EFC" name="X83F8EC7C7BF27EFC"></a></p>
<h5>21.17-1 IsMatchingSublist</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMatchingSublist</code>( <var class="Arg">list</var>, <var class="Arg">sub</var>[, <var class="Arg">at</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns <code class="keyw">true</code> if <var class="Arg">sub</var> matches a sublist of <var class="Arg">list</var> from position <code class="code">1</code> (or position <var class="Arg">at</var>, in the case of three arguments), or <code class="keyw">false</code>, otherwise. If <var class="Arg">sub</var> is empty <code class="keyw">true</code> is returned. If <var class="Arg">list</var> is empty but <var class="Arg">sub</var> is non-empty <code class="keyw">false</code> is returned.</p>
<p>If you actually want to know whether there is an <var class="Arg">at</var> for which <code class="code">IsMatchingSublist( <var class="Arg">list</var>, <var class="Arg">sub</var>, <var class="Arg">at</var> )</code> is true, use a construction like <code class="code">PositionSublist( <var class="Arg">list</var>, <var class="Arg">sub</var> ) <> fail</code> instead (see <code class="func">PositionSublist</code> (<a href="chap21.html#X87A8C62A867D6DA4"><span class="RefLink">21.16-12</span></a>)); it's more efficient.</p>
<p><a id="X7FA892828252BB3B" name="X7FA892828252BB3B"></a></p>
<h5>21.17-2 IsDuplicateFree</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDuplicateFree</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDuplicateFreeList</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><code class="func">IsDuplicateFree</code> returns <code class="keyw">true</code> if <var class="Arg">obj</var> is both a list or collection, and it is duplicate free; otherwise it returns <code class="keyw">false</code>. <code class="func">IsDuplicateFreeList</code> is a synonym for <code class="code">IsDuplicateFree and IsList</code>.</p>
<p>A list is <em>duplicate free</em> if it is dense and does not contain equal entries in different positions. Every domain (see <a href="chap12.html#X7BAF69417BB925F6"><span class="RefLink">12.4</span></a>) is duplicate free.</p>
<p>Note that <strong class="pkg">GAP</strong> cannot compare arbitrary objects (by equality). This can cause that <code class="func">IsDuplicateFree</code> runs into an error, if <var class="Arg">obj</var> is a list with some non-comparable entries.</p>
<p><a id="X7BAA9B0E81D4A884" name="X7BAA9B0E81D4A884"></a></p>
<h5>21.17-3 IsSortedList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSortedList</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>returns <code class="keyw">true</code> if <var class="Arg">obj</var> is a list and it is sorted, and <code class="keyw">false</code> otherwise.</p>
<p>A list <var class="Arg">list</var> is <em>sorted</em> if it is dense (see <code class="func">IsDenseList</code> (<a href="chap21.html#X870AA9D8798C93DD"><span class="RefLink">21.1-2</span></a>)) and satisfies the relation <span class="SimpleMath"><var class="Arg">list</var>[i] ≤ <var class="Arg">list</var>[j]</span> whenever <span class="SimpleMath">i < j</span>. Note that a sorted list is not necessarily duplicate free (see <code class="func">IsDuplicateFree</code> (<a href="chap21.html#X7FA892828252BB3B"><span class="RefLink">21.17-2</span></a>) and <code class="func">IsSSortedList</code> (<a href="chap21.html#X80CDAF45782E8DCB"><span class="RefLink">21.17-4</span></a>)).</p>
<p>Many sorted lists are in fact homogeneous (see <code class="func">IsHomogeneousList</code> (<a href="chap21.html#X7C71596C82B6EF35"><span class="RefLink">21.1-3</span></a>)), but also non-homogeneous lists may be sorted (see <a href="chap31.html#X7B3BC7BA7BB2646D"><span class="RefLink">31.11</span></a>).</p>
<p>In sorted lists, membership test and computing of positions can be done by binary search, see <a href="chap21.html#X80ABC25582343910"><span class="RefLink">21.19</span></a>.</p>
<p>Note that <strong class="pkg">GAP</strong> cannot compare (by less than) arbitrary objects. This can cause that <code class="func">IsSortedList</code> runs into an error, if <var class="Arg">obj</var> is a list with some non-comparable entries.</p>
<p><a id="X80CDAF45782E8DCB" name="X80CDAF45782E8DCB"></a></p>
<h5>21.17-4 IsSSortedList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSSortedList</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSet</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>returns <code class="keyw">true</code> if <var class="Arg">obj</var> is a list and it is strictly sorted, and <code class="keyw">false</code> otherwise. <code class="func">IsSSortedList</code> is short for "is strictly sorted list"; <code class="func">IsSet</code> is just a synonym for <code class="func">IsSSortedList</code>.</p>
<p>A list <var class="Arg">list</var> is <em>strictly sorted</em> if it is sorted (see <code class="func">IsSortedList</code> (<a href="chap21.html#X7BAA9B0E81D4A884"><span class="RefLink">21.17-3</span></a>)) and satisfies the relation <span class="SimpleMath"><var class="Arg">list</var>[i] < <var class="Arg">list</var>[j]</span> whenever <span class="SimpleMath">i < j</span>. In particular, such lists are duplicate free (see <code class="func">IsDuplicateFree</code> (<a href="chap21.html#X7FA892828252BB3B"><span class="RefLink">21.17-2</span></a>)).</p>
<p>(Currently there is little special treatment of lists that are sorted but not strictly sorted. In particular, internally represented lists will <em>not</em> store that they are sorted but not strictly sorted.)</p>
<p>Note that <strong class="pkg">GAP</strong> cannot compare (by less than) arbitrary objects. This can cause that <code class="func">IsSSortedList</code> runs into an error, if <var class="Arg">obj</var> is a list with some non-comparable entries.</p>
<p><a id="X780769238600AFD1" name="X780769238600AFD1"></a></p>
<h5>21.17-5 Length</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Length</code>( <var class="Arg">list</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the <em>length</em> of the list <var class="Arg">list</var>, which is defined to be the index of the last bound entry in <var class="Arg">list</var>.</p>
<p><a id="X7B55FB967CDEF468" name="X7B55FB967CDEF468"></a></p>
<h5>21.17-6 ConstantTimeAccessList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ConstantTimeAccessList</code>( <var class="Arg">list</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">ConstantTimeAccessList</code> returns an immutable list containing the same elements as the list <var class="Arg">list</var> (which may have holes) in the same order. If <var class="Arg">list</var> is already a constant time access list, <code class="func">ConstantTimeAccessList</code> returns an immutable copy of <var class="Arg">list</var> directly. Otherwise it puts all elements and holes of <var class="Arg">list</var> into a new list and makes that list immutable.</p>
<p><a id="X83E558E37D1B44D4" name="X83E558E37D1B44D4"></a></p>
<h4>21.18 <span class="Heading">Sorting Lists</span></h4>
<p><a id="X7FE4975F8166884D" name="X7FE4975F8166884D"></a></p>
<h5>21.18-1 Sort</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Sort</code>( <var class="Arg">list</var>[, <var class="Arg">func</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>sorts the list <var class="Arg">list</var> in increasing order. In the one argument form <code class="func">Sort</code> uses the operator <code class="code"><</code> to compare the elements. (If the list is not homogeneous it is the users responsibility to ensure that <code class="code"><</code> is defined for all element pairs, see <a href="chap31.html#X7B3BC7BA7BB2646D"><span class="RefLink">31.11</span></a>) In the two argument form <code class="func">Sort</code> uses the function <var class="Arg">func</var> to compare elements. <var class="Arg">func</var> must be a function taking two arguments that returns <code class="keyw">true</code> if the first is regarded as strictly smaller than the second, and <code class="keyw">false</code> otherwise.</p>
<p>Note that, in cases where it is applicable, <code class="func">SortBy</code> is likely to be more efficient.</p>
<p><code class="func">Sort</code> does not return anything, it just changes the argument <var class="Arg">list</var>. Use <code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>) if you want to keep <var class="Arg">list</var>. Use <code class="func">Reversed</code> (<a href="chap21.html#X7C4FDB007C3F54A1"><span class="RefLink">21.20-7</span></a>) if you want to get a new list that is sorted in decreasing order.</p>
<p>It is possible to sort lists that contain multiple elements which compare equal. It is not guaranteed that those elements keep their relative order, i.e., <code class="func">Sort</code> is not stable.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">list := [ 5, 4, 6, 1, 7, 5 ];; Sort( list ); list;</span>
[ 1, 4, 5, 5, 6, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">list := [ [0,6], [1,2], [1,3], [1,5], [0,4], [3,4] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Sort( list, function(v,w) return v*v < w*w; end );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">list; # sorted according to the Euclidean distance from [0,0]</span>
[ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 3, 4 ], [ 1, 5 ], [ 0, 6 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">list := [ [0,6], [1,3], [3,4], [1,5], [1,2], [0,4], ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Sort( list, function(v,w) return v[1] < w[1]; end );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"># note the random order of the elements with equal first component:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">list;</span>
[ [ 0, 6 ], [ 0, 4 ], [ 1, 3 ], [ 1, 5 ], [ 1, 2 ], [ 3, 4 ] ]
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SortBy</code>( <var class="Arg">list</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>sorts the list <var class="Arg">list</var> into an order such that <code class="code">func(list[i]) <= func(list[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(list[i])</code> is computed just once and stored, making this more efficient than using the two-argument version of <code class="func">Sort</code> in many cases.</p>
<p><a id="X791F2B2C7E9B9A46" name="X791F2B2C7E9B9A46"></a></p>
<h5>21.18-2 SortParallel</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SortParallel</code>( <var class="Arg">list1</var>, <var class="Arg">list2</var>[, <var class="Arg">func</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>sorts the list <var class="Arg">list1</var> in increasing order just as <code class="func">Sort</code> (<a href="chap21.html#X7FE4975F8166884D"><span class="RefLink">21.18-1</span></a>) does. In parallel it applies the same exchanges that are necessary to sort <var class="Arg">list1</var> to the list <var class="Arg">list2</var>, which must of course have at least as many elements as <var class="Arg">list1</var> does.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">list1 := [ 5, 4, 6, 1, 7, 5 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">list2 := [ 2, 3, 5, 7, 8, 9 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SortParallel( list1, list2 );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">list1;</span>
[ 1, 4, 5, 5, 6, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">list2;</span>
[ 7, 3, 2, 9, 5, 8 ]
</pre></div>
<p>Note that <code class="code">[ 7, 3, 2, 9, 5, 8 ]</code> or <code class="code">[ 7, 3, 9, 2, 5, 8 ]</code> are possible results.</p>
<p><a id="X87287FCA81E2B06A" name="X87287FCA81E2B06A"></a></p>
<h5>21.18-3 Sortex</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Sortex</code>( <var class="Arg">list</var>[, <var class="Arg">func</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>sorts the list <var class="Arg">list</var> and returns a permutation that can be applied to <var class="Arg">list</var> to obtain the sorted list. The one argument form sorts via the operator <code class="code"><</code>, the two argument form sorts w.r.t. the function <var class="Arg">func</var>. (If the list is not homogeneous it is the user's responsibility to ensure that <code class="code"><</code> is defined for all element pairs, see <a href="chap31.html#X7B3BC7BA7BB2646D"><span class="RefLink">31.11</span></a>)</p>
<p><code class="func">Permuted</code> (<a href="chap21.html#X7B5A19098406347A"><span class="RefLink">21.20-18</span></a>) allows you to rearrange a list according to a given permutation.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">list1 := [ 5, 4, 6, 1, 7, 5 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">list2 := ShallowCopy( list1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">perm := Sortex( list1 );</span>
(1,3,5,6,4)
<span class="GAPprompt">gap></span> <span class="GAPinput">list1;</span>
[ 1, 4, 5, 5, 6, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Permuted( list2, perm );</span>
[ 1, 4, 5, 5, 6, 7 ]
</pre></div>
<p><a id="X800209E881E7CECB" name="X800209E881E7CECB"></a></p>
<h5>21.18-4 SortingPerm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SortingPerm</code>( <var class="Arg">list</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">SortingPerm</code> returns the same as <code class="func">Sortex</code> (<a href="chap21.html#X87287FCA81E2B06A"><span class="RefLink">21.18-3</span></a>) but does <em>not</em> change the argument.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">list1 := [ 5, 4, 6, 1, 7, 5 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">list2 := ShallowCopy( list1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">perm := SortingPerm( list1 );</span>
(1,3,5,6,4)
<span class="GAPprompt">gap></span> <span class="GAPinput">list1;</span>
[ 5, 4, 6, 1, 7, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Permuted( list2, perm );</span>
[ 1, 4, 5, 5, 6, 7 ]
</pre></div>
<p>The default methods for all of these sorting operations currently use Shell sort as it has a comparable performance to Quicksort for lists of length at most a few thousands, and has better worst-case behaviour.</p>
<p><a id="X80ABC25582343910" name="X80ABC25582343910"></a></p>
<h4>21.19 <span class="Heading">Sorted Lists and Sets</span></h4>
<p>Searching objects in a list works much quicker if the list is known to be sorted. Currently <strong class="pkg">GAP</strong> exploits the sortedness of a list automatically only if the list is <em>strictly sorted</em>, which is indicated by the property <code class="func">IsSSortedList</code> (<a href="chap21.html#X80CDAF45782E8DCB"><span class="RefLink">21.17-4</span></a>).</p>
<p>Remember that a list of <em>mutable</em> objects cannot store that it is strictly sorted but has to test it anew whenever it is asked whether it is sorted, see the remark in <a href="chap21.html#X7865747A7CCF5812"><span class="RefLink">21.17</span></a>. Therefore <strong class="pkg">GAP</strong> cannot take advantage of the sortedness of a list if this list has mutable entries. Moreover, if a sorted list <var class="Arg">list</var> with mutable elements is used as an argument of a function that <em>expects</em> this argument to be sorted, for example <code class="func">UniteSet</code> (<a href="chap21.html#X7B3469CD7EFC1A87"><span class="RefLink">21.19-6</span></a>) or <code class="func">RemoveSet</code> (<a href="chap21.html#X7FCA282E789A4F4B"><span class="RefLink">21.19-5</span></a>), then it is checked whether <var class="Arg">list</var> is in fact sorted; this check can have the effect actually to slow down the computations, compared to computations with sorted lists of immutable elements or computations that do not involve functions that do automatically check sortedness.</p>
<p>Strictly sorted lists are used to represent <em>sets</em> in <strong class="pkg">GAP</strong>. More precisely, a strictly sorted list is called a <em>proper set</em> in the following, in order to avoid confusion with domains (see <a href="chap12.html#X7BAF69417BB925F6"><span class="RefLink">12.4</span></a>) which also represent sets.</p>
<p>In short proper sets are represented by sorted lists without holes and duplicates in <strong class="pkg">GAP</strong>. Note that we guarantee this representation, so you may make use of the fact that a set is represented by a sorted list in your functions.</p>
<p>In some contexts (for example see <a href="chap16.html#X7BDA99EE7CEADA7C"><span class="RefLink">16</span></a>), we also want to talk about multisets. A <em>multiset</em> is like a set, except that an element may appear several times in a multiset. Such multisets are represented by sorted lists without holes that may have duplicates.</p>
<p>This section lists only those functions that are defined exclusively for proper sets. Set theoretic functions for general collections, such as <code class="func">Intersection</code> (<a href="chap30.html#X851069107CACF98E"><span class="RefLink">30.5-2</span></a>) and <code class="func">Union</code> (<a href="chap30.html#X799F0E2F7A502DBA"><span class="RefLink">30.5-3</span></a>), are described in Chapter <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a>. In particular, for the construction of proper sets, see <code class="func">SSortedList</code> (<a href="chap30.html#X7E399AC97FD98217"><span class="RefLink">30.3-7</span></a>) and <code class="func">AsSSortedList</code> (<a href="chap30.html#X856D927378C33548"><span class="RefLink">30.3-10</span></a>). For finding positions in sorted lists, see <code class="func">PositionSorted</code> (<a href="chap21.html#X7A122E848464E534"><span class="RefLink">21.16-5</span></a>).</p>
<p>There are nondestructive counterparts of the functions <code class="func">UniteSet</code> (<a href="chap21.html#X7B3469CD7EFC1A87"><span class="RefLink">21.19-6</span></a>), <code class="func">IntersectSet</code> (<a href="chap21.html#X8473AA657FEC3D4D"><span class="RefLink">21.19-7</span></a>), and <code class="func">SubtractSet</code> (<a href="chap21.html#X80B427537EB07D09"><span class="RefLink">21.19-8</span></a>) available for proper sets. These are <code class="code">UnionSet</code>, <code class="code">IntersectionSet</code>, and <code class="func">Difference</code> (<a href="chap30.html#X825AC0F07E010B07"><span class="RefLink">30.5-4</span></a>). The former two are methods for the more general operations <code class="func">Union</code> (<a href="chap30.html#X799F0E2F7A502DBA"><span class="RefLink">30.5-3</span></a>) and <code class="func">Intersection</code> (<a href="chap30.html#X851069107CACF98E"><span class="RefLink">30.5-2</span></a>), the latter is itself an operation (see <code class="func">Difference</code> (<a href="chap30.html#X825AC0F07E010B07"><span class="RefLink">30.5-4</span></a>)).</p>
<p>The result of <code class="code">IntersectionSet</code> and <code class="code">UnionSet</code> is always a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the first argument <var class="Arg">set</var>. If <var class="Arg">set</var> is not a proper set it is not specified to which of a number of equal elements in <var class="Arg">set</var> the element in the result is identical (see <a href="chap21.html#X7DD65BEA7EDB0CD7"><span class="RefLink">21.6</span></a>). The following functions, if not explicitly stated differently, take two arguments, <var class="Arg">set</var> and <var class="Arg">obj</var>, where <var class="Arg">set</var> must be a proper set, otherwise an error is signalled; If the second argument <var class="Arg">obj</var> is a list that is not a proper set then <code class="func">Set</code> (<a href="chap30.html#X7E399AC97FD98217"><span class="RefLink">30.3-7</span></a>) is silently applied to it first.</p>
<p><a id="X7B16AD597CB12305" name="X7B16AD597CB12305"></a></p>
<h5>21.19-1 \in</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \in</code>( <var class="Arg">obj</var>, <var class="Arg">list</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>For a list <var class="Arg">list</var> that stores that it is strictly sorted, the test with <code class="func">\in</code> whether the object <var class="Arg">obj</var> is an entry of <var class="Arg">list</var> uses binary search. This test can be entered also with the infix notation <var class="Arg">obj</var> <code class="keyw">in</code> <var class="Arg">list</var>.</p>
<p><a id="X7B4C0FEE7CDF6F2A" name="X7B4C0FEE7CDF6F2A"></a></p>
<h5>21.19-2 IsEqualSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEqualSet</code>( <var class="Arg">list1</var>, <var class="Arg">list2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>tests whether <var class="Arg">list1</var> and <var class="Arg">list2</var> are equal <em>when viewed as sets</em>, that is if every element of <var class="Arg">list1</var> is an element of <var class="Arg">list2</var> and vice versa. Either argument of <code class="func">IsEqualSet</code> may also be a list that is not a proper set, in which case <code class="func">Set</code> (<a href="chap30.html#X7E399AC97FD98217"><span class="RefLink">30.3-7</span></a>) is applied to it first.</p>
<p>If both lists are proper sets then they are of course equal if and only if they are also equal as lists. Thus <code class="code">IsEqualSet( <var class="Arg">list1</var>, <var class="Arg">list2</var> )</code> is equivalent to <code class="code">Set( <var class="Arg">list1</var> ) = Set( <var class="Arg">list2</var> )</code> (see <code class="func">Set</code> (<a href="chap30.html#X7E399AC97FD98217"><span class="RefLink">30.3-7</span></a>)), but the former is more efficient.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEqualSet( [2,3,5,7,11], [11,7,5,3,2] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEqualSet( [2,3,5,7,11], [2,3,5,7,11,13] );</span>
false
</pre></div>
<p><a id="X79B940567A849216" name="X79B940567A849216"></a></p>
<h5>21.19-3 IsSubsetSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubsetSet</code>( <var class="Arg">list1</var>, <var class="Arg">list2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>tests whether every element of <var class="Arg">list2</var> is contained in <var class="Arg">list1</var>. Either argument of <code class="func">IsSubsetSet</code> may also be a list that is not a proper set, in which case <code class="func">Set</code> (<a href="chap30.html#X7E399AC97FD98217"><span class="RefLink">30.3-7</span></a>) is applied to it first.</p>
<p><a id="X832C23CC7FCD8892" name="X832C23CC7FCD8892"></a></p>
<h5>21.19-4 AddSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AddSet</code>( <var class="Arg">set</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>adds the element <var class="Arg">obj</var> to the proper set <var class="Arg">set</var>. If <var class="Arg">obj</var> is already contained in <var class="Arg">set</var> then <var class="Arg">set</var> is not changed. Otherwise <var class="Arg">obj</var> is inserted at the correct position such that <var class="Arg">set</var> is again a proper set afterwards.</p>
<p>Note that <var class="Arg">obj</var> must be in the same family as each element of <var class="Arg">set</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s := [2,3,7,11];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AddSet( s, 5 ); s;</span>
[ 2, 3, 5, 7, 11 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AddSet( s, 13 ); s;</span>
[ 2, 3, 5, 7, 11, 13 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AddSet( s, 3 ); s;</span>
[ 2, 3, 5, 7, 11, 13 ]
</pre></div>
<p><a id="X7FCA282E789A4F4B" name="X7FCA282E789A4F4B"></a></p>
<h5>21.19-5 RemoveSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RemoveSet</code>( <var class="Arg">set</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>removes the element <var class="Arg">obj</var> from the proper set <var class="Arg">set</var>. If <var class="Arg">obj</var> is not contained in <var class="Arg">set</var> then <var class="Arg">set</var> is not changed. If <var class="Arg">obj</var> is an element of <var class="Arg">set</var> it is removed and all the following elements in the list are moved one position forward.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s := [ 2, 3, 4, 5, 6, 7 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RemoveSet( s, 6 ); s;</span>
[ 2, 3, 4, 5, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RemoveSet( s, 10 ); s;</span>
[ 2, 3, 4, 5, 7 ]
</pre></div>
<p><a id="X7B3469CD7EFC1A87" name="X7B3469CD7EFC1A87"></a></p>
<h5>21.19-6 UniteSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UniteSet</code>( <var class="Arg">set</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>unites the proper set <var class="Arg">set</var> with <var class="Arg">list</var>. This is equivalent to adding all elements of <var class="Arg">list</var> to <var class="Arg">set</var> (see <code class="func">AddSet</code> (<a href="chap21.html#X832C23CC7FCD8892"><span class="RefLink">21.19-4</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">set := [ 2, 3, 5, 7, 11 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">UniteSet( set, [ 4, 8, 9 ] ); set;</span>
[ 2, 3, 4, 5, 7, 8, 9, 11 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">UniteSet( set, [ 16, 9, 25, 13, 16 ] ); set;</span>
[ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 25 ]
</pre></div>
<p><a id="X8473AA657FEC3D4D" name="X8473AA657FEC3D4D"></a></p>
<h5>21.19-7 IntersectSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IntersectSet</code>( <var class="Arg">set</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>intersects the proper set <var class="Arg">set</var> with <var class="Arg">list</var>. This is equivalent to removing from <var class="Arg">set</var> all elements of <var class="Arg">set</var> that are not contained in <var class="Arg">list</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">set := [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IntersectSet( set, [ 3, 5, 7, 9, 11, 13, 15, 17 ] ); set;</span>
[ 3, 5, 7, 9, 11, 13 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IntersectSet( set, [ 9, 4, 6, 8 ] ); set;</span>
[ 9 ]
</pre></div>
<p><a id="X80B427537EB07D09" name="X80B427537EB07D09"></a></p>
<h5>21.19-8 SubtractSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubtractSet</code>( <var class="Arg">set</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>subtracts <var class="Arg">list</var> from the proper set <var class="Arg">set</var>. This is equivalent to removing from <var class="Arg">set</var> all elements of <var class="Arg">list</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">set := [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SubtractSet( set, [ 6, 10 ] ); set;</span>
[ 2, 3, 4, 5, 7, 8, 9, 11 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SubtractSet( set, [ 9, 4, 6, 8 ] ); set;</span>
[ 2, 3, 5, 7, 11 ]
</pre></div>
<p><a id="X7DF510F7848CBBFD" name="X7DF510F7848CBBFD"></a></p>
<h4>21.20 <span class="Heading">Operations for Lists</span></h4>
<p>Several of the following functions expect the first argument to be either a list or a collection (see <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a>), with possibly slightly different meaning for lists and non-list collections.</p>
<p><a id="X840C55A77D1BB2E1" name="X840C55A77D1BB2E1"></a></p>
<h5>21.20-1 Concatenation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Concatenation</code>( <var class="Arg">list1</var>, <var class="Arg">list2</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">‣ Concatenation</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form <code class="func">Concatenation</code> returns the concatenation of the lists <var class="Arg">list1</var>, <var class="Arg">list2</var>, etc. The <em>concatenation</em> is the list that begins with the elements of <var class="Arg">list1</var>, followed by the elements of <var class="Arg">list2</var>, and so on. Each list may also contain holes, in which case the concatenation also contains holes at the corresponding positions.</p>
<p>In the second form <var class="Arg">list</var> must be a dense list of lists <var class="Arg">list1</var>, <var class="Arg">list2</var>, etc., and <code class="func">Concatenation</code> returns the concatenation of those lists.</p>
<p>The result is a new mutable list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of <var class="Arg">list1</var>, <var class="Arg">list2</var>, etc. (see <a href="chap21.html#X7DD65BEA7EDB0CD7"><span class="RefLink">21.6</span></a>).</p>
<p>Note that <code class="func">Concatenation</code> creates a new list and leaves its arguments unchanged, while <code class="func">Append</code> (<a href="chap21.html#X79E31DB27C82D6E1"><span class="RefLink">21.4-5</span></a>) changes its first argument. For computing the union of proper sets, <code class="func">Union</code> (<a href="chap30.html#X799F0E2F7A502DBA"><span class="RefLink">30.5-3</span></a>) can be used, see also <a href="chap21.html#X80ABC25582343910"><span class="RefLink">21.19</span></a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Concatenation( [ 1, 2, 3 ], [ 4, 5 ] );</span>
[ 1, 2, 3, 4, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Concatenation( [2,3,,5,,7], [11,,13,,,,17,,19] );</span>
[ 2, 3,, 5,, 7, 11,, 13,,,, 17,, 19 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Concatenation( [ [1,2,3], [2,3,4], [3,4,5] ] );</span>
[ 1, 2, 3, 2, 3, 4, 3, 4, 5 ]
</pre></div>
<p><a id="X7CB0A6AF87C7FAF7" name="X7CB0A6AF87C7FAF7"></a></p>
<h5>21.20-2 Compacted</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Compacted</code>( <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns a new mutable list that contains the elements of <var class="Arg">list</var> in the same order but omitting the holes.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:=[,1,,,3,,,4,[5,,,6],7];; Compacted( l );</span>
[ 1, 3, 4, [ 5,,, 6 ], 7 ]
</pre></div>
<p><a id="X7ECE9056792F28BA" name="X7ECE9056792F28BA"></a></p>
<h5>21.20-3 Collected</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Collected</code>( <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns a new list <var class="Arg">new</var> that contains for each element <var class="Arg">elm</var> of the list <var class="Arg">list</var> a list of length two, the first element of this is <var class="Arg">elm</var> itself and the second element is the number of times <var class="Arg">elm</var> appears in <var class="Arg">list</var>. The order of those pairs in <var class="Arg">new</var> corresponds to the ordering of the elements elm, so that the result is sorted.</p>
<p>For all pairs of elements in <var class="Arg">list</var> the comparison via <code class="code"><</code> must be defined.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Factors( Factorial( 10 ) );</span>
[ 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Collected( last );</span>
[ [ 2, 8 ], [ 3, 4 ], [ 5, 2 ], [ 7, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Collected( last );</span>
[ [ [ 2, 8 ], 1 ], [ [ 3, 4 ], 1 ], [ [ 5, 2 ], 1 ], [ [ 7, 1 ], 1 ] ]
</pre></div>
<p><a id="X8727F2928467C2F9" name="X8727F2928467C2F9"></a></p>
<h5>21.20-4 DuplicateFreeList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DuplicateFreeList</code>( <var class="Arg">list</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">‣ Unique</code>( <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns a new mutable list whose entries are the elements of the list <var class="Arg">list</var> with duplicates removed. <code class="func">DuplicateFreeList</code> only uses the <code class="code">=</code> comparison and will not sort the result. Therefore <code class="func">DuplicateFreeList</code> can be used even if the elements of <var class="Arg">list</var> do not lie in the same family. Otherwise, if <var class="Arg">list</var> contains objects that can be compared with <code class="func">\<</code> (<a href="chap31.html#X7EF67D047F03CA6F"><span class="RefLink">31.11-1</span></a>) then it is much more efficient to use <code class="func">Set</code> (<a href="chap30.html#X7E399AC97FD98217"><span class="RefLink">30.3-7</span></a>) instead of <code class="func">DuplicateFreeList</code>.</p>
<p><code class="func">Unique</code> is a synonym for <code class="func">DuplicateFreeList</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:=[1,Z(3),1,"abc",Group((1,2,3),(1,2)),Z(3),Group((1,2),(2,3))];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DuplicateFreeList( l );</span>
[ 1, Z(3), "abc", Group([ (1,2,3), (1,2) ]) ]
</pre></div>
<p><a id="X7F5D4DD87E4378AC" name="X7F5D4DD87E4378AC"></a></p>
<h5>21.20-5 AsDuplicateFreeList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsDuplicateFreeList</code>( <var class="Arg">list</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the same result as <code class="func">DuplicateFreeList</code> (<a href="chap21.html#X8727F2928467C2F9"><span class="RefLink">21.20-4</span></a>), except that the result is immutable.</p>
<p><a id="X7FA272D984EF82ED" name="X7FA272D984EF82ED"></a></p>
<h5>21.20-6 Flat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Flat</code>( <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the list of all elements that are contained in the list <var class="Arg">list</var> or its sublists. That is, <code class="func">Flat</code> first makes a new empty list <var class="Arg">new</var>. Then it loops over the elements <var class="Arg">elm</var> of <var class="Arg">list</var>. If <var class="Arg">elm</var> is not a list it is added to <var class="Arg">new</var>, otherwise <code class="func">Flat</code> appends <code class="code">Flat( <var class="Arg">elm</var> )</code> to <var class="Arg">new</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Flat( [ 1, [ 2, 3 ], [ [ 1, 2 ], 3 ] ] );</span>
[ 1, 2, 3, 1, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Flat( [ ] );</span>
[ ]
</pre></div>
<p>To reconstruct a matrix from the list obtained by applying <code class="func">Flat</code> to the matrix, the sublist operator can be used, as follows.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:=[9..14];;w:=2;; # w is the length of each row</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">sub:=[1..w];;List([1..Length(l)/w],i->l{(i-1)*w+sub});</span>
[ [ 9, 10 ], [ 11, 12 ], [ 13, 14 ] ]
</pre></div>
<p><a id="X7C4FDB007C3F54A1" name="X7C4FDB007C3F54A1"></a></p>
<h5>21.20-7 Reversed</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Reversed</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a new mutable list, containing the elements of the dense list <var class="Arg">list</var> in reversed order.</p>
<p>The argument list is unchanged. The result list is a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the argument list (see <a href="chap21.html#X7DD65BEA7EDB0CD7"><span class="RefLink">21.6</span></a>).</p>
<p><code class="func">Reversed</code> implements a special case of list assignment, which can also be formulated in terms of the <code class="code">{}</code> operator (see <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Reversed( [ 1, 4, 9, 5, 6, 7 ] );</span>
[ 7, 6, 5, 9, 4, 1 ]
</pre></div>
<p><a id="X8057372F83374193" name="X8057372F83374193"></a></p>
<h5>21.20-8 Shuffle</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Shuffle</code>( <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The argument <var class="Arg">list</var> must be a dense mutable list. This operation permutes the entries of <var class="Arg">list</var> randomly (in place), and returns <var class="Arg">list</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Reset(GlobalMersenneTwister, 12345);; # make manual tester happy</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [1..20];</span>
[ 1 .. 20 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">m := Shuffle(ShallowCopy(l));</span>
[ 15, 13, 3, 19, 8, 11, 14, 7, 16, 4, 17, 18, 5, 1, 10, 6, 2, 9, 12,
20 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l;</span>
[ 1 .. 20 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Shuffle(l);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">l;</span>
[ 3, 4, 18, 13, 10, 7, 9, 8, 14, 17, 16, 6, 19, 12, 1, 11, 20, 2, 15,
5 ]
</pre></div>
<p><a id="X7BA5EF2181DD78D7" name="X7BA5EF2181DD78D7"></a></p>
<h5>21.20-9 IsLexicographicallyLess</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLexicographicallyLess</code>( <var class="Arg">list1</var>, <var class="Arg">list2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">list1</var> and <var class="Arg">list2</var> be two dense, but not necessarily homogeneous lists (see <code class="func">IsDenseList</code> (<a href="chap21.html#X870AA9D8798C93DD"><span class="RefLink">21.1-2</span></a>), <code class="func">IsHomogeneousList</code> (<a href="chap21.html#X7C71596C82B6EF35"><span class="RefLink">21.1-3</span></a>)), such that for each <span class="SimpleMath">i</span>, the entries in both lists at position <span class="SimpleMath">i</span> can be compared via <code class="code"><</code>. <code class="func">IsLexicographicallyLess</code> returns <code class="keyw">true</code> if <var class="Arg">list1</var> is smaller than <var class="Arg">list2</var> w.r.t. lexicographical ordering, and <code class="keyw">false</code> otherwise.</p>
<p><a id="X8075FBDE7B81B4C8" name="X8075FBDE7B81B4C8"></a></p>
<h5>21.20-10 Apply</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Apply</code>( <var class="Arg">list</var>, <var class="Arg">func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">Apply</code> applies the function <var class="Arg">func</var> to every element of the dense and mutable list <var class="Arg">list</var>, and replaces each element entry by the corresponding return value.</p>
<p><code class="func">Apply</code> changes its argument. The nondestructive counterpart of <code class="func">Apply</code> is <code class="func">List</code> (<a href="chap30.html#X7F12F40E87F3C3A7"><span class="RefLink">30.3-5</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= [ 1, 2, 3 ];; Apply( l, i -> i^2 ); l;</span>
[ 1, 4, 9 ]
</pre></div>
<p><a id="X7EF6E2BC81DBF6FB" name="X7EF6E2BC81DBF6FB"></a></p>
<h5>21.20-11 Perform</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Perform</code>( <var class="Arg">list</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">Perform</code> applies the function <var class="Arg">func</var> to every element of the list <var class="Arg">list</var>, discarding any return values. It does not return a value.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := [1, 2, 3];; Perform(l, </span>
<span class="GAPprompt">></span> <span class="GAPinput">function(x) if IsPrimeInt(x) then Print(x,"\n"); fi; end);</span>
2
3
</pre></div>
<p><a id="X8763882A7D65F979" name="X8763882A7D65F979"></a></p>
<h5>21.20-12 PermListList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermListList</code>( <var class="Arg">list1</var>, <var class="Arg">list2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a permutation <span class="SimpleMath">p</span> of <code class="code">[ 1 .. Length( <var class="Arg">list1</var> ) ]</code> such that <var class="Arg">list1</var><span class="SimpleMath">[i</span><code class="code">^</code><span class="SimpleMath">p] =</span> <var class="Arg">list2</var><span class="SimpleMath">[i]</span>. It returns <code class="keyw">fail</code> if there is no such permutation.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">list1 := [ 5, 4, 6, 1, 7, 5 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">list2 := [ 4, 1, 7, 5, 5, 6 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">perm := PermListList(list1, list2);</span>
(1,2,4)(3,5,6)
<span class="GAPprompt">gap></span> <span class="GAPinput">Permuted( list2, perm );</span>
[ 5, 4, 6, 1, 7, 5 ]
</pre></div>
<p><a id="X82CE0DE8828E4303" name="X82CE0DE8828E4303"></a></p>
<h5>21.20-13 <span class="Heading">Maximum</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Maximum</code>( <var class="Arg">obj1</var>, <var class="Arg">obj2</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">‣ Maximum</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form <code class="func">Maximum</code> returns the <em>maximum</em> of its arguments, i.e., one argument <var class="Arg">obj</var> for which <span class="SimpleMath"><var class="Arg">obj</var> ≥ <var class="Arg">obj1</var></span>, <span class="SimpleMath"><var class="Arg">obj</var> ≥ <var class="Arg">obj2</var></span> etc.</p>
<p>In the second form <code class="func">Maximum</code> takes a homogeneous list <var class="Arg">list</var> and returns the maximum of the elements in this list.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Maximum( -123, 700, 123, 0, -1000 );</span>
700
<span class="GAPprompt">gap></span> <span class="GAPinput">Maximum( [ -123, 700, 123, 0, -1000 ] );</span>
700
<span class="GAPprompt">gap></span> <span class="GAPinput"># lists are compared elementwise:</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Maximum( [1,2], [0,15], [1,5], [2,-11] ); </span>
[ 2, -11 ]
</pre></div>
<p><a id="X82F133EC7F89665F" name="X82F133EC7F89665F"></a></p>
<h5>21.20-14 <span class="Heading">Minimum</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Minimum</code>( <var class="Arg">obj1</var>, <var class="Arg">obj2</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">‣ Minimum</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form <code class="func">Minimum</code> returns the <em>minimum</em> of its arguments, i.e., one argument <var class="Arg">obj</var> for which <span class="SimpleMath"><var class="Arg">obj</var> ≤ <var class="Arg">obj1</var></span>, <span class="SimpleMath"><var class="Arg">obj</var> ≤ <var class="Arg">obj2</var></span> etc.</p>
<p>In the second form <code class="func">Minimum</code> takes a homogeneous list <var class="Arg">list</var> and returns the minimum of the elements in this list.</p>
<p>Note that for both <code class="func">Maximum</code> (<a href="chap21.html#X82CE0DE8828E4303"><span class="RefLink">21.20-13</span></a>) and <code class="func">Minimum</code> the comparison of the objects <var class="Arg">obj1</var>, <var class="Arg">obj2</var> etc. must be defined; for that, usually they must lie in the same family (see <a href="chap13.html#X846063757EC05986"><span class="RefLink">13.1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Minimum( -123, 700, 123, 0, -1000 );</span>
-1000
<span class="GAPprompt">gap></span> <span class="GAPinput">Minimum( [ -123, 700, 123, 0, -1000 ] );</span>
-1000
<span class="GAPprompt">gap></span> <span class="GAPinput">Minimum( [ 1, 2 ], [ 0, 15 ], [ 1, 5 ], [ 2, -11 ] );</span>
[ 0, 15 ]
</pre></div>
<p><a id="X842851EB7E0969F7" name="X842851EB7E0969F7"></a></p>
<h5>21.20-15 <span class="Heading">MaximumList and MinimumList</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MaximumList</code>( <var class="Arg">list</var>[, <var class="Arg">seed</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">‣ MinimumList</code>( <var class="Arg">list</var>[, <var class="Arg">seed</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>return the maximum resp. the minimum of the elements in the list <var class="Arg">list</var>. They are the operations called by <code class="func">Maximum</code> (<a href="chap21.html#X82CE0DE8828E4303"><span class="RefLink">21.20-13</span></a>) resp. <code class="func">Minimum</code> (<a href="chap21.html#X82F133EC7F89665F"><span class="RefLink">21.20-14</span></a>). Methods can be installed for special kinds of lists. For example, there are special methods to compute the maximum resp. the minimum of a range (see <a href="chap21.html#X79596BDE7CAF8491"><span class="RefLink">21.22</span></a>).</p>
<p>If a second argument <var class="Arg">seed</var> is supplied, then the result is the maximum resp. minimum of the union of <var class="Arg">list</var> and <var class="Arg">seed</var>. In this manner, the operations may be applied to empty lists.</p>
<p><a id="X7E1593B979BDF2CD" name="X7E1593B979BDF2CD"></a></p>
<h5>21.20-16 <span class="Heading">Cartesian</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Cartesian</code>( <var class="Arg">list1</var>, <var class="Arg">list2</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">‣ Cartesian</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form <code class="func">Cartesian</code> returns the cartesian product of the lists <var class="Arg">list1</var>, <var class="Arg">list2</var>, etc.</p>
<p>In the second form <var class="Arg">list</var> must be a list of lists <var class="Arg">list1</var>, <var class="Arg">list2</var>, etc., and <code class="func">Cartesian</code> returns the cartesian product of those lists.</p>
<p>The <em>cartesian product</em> is a list <var class="Arg">cart</var> of lists <var class="Arg">tup</var>, such that the first element of <var class="Arg">tup</var> is an element of <var class="Arg">list1</var>, the second element of <var class="Arg">tup</var> is an element of <var class="Arg">list2</var>, and so on. The total number of elements in <var class="Arg">cart</var> is the product of the lengths of the argument lists. In particular <var class="Arg">cart</var> is empty if and only if at least one of the argument lists is empty. Also <var class="Arg">cart</var> contains duplicates if and only if no argument list is empty and at least one contains duplicates.</p>
<p>The last index runs fastest. That means that the first element <var class="Arg">tup1</var> of <var class="Arg">cart</var> contains the first element from <var class="Arg">list1</var>, from <var class="Arg">list2</var> and so on. The second element <var class="Arg">tup2</var> of <var class="Arg">cart</var> contains the first element from <var class="Arg">list1</var>, the first from <var class="Arg">list2</var>, an so on, but the last element of <var class="Arg">tup2</var> is the second element of the last argument list. This implies that <var class="Arg">cart</var> is a proper set if and only if all argument lists are proper sets (see <a href="chap21.html#X80ABC25582343910"><span class="RefLink">21.19</span></a>).</p>
<p>The function <code class="func">Tuples</code> (<a href="chap16.html#X86A3CA0F7CC8C320"><span class="RefLink">16.2-8</span></a>) computes the <var class="Arg">k</var>-fold cartesian product of a list.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Cartesian( [1,2], [3,4], [5,6] );</span>
[ [ 1, 3, 5 ], [ 1, 3, 6 ], [ 1, 4, 5 ], [ 1, 4, 6 ], [ 2, 3, 5 ],
[ 2, 3, 6 ], [ 2, 4, 5 ], [ 2, 4, 6 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Cartesian( [1,2,2], [1,1,2] );</span>
[ [ 1, 1 ], [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 1 ], [ 2, 2 ],
[ 2, 1 ], [ 2, 1 ], [ 2, 2 ] ]
</pre></div>
<p><a id="X7E76F5A782184823" name="X7E76F5A782184823"></a></p>
<h5>21.20-17 <span class="Heading">IteratorOfCartesianProduct</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IteratorOfCartesianProduct</code>( <var class="Arg">list1</var>, <var class="Arg">list2</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">‣ IteratorOfCartesianProduct</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form <code class="func">IteratorOfCartesianProduct</code> returns an iterator (see <a href="chap30.html#X85A3F00985453F95"><span class="RefLink">30.8</span></a>) of all elements of the cartesian product (see <code class="func">Cartesian</code> (<a href="chap21.html#X7E1593B979BDF2CD"><span class="RefLink">21.20-16</span></a>)) of the lists <var class="Arg">list1</var>, <var class="Arg">list2</var>, etc.</p>
<p>In the second form <var class="Arg">list</var> must be a list of lists <var class="Arg">list1</var>, <var class="Arg">list2</var>, etc., and <code class="func">IteratorOfCartesianProduct</code> returns an iterator of the cartesian product of those lists.</p>
<p>Resulting tuples will be returned in the lexicographic order. Usage of iterators of cartesian products is recommended in the case when the resulting cartesian product is big enough, so its generating and storage will require essential amount of runtime and memory. For smaller cartesian products it is faster to generate the full set of tuples using <code class="func">Cartesian</code> (<a href="chap21.html#X7E1593B979BDF2CD"><span class="RefLink">21.20-16</span></a>) and then loop over its elements (with some minor overhead of needing more memory).</p>
<p><a id="X7B5A19098406347A" name="X7B5A19098406347A"></a></p>
<h5>21.20-18 Permuted</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Permuted</code>( <var class="Arg">list</var>, <var class="Arg">perm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns a new list <var class="Arg">new</var> that contains the elements of the list <var class="Arg">list</var> permuted according to the permutation <var class="Arg">perm</var>. That is <code class="code"><var class="Arg">new</var>[<var class="Arg">i</var>^<var class="Arg">perm</var>] = <var class="Arg">list</var>[<var class="Arg">i</var>]</code>.</p>
<p><code class="func">Sortex</code> (<a href="chap21.html#X87287FCA81E2B06A"><span class="RefLink">21.18-3</span></a>) allows you to compute a permutation that must be applied to a list in order to get the sorted list.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Permuted( [ 5, 4, 6, 1, 7, 5 ], (1,3,5,6,4) );</span>
[ 1, 4, 5, 5, 6, 7 ]
</pre></div>
<p><a id="X86CB7DCE8510F977" name="X86CB7DCE8510F977"></a></p>
<h5>21.20-19 List</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ List</code>( <var class="Arg">list</var>[, <var class="Arg">func</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function returns a new mutable list <code class="code">new</code> of the same length as the list <var class="Arg">list</var> (which may have holes). The entry <code class="code">new[i]</code> is unbound if <code class="code"><var class="Arg">list</var>[i]</code> is unbound. Otherwise <code class="code">new[i] = <var class="Arg">func</var>(<var class="Arg">list</var>[i])</code>. If the argument <var class="Arg">func</var> is omitted, its default is <code class="func">IdFunc</code> (<a href="chap5.html#X810325697BDEF899"><span class="RefLink">5.3-4</span></a>), so this function does the same as <code class="func">ShallowCopy</code> (<a href="chap12.html#X846BC7107C352031"><span class="RefLink">12.7-1</span></a>) (see also <a href="chap21.html#X7ED7C0738495556F"><span class="RefLink">21.7</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List( [1,2,3], i -> i^2 );</span>
[ 1, 4, 9 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List( [1..10], IsPrime );</span>
[ false, true, true, false, true, false, true, false, false, false ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List([,1,,3,4], x-> x > 2);</span>
[ , false,, true, true ]
</pre></div>
<p>(See also <code class="func">List</code> (<a href="chap30.html#X7F12F40E87F3C3A7"><span class="RefLink">30.3-5</span></a>).)</p>
<p><a id="X7C86D7F7795125F0" name="X7C86D7F7795125F0"></a></p>
<h5>21.20-20 Filtered</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Filtered</code>( <var class="Arg">listorcoll</var>, <var class="Arg">func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a new list that contains those elements of the list or collection <var class="Arg">listorcoll</var> (see <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a>), respectively, for which the unary function <var class="Arg">func</var> returns <code class="keyw">true</code>.</p>
<p>If the first argument is a list, the order of the elements in the result is the same as the order of the corresponding elements of this list. If an element for which <var class="Arg">func</var> returns <code class="keyw">true</code> appears several times in the list it will also appear the same number of times in the result. The argument list may contain holes, they are ignored by <code class="func">Filtered</code>.</p>
<p>For each element of <var class="Arg">listorcoll</var>, <var class="Arg">func</var> must return either <code class="keyw">true</code> or <code class="keyw">false</code>, otherwise an error is signalled.</p>
<p>The result is a new list that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the argument list (see <a href="chap21.html#X7DD65BEA7EDB0CD7"><span class="RefLink">21.6</span></a>).</p>
<p>List assignment using the operator <code class="func">\{\}</code> (<a href="chap21.html#X78791B8B838A8BA0"><span class="RefLink">21.3-1</span></a>) (see <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>) can be used to extract elements of a list according to indices given in another list.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered( [1..20], IsPrime );</span>
[ 2, 3, 5, 7, 11, 13, 17, 19 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered( [ 1, 3, 4, -4, 4, 7, 10, 6 ], IsPrimePowerInt );</span>
[ 3, 4, 4, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered( [ 1, 3, 4, -4, 4, 7, 10, 6 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> n -> IsPrimePowerInt(n) and n mod 2 <> 0 );</span>
[ 3, 7 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered( Group( (1,2), (1,2,3) ), x -> Order( x ) = 2 );</span>
[ (2,3), (1,2), (1,3) ]
</pre></div>
<p><a id="X8179B13D80E935FC" name="X8179B13D80E935FC"></a></p>
<h5>21.20-21 Number</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Number</code>( <var class="Arg">listorcoll</var>[, <var class="Arg">func</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Called with a list <var class="Arg">listorcoll</var>, <code class="func">Number</code> returns the number of bound entries in this list. For dense lists <code class="func">Number</code>, <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>), and <code class="func">Size</code> (<a href="chap30.html#X858ADA3B7A684421"><span class="RefLink">30.4-6</span></a>) return the same value; for lists with holes <code class="func">Number</code> returns the number of bound entries, <code class="func">Length</code> (<a href="chap21.html#X780769238600AFD1"><span class="RefLink">21.17-5</span></a>) returns the largest index of a bound entry, and <code class="func">Size</code> (<a href="chap30.html#X858ADA3B7A684421"><span class="RefLink">30.4-6</span></a>) signals an error.</p>
<p>Called with two arguments, a list or collection <var class="Arg">listorcoll</var> and a unary function <var class="Arg">func</var>, <code class="func">Number</code> returns the number of elements of <var class="Arg">listorcoll</var> for which <var class="Arg">func</var> returns <code class="keyw">true</code>. If an element for which <var class="Arg">func</var> returns <code class="keyw">true</code> appears several times in <var class="Arg">listorcoll</var> it will also be counted the same number of times.</p>
<p>For each element of <var class="Arg">listorcoll</var>, <var class="Arg">func</var> must return either <code class="keyw">true</code> or <code class="keyw">false</code>, otherwise an error is signalled.</p>
<p><code class="func">Filtered</code> (<a href="chap21.html#X7C86D7F7795125F0"><span class="RefLink">21.20-20</span></a>) allows you to extract the elements of a list that have a certain property.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Number( [ 2, 3, 5, 7 ] );</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">Number( [, 2, 3,, 5,, 7,,,, 11 ] );</span>
5
<span class="GAPprompt">gap></span> <span class="GAPinput">Number( [1..20], IsPrime );</span>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">Number( [ 1, 3, 4, -4, 4, 7, 10, 6 ], IsPrimePowerInt );</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">Number( [ 1, 3, 4, -4, 4, 7, 10, 6 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> n -> IsPrimePowerInt(n) and n mod 2 <> 0 );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">Number( Group( (1,2), (1,2,3) ), x -> Order( x ) = 2 );</span>
3
</pre></div>
<p><a id="X82801DFA84E11272" name="X82801DFA84E11272"></a></p>
<h5>21.20-22 First</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ First</code>( <var class="Arg">list</var>, <var class="Arg">func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">First</code> returns the first element of the list <var class="Arg">list</var> for which the unary function <var class="Arg">func</var> returns <code class="keyw">true</code>. <var class="Arg">list</var> may contain holes. <var class="Arg">func</var> must return either <code class="keyw">true</code> or <code class="keyw">false</code> for each element of <var class="Arg">list</var>, otherwise an error is signalled. If <var class="Arg">func</var> returns <code class="keyw">false</code> for all elements of <var class="Arg">list</var> then <code class="func">First</code> returns <code class="keyw">fail</code>.</p>
<p><code class="func">PositionProperty</code> (<a href="chap21.html#X7E6C763A82C6153B"><span class="RefLink">21.16-7</span></a>) allows you to find the position of the first element in a list that satisfies a certain property.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">First( [10^7..10^8], IsPrime );</span>
10000019
<span class="GAPprompt">gap></span> <span class="GAPinput">First( [10^5..10^6],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> n -> not IsPrime(n) and IsPrimePowerInt(n) );</span>
100489
<span class="GAPprompt">gap></span> <span class="GAPinput">First( [ 1 .. 20 ], x -> x < 0 );</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">First( [ fail ], x -> x = fail );</span>
fail
</pre></div>
<p><a id="X7F06961278166671" name="X7F06961278166671"></a></p>
<h5>21.20-23 ForAll</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ForAll</code>( <var class="Arg">listorcoll</var>, <var class="Arg">func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>tests whether the unary function <var class="Arg">func</var> returns <code class="keyw">true</code> for all elements in the list or collection <var class="Arg">listorcoll</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll( [1..20], IsPrime );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll( [2,3,4,5,8,9], IsPrimePowerInt );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll( [2..14], n -> IsPrimePowerInt(n) or n mod 2 = 0 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll( Group( (1,2), (1,2,3) ), i -> SignPerm(i) = 1 );</span>
false
</pre></div>
<p><a id="X7AF82E747A8BDA75" name="X7AF82E747A8BDA75"></a></p>
<h5>21.20-24 ForAny</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ForAny</code>( <var class="Arg">listorcoll</var>, <var class="Arg">func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>tests whether the unary function <var class="Arg">func</var> returns <code class="keyw">true</code> for at least one element in the list or collection <var class="Arg">listorcoll</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAny( [1..20], IsPrime );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAny( [2,3,4,5,8,9], IsPrimePowerInt );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAny( [2..14],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> n -> IsPrimePowerInt(n) and n mod 5 = 0 and not IsPrime(n) );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAny( Integers, i -> i > 0</span>
<span class="GAPprompt">></span> <span class="GAPinput"> and ForAll( [0,2..4], j -> IsPrime(i+j) ) );</span>
true
</pre></div>
<p><a id="X7E5C72F27B657948" name="X7E5C72F27B657948"></a></p>
<h5>21.20-25 Product</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Product</code>( <var class="Arg">listorcoll</var>[, <var class="Arg">func</var>][, <var class="Arg">init</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Called with one argument, a dense list or collection <var class="Arg">listorcoll</var>, <code class="func">Product</code> returns the product of the elements of <var class="Arg">listorcoll</var> (see <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a>).</p>
<p>Called with a dense list or collection <var class="Arg">listorcoll</var> and a function <var class="Arg">func</var>, which must be a function taking one argument, <code class="func">Product</code> applies the function <var class="Arg">func</var> to the elements of <var class="Arg">listorcoll</var>, and returns the product of the results. In either case <code class="func">Product</code> returns <code class="code">1</code> if the first argument is empty.</p>
<p>The general rules for arithmetic operations apply (see <a href="chap21.html#X8676EFE67972FD06"><span class="RefLink">21.15</span></a>), so the result is immutable if and only if all summands are immutable.</p>
<p>If <var class="Arg">listorcoll</var> contains exactly one element then this element (or its image under <var class="Arg">func</var> if applicable) itself is returned, not a shallow copy of this element.</p>
<p>If an additional initial value <var class="Arg">init</var> is given, <code class="func">Product</code> returns the product of <var class="Arg">init</var> and the elements of the first argument resp. of their images under the function <var class="Arg">func</var>. This is useful for example if the first argument is empty and a different identity than <code class="code">1</code> is desired, in which case <var class="Arg">init</var> is returned.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Product( [ 2, 3, 5, 7, 11, 13, 17, 19 ] );</span>
9699690
<span class="GAPprompt">gap></span> <span class="GAPinput">Product( [1..10], x->x^2 );</span>
13168189440000
<span class="GAPprompt">gap></span> <span class="GAPinput">Product( [ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) ] );</span>
(1,4)(2,3)
<span class="GAPprompt">gap></span> <span class="GAPinput">Product( GF(8) );</span>
0*Z(2)
</pre></div>
<p><a id="X7A04B71C84CFCC2D" name="X7A04B71C84CFCC2D"></a></p>
<h5>21.20-26 Sum</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Sum</code>( <var class="Arg">listorcoll</var>[, <var class="Arg">func</var>][, <var class="Arg">init</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Called with one argument, a dense list or collection <var class="Arg">listorcoll</var>, <code class="func">Sum</code> returns the sum of the elements of <var class="Arg">listorcoll</var> (see <a href="chap30.html#X8050A8037984E5B6"><span class="RefLink">30</span></a>).</p>
<p>Called with a dense list or collection <var class="Arg">listorcoll</var> and a function <var class="Arg">func</var>, which must be a function taking one argument, <code class="func">Sum</code> applies the function <var class="Arg">func</var> to the elements of <var class="Arg">listorcoll</var>, and returns the sum of the results. In either case <code class="func">Sum</code> returns <code class="code">0</code> if the first argument is empty.</p>
<p>The general rules for arithmetic operations apply (see <a href="chap21.html#X8676EFE67972FD06"><span class="RefLink">21.15</span></a>), so the result is immutable if and only if all summands are immutable.</p>
<p>If <var class="Arg">listorcoll</var> contains exactly one element then this element (or its image under <var class="Arg">func</var> if applicable) itself is returned, not a shallow copy of this element.</p>
<p>If an additional initial value <var class="Arg">init</var> is given, <code class="func">Sum</code> returns the sum of <var class="Arg">init</var> and the elements of the first argument resp. of their images under the function <var class="Arg">func</var>. This is useful for example if the first argument is empty and a different zero than <code class="code">0</code> is desired, in which case <var class="Arg">init</var> is returned.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Sum( [ 2, 3, 5, 7, 11, 13, 17, 19 ] );</span>
77
<span class="GAPprompt">gap></span> <span class="GAPinput">Sum( [1..10], x->x^2 );</span>
385
<span class="GAPprompt">gap></span> <span class="GAPinput">Sum( [ [1,2], [3,4], [5,6] ] );</span>
[ 9, 12 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Sum( GF(8) );</span>
0*Z(2)
</pre></div>
<p><a id="X834E4DF57F3A20F0" name="X834E4DF57F3A20F0"></a></p>
<h5>21.20-27 Iterated</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Iterated</code>( <var class="Arg">list</var>, <var class="Arg">f</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the result of the iterated application of the function <var class="Arg">f</var>, which must take two arguments, to the elements of the list <var class="Arg">list</var>. More precisely, if <var class="Arg">list</var> has length <span class="SimpleMath">n</span> then <code class="func">Iterated</code> returns the result of the following application, <span class="SimpleMath"><var class="Arg">f</var>( ... <var class="Arg">f</var>( <var class="Arg">f</var>( <var class="Arg">list</var>[1], <var class="Arg">list</var>[2] ), <var class="Arg">list</var>[3] ), ..., <var class="Arg">list</var>[n] )</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Iterated( [ 126, 66, 105 ], Gcd );</span>
3
</pre></div>
<p><a id="X7D150C2881881139" name="X7D150C2881881139"></a></p>
<h5>21.20-28 ListN</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ListN</code>( <var class="Arg">list1</var>, <var class="Arg">list2</var>, <var class="Arg">...</var>, <var class="Arg">listn</var>, <var class="Arg">f</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>applies the <span class="SimpleMath">n</span>-argument function <var class="Arg">f</var> to the lists. That is, <code class="func">ListN</code> returns the list whose <span class="SimpleMath">i</span>-th entry is <span class="SimpleMath"><var class="Arg">f</var>(<var class="Arg">list1</var>[i], <var class="Arg">list2</var>[i], ..., <var class="Arg">listn</var>[i])</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ListN( [1,2], [3,4], \+ );</span>
[ 4, 6 ]
</pre></div>
<p><a id="X805CA0B68029B47A" name="X805CA0B68029B47A"></a></p>
<h4>21.21 <span class="Heading">Advanced List Manipulations</span></h4>
<p>The following functions are generalizations of <code class="func">List</code> (<a href="chap30.html#X7F12F40E87F3C3A7"><span class="RefLink">30.3-5</span></a>), <code class="func">Set</code> (<a href="chap30.html#X7E399AC97FD98217"><span class="RefLink">30.3-7</span></a>), <code class="func">Sum</code> (<a href="chap21.html#X7A04B71C84CFCC2D"><span class="RefLink">21.20-26</span></a>), and <code class="func">Product</code> (<a href="chap21.html#X7E5C72F27B657948"><span class="RefLink">21.20-25</span></a>).</p>
<p><a id="X8258477D7F72171B" name="X8258477D7F72171B"></a></p>
<h5>21.21-1 ListX</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ListX</code>( <var class="Arg">arg1</var>, <var class="Arg">arg2</var>, <var class="Arg">...</var>, <var class="Arg">argn</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">ListX</code> returns a new list constructed from the arguments.</p>
<p>Each of the arguments <var class="Arg">arg1</var>, <var class="Arg">arg2</var>, <span class="SimpleMath">...</span> <var class="Arg">argn</var> must be one of the following:</p>
<dl>
<dt><strong class="Mark">a list or collection</strong></dt>
<dd><p>this introduces a new for-loop in the sequence of nested for-loops and if-statements;</p>
</dd>
<dt><strong class="Mark">a function returning a list or collection</strong></dt>
<dd><p>this introduces a new for-loop in the sequence of nested for-loops and if-statements, where the loop-range depends on the values of the outer loop-variables; or</p>
</dd>
<dt><strong class="Mark">a function returning <code class="keyw">true</code> or <code class="keyw">false</code></strong></dt>
<dd><p>this introduces a new if-statement in the sequence of nested for-loops and if-statements.</p>
</dd>
</dl>
<p>The last argument <var class="Arg">func</var> must be a function, it is applied to the values of the loop-variables and the results are collected.</p>
<p>Thus <code class="code">ListX( <var class="Arg">list</var>, <var class="Arg">func</var> )</code> is the same as <code class="code">List( <var class="Arg">list</var>, <var class="Arg">func</var> )</code>, and <code class="code">ListX( <var class="Arg">list</var>, <var class="Arg">func</var>, x -> x )</code> is the same as <code class="code">Filtered( <var class="Arg">list</var>, <var class="Arg">func</var> )</code>.</p>
<p>As a more elaborate example, assume <var class="Arg">arg1</var> is a list or collection, <var class="Arg">arg2</var> is a function returning <code class="keyw">true</code> or <code class="keyw">false</code>, <var class="Arg">arg3</var> is a function returning a list or collection, and <var class="Arg">arg4</var> is another function returning <code class="keyw">true</code> or <code class="keyw">false</code>, then</p>
<p><code class="code"><var class="Arg">result</var> := ListX( <var class="Arg">arg1</var>, <var class="Arg">arg2</var>, <var class="Arg">arg3</var>, <var class="Arg">arg4</var>, <var class="Arg">func</var> );</code></p>
<p>is equivalent to</p>
<div class="example"><pre>
result := [];
for v1 in arg1 do
if arg2( v1 ) then
for v2 in arg3( v1 ) do
if arg4( v1, v2 ) then
Add( result, func( v1, v2 ) );
fi;
od;
fi;
od;
</pre></div>
<p>The following example shows how <code class="func">ListX</code> can be used to compute all pairs and all strictly sorted pairs of elements in a list.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= [ 1, 2, 3, 4 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair:= function( x, y ) return [ x, y ]; end;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ListX( l, l, pair );</span>
[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 2 ],
[ 2, 3 ], [ 2, 4 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ], [ 3, 4 ],
[ 4, 1 ], [ 4, 2 ], [ 4, 3 ], [ 4, 4 ] ]
</pre></div>
<p>In the following example, <code class="func">\<</code> (<a href="chap31.html#X7EF67D047F03CA6F"><span class="RefLink">31.11-1</span></a>) is the comparison operation:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ListX( l, l, \<, pair );</span>
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
</pre></div>
<p><a id="X7AC321B87A2DCAF5" name="X7AC321B87A2DCAF5"></a></p>
<h5>21.21-2 SetX</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetX</code>( <var class="Arg">arg1</var>, <var class="Arg">arg2</var>, <var class="Arg">...</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The only difference between <code class="func">SetX</code> and <code class="func">ListX</code> (<a href="chap21.html#X8258477D7F72171B"><span class="RefLink">21.21-1</span></a>) is that the result list of <code class="func">SetX</code> is strictly sorted.</p>
<p><a id="X82B1411E7FBE925F" name="X82B1411E7FBE925F"></a></p>
<h5>21.21-3 SumX</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SumX</code>( <var class="Arg">arg1</var>, <var class="Arg">arg2</var>, <var class="Arg">...</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">SumX</code> returns the sum of the elements in the list obtained by <code class="func">ListX</code> (<a href="chap21.html#X8258477D7F72171B"><span class="RefLink">21.21-1</span></a>) when this is called with the same arguments.</p>
<p><a id="X7FB318B47D8783DA" name="X7FB318B47D8783DA"></a></p>
<h5>21.21-4 ProductX</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ProductX</code>( <var class="Arg">arg1</var>, <var class="Arg">arg2</var>, <var class="Arg">...</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">ProductX</code> returns the product of the elements in the list obtained by <code class="func">ListX</code> (<a href="chap21.html#X8258477D7F72171B"><span class="RefLink">21.21-1</span></a>) when this is called with the same arguments.</p>
<p><a id="X79596BDE7CAF8491" name="X79596BDE7CAF8491"></a></p>
<h4>21.22 <span class="Heading">Ranges</span></h4>
<p>A <em>range</em> is a dense list of integers in arithmetic progression (or degression). This is a list of integers such that the difference between consecutive elements is a nonzero constant. Ranges can be abbreviated with the syntactic construct</p>
<p><code class="code">[ <var class="Arg">first</var>, <var class="Arg">second</var> .. <var class="Arg">last</var> ]</code></p>
<p>or, if the difference between consecutive elements is 1, as</p>
<p><code class="code">[ <var class="Arg">first</var> .. <var class="Arg">last</var> ]</code>.</p>
<p>If <code class="code"><var class="Arg">first</var> > <var class="Arg">last</var></code>, <code class="code">[ <var class="Arg">first</var> .. <var class="Arg">last</var> ]</code> is the empty list, which by definition is also a range; also, if <code class="code"><var class="Arg">second</var> > <var class="Arg">first</var> > <var class="Arg">last</var></code> or <code class="code"><var class="Arg">second</var> < <var class="Arg">first</var> < <var class="Arg">last</var></code>, then <code class="code">[ <var class="Arg">first</var>, <var class="Arg">second</var> .. <var class="Arg">last</var> ]</code> is the empty list. If <code class="code"><var class="Arg">first</var> = <var class="Arg">last</var></code>, <code class="code">[ <var class="Arg">first</var>, <var class="Arg">second</var> .. <var class="Arg">last</var> ]</code> is a singleton list, which is a range, too. Note that <code class="code"><var class="Arg">last</var> - <var class="Arg">first</var></code> must be divisible by the increment <code class="code"><var class="Arg">second</var> - <var class="Arg">first</var></code>, otherwise an error is signalled.</p>
<p>Currently, the integers <var class="Arg">first</var>, <var class="Arg">second</var> and <var class="Arg">last</var> and the length of a range must be small integers, that is at least <span class="SimpleMath">-2^d</span> and at most <span class="SimpleMath">2^d - 1</span> with <span class="SimpleMath">d = 28</span> on 32-bit architectures and <span class="SimpleMath">d = 60</span> on 64-bit architectures.</p>
<p>Note also that a range is just a special case of a list. Thus you can access elements in a range (see <a href="chap21.html#X7921047F83F5FA28"><span class="RefLink">21.3</span></a>), test for membership etc. You can even assign to such a range if it is mutable (see <a href="chap21.html#X8611EF768210625B"><span class="RefLink">21.4</span></a>). Of course, unless you assign <code class="code"><var class="Arg">last</var> + <var class="Arg">second</var> - <var class="Arg">first</var></code> to the entry <code class="code"><var class="Arg">range</var>[ Length( <var class="Arg">range</var> ) + 1 ]</code>, the resulting list will no longer be a range.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">r := [10..20];</span>
[ 10 .. 20 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Length( r );</span>
11
<span class="GAPprompt">gap></span> <span class="GAPinput">r[3];</span>
12
<span class="GAPprompt">gap></span> <span class="GAPinput">17 in r;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">r[12] := 25;; r; # r is no longer a range</span>
[ 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 25 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">r := [1,3..17];</span>
[ 1, 3 .. 17 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Length( r );</span>
9
<span class="GAPprompt">gap></span> <span class="GAPinput">r[4];</span>
7
<span class="GAPprompt">gap></span> <span class="GAPinput">r := [0,-1..-9];</span>
[ 0, -1 .. -9 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">r[5];</span>
-4
<span class="GAPprompt">gap></span> <span class="GAPinput">r := [ 1, 4 .. 32 ];</span>
Error, Range: <last>-<first> (31) must be divisible by <inc> (3)
</pre></div>
<p>Most often ranges are used in connection with the <code class="keyw">for</code>-loop see <a href="chap4.html#X78783E777867638A"><span class="RefLink">4.20</span></a>). Here the construct</p>
<p><code class="code">for <var class="Arg">var</var> in [ <var class="Arg">first</var> .. <var class="Arg">last</var> ] do <var class="Arg">statements</var> od</code></p>
<p>replaces the</p>
<p><code class="code">for <var class="Arg">var</var> from <var class="Arg">first</var> to <var class="Arg">last</var> do <var class="Arg">statements</var> od</code></p>
<p>which is more usual in other programming languages.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s := [];; for i in [10..20] do Add( s, i^2 ); od; s;</span>
[ 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400 ]
</pre></div>
<p>Note that a range with <code class="code"><var class="Arg">last</var> >= <var class="Arg">first</var></code> is at the same time also a proper set (see <a href="chap21.html#X80ABC25582343910"><span class="RefLink">21.19</span></a>), because it contains no holes or duplicates and is sorted, and also a row vector (see <a href="chap23.html#X82C7E6CF7BA03391"><span class="RefLink">23</span></a>), because it contains no holes and all elements are integers.</p>
<p><a id="X86DDC2FF7A50FBEE" name="X86DDC2FF7A50FBEE"></a></p>
<h5>21.22-1 IsRange</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRange</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>tests if the object <var class="Arg">obj</var> is a range, i.e. is a dense list of integers that is also a range (see <a href="chap21.html#X79596BDE7CAF8491"><span class="RefLink">21.22</span></a> for a definition of "range").</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRange( [1,2,3] ); IsRange( [7,5,3,1] );</span>
true
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRange( [1,2,4,5] ); IsRange( [1,,3,,5,,7] );</span>
false
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRange( [] ); IsRange( [1] );</span>
true
true
</pre></div>
<p><a id="X7D22B2298167A58F" name="X7D22B2298167A58F"></a></p>
<h5>21.22-2 ConvertToRangeRep</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ConvertToRangeRep</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For some lists the <strong class="pkg">GAP</strong> kernel knows that they are in fact ranges. Those lists are represented internally in a compact way instead of the ordinary way.</p>
<p>If <var class="Arg">list</var> is a range then <code class="func">ConvertToRangeRep</code> changes the representation of <var class="Arg">list</var> to this compact representation.</p>
<p>This is important since this representation needs only 12 bytes for the entire range while the ordinary representation needs <span class="SimpleMath">4 length</span> bytes.</p>
<p>Note that a list that is represented in the ordinary way might still be a range. It is just that <strong class="pkg">GAP</strong> does not know this. The following rules tell you under which circumstances a range is represented in the compact way, so you can write your program in such a way that you make best use of this compact representation for ranges.</p>
<p>Lists created by the syntactic construct <code class="code">[ <var class="Arg">first</var>, <var class="Arg">second</var> .. <var class="Arg">last</var> ]</code> are of course known to be ranges and are represented in the compact way.</p>
<p>If you call <code class="func">ConvertToRangeRep</code> for a list represented the ordinary way that is indeed a range, the representation is changed from the ordinary to the compact representation. A call of <code class="func">ConvertToRangeRep</code> for a list that is not a range is ignored.</p>
<p>If you change a mutable range that is represented in the compact way, by assignment, <code class="func">Add</code> (<a href="chap21.html#X795EC9D67E34DAB0"><span class="RefLink">21.4-2</span></a>) or <code class="func">Append</code> (<a href="chap21.html#X79E31DB27C82D6E1"><span class="RefLink">21.4-5</span></a>), the range will be converted to the ordinary representation, even if the change is such that the resulting list is still a proper range.</p>
<p>Suppose you have built a proper range in such a way that it is represented in the ordinary way and that you now want to convert it to the compact representation to save space. Then you should call <code class="func">ConvertToRangeRep</code> with that list as an argument. You can think of the call to <code class="func">ConvertToRangeRep</code> as a hint to <strong class="pkg">GAP</strong> that this list is a proper range.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">r:= [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];</span>
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ConvertToRangeRep( r ); r;</span>
[ 1 .. 10 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= [ 1, 2, 4, 5 ];; ConvertToRangeRep( l ); l;</span>
[ 1, 2, 4, 5 ]
</pre></div>
<p><a id="X7EA3ACE27E43D174" name="X7EA3ACE27E43D174"></a></p>
<h4>21.23 <span class="Heading">Enumerators</span></h4>
<p>An <em>enumerator</em> is an immutable list that need not store its elements explicitly but knows, from a set of basic data, how to determine the <span class="SimpleMath">i</span>-th element and the position of a given object. A typical example of this is a vector space over a finite field with <span class="SimpleMath">q</span> elements, say, for which it is very easy to enumerate all elements using <span class="SimpleMath">q</span>-adic expansions of integers.</p>
<p>Using this enumeration can be even quicker than a binary search in a sorted list of vectors, see <code class="func">IsQuickPositionList</code> (<a href="chap21.html#X7BB462C17962647F"><span class="RefLink">21.23-1</span></a>).</p>
<p>On the one hand, element access to an enumerator may take more time than element access to an internally represented list containing the same elements. On the other hand, an enumerator may save a vast amount of memory. Take for example a permutation group of size a few millions. Even for moderate degree it is unlikely that a list of all its elements will fit into memory whereas it is no problem to construct an enumerator from a stabilizer chain (see <a href="chap43.html#X7FA58C3A8283F3BD"><span class="RefLink">43.6</span></a>).</p>
<p>There are situations where one only wants to loop over the elements of a domain, without using the special facilities of an enumerator, namely the particular order of elements and the possibility to find the position of elements. For such cases, <strong class="pkg">GAP</strong> provides iterators (see <a href="chap30.html#X85A3F00985453F95"><span class="RefLink">30.8</span></a>).</p>
<p>The functions <code class="func">Enumerator</code> (<a href="chap30.html#X7EF8910F82B45EC7"><span class="RefLink">30.3-2</span></a>) and <code class="func">EnumeratorSorted</code> (<a href="chap30.html#X80CD7DDC7D0C60D5"><span class="RefLink">30.3-3</span></a>) return enumerators of domains. Most of the special implementations of enumerators in the <strong class="pkg">GAP</strong> library are based on the general interface that is provided by <code class="func">EnumeratorByFunctions</code> (<a href="chap30.html#X85E149177AC547C3"><span class="RefLink">30.3-4</span></a>); one generic example is <code class="func">EnumeratorByBasis</code> (<a href="chap61.html#X7EB0D16A7EC2DEE3"><span class="RefLink">61.6-5</span></a>), which can be used to get an enumerator of a finite dimensional free module.</p>
<p>Also enumerators for non-domains can be implemented via <code class="func">EnumeratorByFunctions</code> (<a href="chap30.html#X85E149177AC547C3"><span class="RefLink">30.3-4</span></a>); for a discussion, see <a href="chap79.html#X849D8BC278649EA5"><span class="RefLink">79.12</span></a>.</p>
<p><a id="X7BB462C17962647F" name="X7BB462C17962647F"></a></p>
<h5>21.23-1 IsQuickPositionList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsQuickPositionList</code>( <var class="Arg">list</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>This filter indicates that a position test in <var class="Arg">list</var> is quicker than about 5 or 6 element comparisons for "smaller". If this is the case it can be beneficial to use <code class="func">Position</code> (<a href="chap21.html#X79975EC6783B4293"><span class="RefLink">21.16-1</span></a>) in <var class="Arg">list</var> and a bit list than ordered lists to represent subsets of <var class="Arg">list</var>.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap20.html">[Previous Chapter]</a> <a href="chap22.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><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>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
|