Pairs-and-lists.html (29641B)
1 <html lang="en"> 2 <head> 3 <title>Pairs and lists - klisp Reference Manual</title> 4 <meta http-equiv="Content-Type" content="text/html"> 5 <meta name="description" content="klisp Reference Manual"> 6 <meta name="generator" content="makeinfo 4.13"> 7 <link title="Top" rel="start" href="index.html#Top"> 8 <link rel="prev" href="Control.html#Control" title="Control"> 9 <link rel="next" href="Environments.html#Environments" title="Environments"> 10 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage"> 11 <meta http-equiv="Content-Style-Type" content="text/css"> 12 <style type="text/css"><!-- 13 pre.display { font-family:inherit } 14 pre.format { font-family:inherit } 15 pre.smalldisplay { font-family:inherit; font-size:smaller } 16 pre.smallformat { font-family:inherit; font-size:smaller } 17 pre.smallexample { font-size:smaller } 18 pre.smalllisp { font-size:smaller } 19 span.sc { font-variant:small-caps } 20 span.roman { font-family:serif; font-weight:normal; } 21 span.sansserif { font-family:sans-serif; font-weight:normal; } 22 --></style> 23 <link rel="stylesheet" type="text/css" href="css/style.css"> 24 </head> 25 <body> 26 <div class="node"> 27 <a name="Pairs-and-lists"></a> 28 <p> 29 Next: <a rel="next" accesskey="n" href="Environments.html#Environments">Environments</a>, 30 Previous: <a rel="previous" accesskey="p" href="Control.html#Control">Control</a>, 31 Up: <a rel="up" accesskey="u" href="index.html#Top">Top</a> 32 <hr> 33 </div> 34 35 <!-- node-name, next, previous, up --> 36 <h2 class="chapter">7 Pairs and lists</h2> 37 38 <p><a name="index-pairs-39"></a><a name="index-nil-40"></a><a name="index-empty-list-41"></a><a name="index-lists-42"></a> 39 A pair is an object that refers to two other objects, called its car 40 and cdr. The Kernel data type pair is encapsulated. 41 42 <p>The null data type consists of a single immutable value, called nil 43 or the empty list and having external representation <code>()</code>, with 44 or without whitespace between the parentheses. It is immutable, and 45 the null type is encapsulated. 46 47 <p>If <code>a</code> and <code>d</code> are external representations of 48 respectively the car and cdr of a pair <code>p</code>, then <code>(a . d)</code> 49 is an external representation of <code>p</code>. If the cdr of <code>p</code> is 50 nil, then <code>(a)</code> is also an external representation of 51 <code>p</code>. If the cdr of <code>p</code> is a pair <code>p2</code>, and <code>(r)</code> 52 is an external representation of <code>p2</code>, then <code>(a r)</code> is an 53 external representation of <code>p</code>. 54 <!-- add xref for write --> 55 When a pair is output (as by write), an external representation with 56 the fewest parentheses is used; in the case of a finite list, only one 57 set of parentheses is required beyond those used in representing the 58 elements of the list. For example, an object with external 59 representation <code>(1 . (2 . (3 . ())))</code> would be output using, 60 modulo whitespace, external representation <code>(1 2 3)</code>. 61 62 <div class="defun"> 63 — Applicative: <b>pair?</b> (<var>pair? . objects</var>)<var><a name="index-pair_003f-43"></a></var><br> 64 <blockquote><p> The primitive type predicate for type pair. <code>pair?</code> returns 65 true iff all the objects in <code>objects</code> are of type pair. 66 </p></blockquote></div> 67 68 <div class="defun"> 69 — Applicative: <b>null?</b> (<var>null? . objects</var>)<var><a name="index-null_003f-44"></a></var><br> 70 <blockquote><p> The primitive type predicate for type null. <code>null?</code> returns 71 true iff all the objects in <code>objects</code> are of type null. 72 </p></blockquote></div> 73 74 <div class="defun"> 75 — Applicative: <b>immutable-pair?</b> (<var>immutable-pair? objects</var>)<var><a name="index-immutable_002dpair_003f-45"></a></var><br> 76 — Applicative: <b>mutable-pair?</b> (<var>mutable-pair? objects</var>)<var><a name="index-mutable_002dpair_003f-46"></a></var><br> 77 <blockquote><p>The primitive type predicates for types immutable pair and mutable 78 pair. These return true iff all the objects in <code>objects</code> are of 79 type immutable pair or mutable pair respectively. 80 81 <p>SOURCE NOTE: these aren't provided in the Kernel report, but added for 82 convenience. These can be implemented in standard kernel by using guards. 83 </p></blockquote></div> 84 85 <div class="defun"> 86 — Applicative: <b>cons</b> (<var>cons object1 object2</var>)<var><a name="index-cons-47"></a></var><br> 87 <blockquote><p> A new mutable pair object is constructed and returned, whose car and 88 cdr referents are respectively <code>object1</code> and <code>object2</code>. No 89 two objects returned by different calls to cons are <code>eq?</code> to each 90 other. 91 </p></blockquote></div> 92 93 <div class="defun"> 94 — Applicative: <b>set-car!</b> (<var>set-car! pair object</var>)<var><a name="index-set_002dcar_0021-48"></a></var><br> 95 — Applicative: <b>set-cdr!</b> (<var>set-cdr! pair object</var>)<var><a name="index-set_002dcdr_0021-49"></a></var><br> 96 <blockquote><p> <code>pair</code> should be a mutable pair. 97 98 <p>These applicatives set the referent of, respectively, the car 99 reference or the cdr reference of <code>pair</code> to <code>object</code>. The 100 result of the expression is inert. 101 </p></blockquote></div> 102 103 <div class="defun"> 104 — Applicative: <b>copy-es-immutable!</b> (<var>copy-es-immutable object</var>)<var><a name="index-copy_002des_002dimmutable_0021-50"></a></var><br> 105 <blockquote><p> The short description of this applicative is that it returns an object 106 <code>equal?</code> to <code>object</code> with an immutable evaluation structure. The 107 “-es-” in the name is short for “evaluation structure”. 108 109 <!-- TODO move the evaluation structure description to the intro --> 110 <p>The evaluation structure of an object <code>o</code> is defined to be the 111 set of all pairs that can be reached by following chains of references 112 from <code>o</code> without ever passing through a non-pair object. The 113 evaluation structure of a non-pair object is empty. 114 115 <p>If <code>object</code> is not a pair, the applicative returns <code>object</code>. 116 Otherwise (if <code>object</code> is a pair), the applicative returns an 117 immutable pair whose car and cdr would be suitable results for 118 <code>(copy-es-immutable (car object))</code> and <code>(copy-es-immutable 119 (cdr object))</code>, respectively. Further, the evaluation structure of 120 <!-- TODO add xref for isomorphic (and add isomorphic to the intro) --> 121 the returned value is isomorphic to that of <code>object</code> at the time 122 of copying, with corresponding non-pair referents being <code>eq?</code>. 123 124 <p>NOTE: In Kernel it's undefined whether immutable pairs are copied or 125 left “as is” in the result. klisp doesn't copy immutable pairs, but 126 that behaviour should not be depended upon. 127 </p></blockquote></div> 128 129 <div class="defun"> 130 — Applicative: <b>list</b> (<var>list . objects</var>)<var><a name="index-list-51"></a></var><br> 131 <blockquote><p>The <code>list</code> applicative returns <code>objects</code>. 132 133 <p>The underlying operative of <code>list</code> returns its undifferentiated 134 operand tree, regardless of whether that tree is or is not a list. 135 </p></blockquote></div> 136 137 <div class="defun"> 138 — Applicative: <b>list*</b> (<var>list* . objects</var>)<var><a name="index-list_002a-52"></a></var><br> 139 <blockquote><p><code>objects</code> should be a finite nonempty list of arguments. 140 141 <p>The following equivalences hold: 142 <pre class="example"> (list* arg1) == arg1 143 (list* arg1 arg2 . args) == (cons arg1 (list* arg2 . args)) 144 </pre> 145 </blockquote></div> 146 147 <div class="defun"> 148 — Applicative: <b>car</b> (<var>car pair</var>)<var><a name="index-car-53"></a></var><br> 149 — Applicative: <b>cdr</b> (<var>cdr pair</var>)<var><a name="index-cdr-54"></a></var><br> 150 <blockquote><p>These applicatives return, respectively, the car and cdr of <code>pair</code>. 151 </p></blockquote></div> 152 153 <div class="defun"> 154 — Applicative: <b>caar</b> (<var>caar pair</var>)<var><a name="index-caar-55"></a></var><br> 155 — Applicative: <b>cadr</b> (<var>cadr pair</var>)<var><a name="index-cadr-56"></a></var><br> 156 — Applicative: <b>cdar</b> (<var>cdar pair</var>)<var><a name="index-cdar-57"></a></var><br> 157 — Applicative: <b>cddr</b> (<var>cddr pair</var>)<var><a name="index-cddr-58"></a></var><br> 158 — Applicative: <b>caaar</b> (<var>caaar pair</var>)<var><a name="index-caaar-59"></a></var><br> 159 — Applicative: <b>caadr</b> (<var>caadr pair</var>)<var><a name="index-caadr-60"></a></var><br> 160 — Applicative: <b>cadar</b> (<var>cadar pair</var>)<var><a name="index-cadar-61"></a></var><br> 161 — Applicative: <b>caddr</b> (<var>caddr pair</var>)<var><a name="index-caddr-62"></a></var><br> 162 — Applicative: <b>cdaar</b> (<var>cdaar pair</var>)<var><a name="index-cdaar-63"></a></var><br> 163 — Applicative: <b>cdadr</b> (<var>cdadr pair</var>)<var><a name="index-cdadr-64"></a></var><br> 164 — Applicative: <b>cddar</b> (<var>cddar pair</var>)<var><a name="index-cddar-65"></a></var><br> 165 — Applicative: <b>cdddr</b> (<var>cdddr pair</var>)<var><a name="index-cdddr-66"></a></var><br> 166 — Applicative: <b>caaaar</b> (<var>caaaar pair</var>)<var><a name="index-caaaar-67"></a></var><br> 167 — Applicative: <b>caaadr</b> (<var>caaadr pair</var>)<var><a name="index-caaadr-68"></a></var><br> 168 — Applicative: <b>caadar</b> (<var>caadar pair</var>)<var><a name="index-caadar-69"></a></var><br> 169 — Applicative: <b>caaddr</b> (<var>caaddr pair</var>)<var><a name="index-caaddr-70"></a></var><br> 170 — Applicative: <b>cadaar</b> (<var>cadaar pair</var>)<var><a name="index-cadaar-71"></a></var><br> 171 — Applicative: <b>cadadr</b> (<var>cadadr pair</var>)<var><a name="index-cadadr-72"></a></var><br> 172 — Applicative: <b>caddar</b> (<var>caddar pair</var>)<var><a name="index-caddar-73"></a></var><br> 173 — Applicative: <b>cadddr</b> (<var>cadddr pair</var>)<var><a name="index-cadddr-74"></a></var><br> 174 — Applicative: <b>cdaaar</b> (<var>cdaaar pair</var>)<var><a name="index-cdaaar-75"></a></var><br> 175 — Applicative: <b>cdaadr</b> (<var>cdaadr pair</var>)<var><a name="index-cdaadr-76"></a></var><br> 176 — Applicative: <b>cdadar</b> (<var>cdadar pair</var>)<var><a name="index-cdadar-77"></a></var><br> 177 — Applicative: <b>cdaddr</b> (<var>cdaddr pair</var>)<var><a name="index-cdaddr-78"></a></var><br> 178 — Applicative: <b>cddaar</b> (<var>cddaar pair</var>)<var><a name="index-cddaar-79"></a></var><br> 179 — Applicative: <b>cddadr</b> (<var>cddadr pair</var>)<var><a name="index-cddadr-80"></a></var><br> 180 — Applicative: <b>cdddar</b> (<var>cdddar pair</var>)<var><a name="index-cdddar-81"></a></var><br> 181 — Applicative: <b>cddddr</b> (<var>cddddr pair</var>)<var><a name="index-cddddr-82"></a></var><br> 182 <blockquote> 183 <!-- TODO add note about pronunciation --> 184 <p>These applicatives are compositions of <code>car</code> and <code>cdr</code>, with 185 the “a’s” and “d’s” in the same order as they would appear if all 186 the individual “car’s” and “cdr’s” were written out in prefix 187 order. Arbitrary compositions up to four deep are provided. There are 188 twenty-eight of these applicatives in all. 189 </p></blockquote></div> 190 191 <div class="defun"> 192 — Applicative: <b>make-list</b> (<var>make-list length </var>[<var>fill</var>])<var><a name="index-make_002dlist-83"></a></var><br> 193 <blockquote><p> <code>length</code> shoulde be an exact non-negative integer. 194 195 <p>Applicative <code>make-list</code> creates a new mutable acyclic list of 196 length <code>length</code>, with all pairs having <code>fill</code> in their 197 cars. If no value is provided for <code>fill</code>, <code>#inert</code> is used. 198 199 <p>SOURCE NOTE: this is taken from r7rs. 200 </p></blockquote></div> 201 202 <div class="defun"> 203 — Applicative: <b>list-copy</b> (<var>list-copy list</var>)<var><a name="index-list_002dcopy-84"></a></var><br> 204 <blockquote><p>Applicative <code>list-copy</code> creates a new mutable copy of 205 <code>list</code>. That is, the returned list has the same list metrics as 206 <code>list</code> and the cars in the returned list are initially <code>eq?</code> 207 to the corresponding cars in <code>list</code>. 208 209 <p>SOURCE NOTE: this is taken from r7rs. 210 </p></blockquote></div> 211 212 <div class="defun"> 213 — Applicative: <b>reverse</b> (<var>reverse list</var>)<var><a name="index-reverse-85"></a></var><br> 214 <blockquote><p><code>list</code> should be an acyclic list. 215 216 <p>Applicative <code>reverse</code> makes a mutable copy of list but with the 217 reverse order. That is, the returned list has the same number of 218 pairs as <code>list</code> and the cars in the returned list are initially 219 <code>eq?</code> to the corresponding cars in <code>list</code> but starting from 220 the end and going backwards. 221 222 <p>SOURCE NOTE: this is taken from r7rs. 223 </p></blockquote></div> 224 225 <div class="defun"> 226 — Applicative: <b>get-list-metrics</b> (<var>get-list-metrics object</var>)<var><a name="index-get_002dlist_002dmetrics-86"></a></var><br> 227 <blockquote><!-- TODO move definition of improper list to intro, xref data structure --> 228 <p>By definition, an improper list is a data structure whose objects 229 are its start together with all objects reachable from the start by 230 following the cdr references of pairs, and whose internal references 231 are just the cdr references of its pairs. Every object, of whatever 232 type, is the start of an improper list. If the start is not a pair, 233 the improper list consists of just that object. The acyclic prefix 234 length of an improper list <code>L</code> is the number of pairs of <code>L</code> 235 that a naive traversal of <code>L</code> would visit only once. The cycle 236 length of <code>L</code> is the number of pairs of <code>L</code> that a naive 237 traversal would visit repeatedly. Two improper lists are structurally 238 <!-- TODO add xref to isomorphic --> 239 isomorphic iff they have the same acyclic prefix length and cycle 240 length and, if they are terminated by non-pair objects rather than by 241 cycles, the non-pair objects have the same type. Applicative 242 <code>get-list-metrics</code> constructs and returns a list of exact 243 integers of the form <code>(p n a c)</code>, where <code>p</code>, <code>n</code>, 244 <code>a</code>, and <code>c</code> are, respectively, the number of pairs in, the 245 number of nil objects in, the acyclic prefix length of, and the cycle 246 length of, the improper list starting with <code>object</code>. <code>n</code> is 247 either <code>0</code> or <code>1</code>, <code>a + c = p</code>, and <code>n</code> and 248 <code>c</code> cannot both be non-zero. If <code>c = 0</code>, the improper list 249 is acyclic; if <code>n = 1</code>, the improper list is a finite list; if 250 <code>n = c = 0</code>, the improper list is not a list; if <code>a = c = 251 0</code>, <code>object</code> is not a pair. 252 </p></blockquote></div> 253 254 <div class="defun"> 255 — Applicative: <b>list-tail</b> (<var>list-tail object k</var>)<var><a name="index-list_002dtail-87"></a></var><br> 256 <blockquote><p><code>object</code> must be the start of an improper list containing at 257 least <code>k</code> pairs. 258 259 <p>The <code>list-tail</code> applicative follows <code>k</code> cdr references 260 starting from <code>object</code>. 261 262 <p>The following equivalences hold: 263 <pre class="example"> (list-tail object 0) == object 264 (list-tail object (+ k 1)) == (list-tail (cdr object) k) 265 </pre> 266 </blockquote></div> 267 268 <div class="defun"> 269 — Applicative: <b>encycle!</b> (<var>encycle! object k1 k2</var>)<var><a name="index-encycle_0021-88"></a></var><br> 270 <blockquote><p> The improper list starting at <code>object</code> must contain at least 271 <code>k1 + k2</code> pairs. 272 273 <p>If <code>k2 = 0</code>, the applicative does nothing. If <code>k2 > 0</code>, 274 the applicative mutates the improper list starting at <code>object</code> to 275 have acyclic prefix length <code>k1</code> and cycle length <code>k2</code>, by 276 setting the cdr of the <code>(k1+k2)</code>th pair in the list to refer to 277 the <code>(k1 + 1)</code>th pair in the list. The result returned by 278 <code>encycle!</code> is inert. 279 </p></blockquote></div> 280 281 <div class="defun"> 282 — Applicative: <b>map</b> (<var>map applicative . lists</var>)<var><a name="index-map-89"></a></var><br> 283 <blockquote><p> <code>lists</code> must be a nonempty list of lists; if there are two or 284 <!-- TODO add xref to length --> 285 more, they must all have the same length. 286 287 <p>The map applicative applies <code>applicative</code> element-wise to the 288 elements of the lists in lists (i.e., applies it to a list of the 289 first elements of the lists, to a list of the second elements of the 290 lists, etc.), using the dynamic environment from which map was called, 291 and returns a list of the results, in order. The applications may be 292 performed in any order, as long as their results occur in the 293 resultant list in the order of their arguments in the original lists. 294 If <code>lists</code> is a cyclic list, each argument list to which 295 <!-- TODO xref to ismorphic --> 296 <code>applicative</code> is applied is structurally isomorphic to <code>lists</code>. If 297 any of the elements of <code>lists</code> is a cyclic list, they all must 298 be, or they wouldn’t all have the same length. Let <code>a1...an</code> be 299 their acyclic prefix lengths, and <code>c1...cn</code> be their cycle 300 lengths. The acyclic prefix length <code>a</code> of the resultant list 301 will be the maximum of the <code>ak</code>, while the cycle length <code>c</code> 302 of the resultant list will be the least common multiple of the 303 <code>ck</code>. In the construction of the result, <code>applicative</code> is 304 called exactly <code>a + c</code> times. 305 </p></blockquote></div> 306 307 <div class="defun"> 308 — Applicative: <b>length</b> (<var>length object</var>)<var><a name="index-length-90"></a></var><br> 309 <blockquote><!-- TODO xref improper-list --> 310 <p>Applicative <code>length</code> returns the (exact) improper-list length 311 of <code>object</code>. That is, it returns the number of consecutive cdr 312 references that can be followed starting from <code>object</code>. If 313 <code>object</code> is not a pair, it returns zero; if <code>object</code> is a 314 cyclic list, it returns positive infinity. 315 </p></blockquote></div> 316 317 <div class="defun"> 318 — Applicative: <b>list-ref</b> (<var>list-ref object k</var>)<var><a name="index-list_002dref-91"></a></var><br> 319 <blockquote><p> The <code>list-ref</code> applicative returns the <code>car</code> of the object 320 obtained by following <code>k</code> cdr references starting from 321 <code>object</code>. 322 323 <p>NOTE: In the current report, object is required to be a list. In 324 klisp, for now, we prefer the behaviour presented here, as it is more 325 in line with the applicative <code>list-tail</code>. That is, we define 326 <code>list-ref</code> by the following equivalence: 327 <pre class="example"> (list-ref object k) == (car (list-tail object k)) 328 </pre> 329 </blockquote></div> 330 331 <div class="defun"> 332 — Applicative: <b>append</b> (<var>append . lists</var>)<var><a name="index-append-92"></a></var><br> 333 <blockquote><p> Here, all the elements of <code>lists</code> except the last element (if 334 any) must be acyclic lists. The <code>append</code> applicative returns a 335 freshly allocated list of the elements of all the specified 336 <code>lists</code>, in order, except that if there is a last specified 337 element of <code>lists</code>, it is not copied, but is simply referenced by 338 the cdr of the preceding pair (if any) in the resultant list. If 339 <code>lists</code> is cyclic, the cycle of the result list consists of just 340 the elements of the lists specified in the cycle in <code>lists</code>. In 341 this case, the acyclic prefix length of the result is the sum of the 342 lengths of the lists specified in the acyclic prefix of <code>lists</code>, 343 and the cycle length of the result is the sum of the lengths of the 344 lists specified in the cycle of <code>lists</code>. 345 346 <p>The following equivalences hold: 347 <pre class="example"> (append) == () 348 (append h) == h 349 (append () h . t) == (append h . t) 350 (append (cons a b) h . t) == (cons a (append b h . t)) 351 </pre> 352 <!-- TODO add xref/comp to append --> 353 </blockquote></div> 354 355 <div class="defun"> 356 — Applicative: <b>list-neighbors</b> (<var>list-neighbors list</var>)<var><a name="index-list_002dneighbors-93"></a></var><br> 357 <blockquote><p> The <code>list-neighbors</code> applicative constructs and returns a list 358 of all the consecutive sublists of <code>list</code> of length 2, in order. 359 If <code>list</code> is nil, the result is nil. If <code>list</code> is non-nil, 360 the length of the result is one less than the length of 361 <code>list</code>. If <code>list</code> is cyclic, the result is structurally 362 isomorphic to it (i.e., has the same acyclic prefix length and cycle 363 length). 364 <!-- TODO add xref to isomorphic --> 365 366 <p>For example: 367 <pre class="example"> (list-neighbors (list 1 2 3 4)) ⇒ ((1 2) (2 3) (3 4)) 368 </pre> 369 </blockquote></div> 370 371 <div class="defun"> 372 — Applicative: <b>filter</b> (<var>filter applicative list</var>)<var><a name="index-filter-94"></a></var><br> 373 <blockquote><p> Applicative <code>filter</code> passes each of the elements of <code>list</code> 374 as an argument to <code>applicative</code>, one at a time in no particular 375 order, using a fresh empty environment for each call. The result of 376 each call to <code>applicative</code> must be boolean, otherwise an error is 377 signaled. <code>filter</code> constructs and returns a list of all elements 378 of <code>list</code> on which <code>applicative</code> returned true, in the same 379 order as in <code>list</code>. <code>applicative</code> is called exactly as many 380 times as there are pairs in <code>list</code>. The resultant list has a 381 cycle containing exactly those elements accepted by <code>applicative</code> 382 that were in the cycle of <code>list</code>; if there were no such elements, 383 the result is acyclic. 384 </p></blockquote></div> 385 386 <div class="defun"> 387 — Applicative: <b>assoc</b> (<var>assoc object pairs </var>[<var>eq-pred?</var>])<var><a name="index-assoc-95"></a></var><br> 388 <blockquote><p> Applicative <code>assoc</code> returns the first element of <code>pairs</code> 389 whose car is <code>eq-pred?</code> to <code>object</code>. If there is no such 390 element in <code>pairs</code>, nil is returned. If <code>eq-pred?</code> is not 391 supplied it defaults to <code>equal?</code>. 392 <!-- TODO add xref/comp to assq --> 393 <!-- TODO add xref to equal? --> 394 SOURCE NOTE: the optional eq-pred? argument is from r7rs. 395 </p></blockquote></div> 396 397 <div class="defun"> 398 — Applicative: <b>member?</b> (<var>member? object list </var>[<var>eq-pred?</var>])<var><a name="index-member_003f-96"></a></var><br> 399 <blockquote><p> Applicative <code>member?</code> is a predicate that returns true iff some 400 element of <code>list</code> is <code>eq-pred?</code> to <code>object</code>. If 401 <code>eq-pred?</code> is not supplied, it defaults to <code>equal?</code>. 402 <!-- TODO add xref/comp to memq --> 403 <!-- TODO add xref to equal? --> 404 SOURCE NOTE: the optional eq-pred? argument is from r7rs. 405 </p></blockquote></div> 406 407 <div class="defun"> 408 — Applicative: <b>finite-list?</b> (<var>finite-list? . objects</var>)<var><a name="index-finite_002dlist_003f-97"></a></var><br> 409 <blockquote><p> This is the type predicate for type finite-list. 410 <code>finite-list?</code> returns true iff all the objects in 411 <code>objects</code> are acyclic lists. 412 </p></blockquote></div> 413 414 <div class="defun"> 415 — Applicative: <b>countable-list?</b> (<var>countable-list? . objects</var>)<var><a name="index-countable_002dlist_003f-98"></a></var><br> 416 <blockquote><p>This is the type predicate for type list. <code>countable-list?</code> 417 returns true iff all the objects in <code>objects</code> are lists. 418 </p></blockquote></div> 419 420 <div class="defun"> 421 — Applicative: <b>reduce</b> (<var>reduce list binary identity </var>[<var>precycle incycle postcycle</var>])<var><a name="index-reduce-99"></a></var><br> 422 <blockquote><p> <code>binary</code> should be an applicative. If the short form is used, 423 <code>list</code> should be an acyclic. If the long form is used, 424 <code>precycle</code>, <code>incycle</code>, and <code>postcycle</code> should be 425 applicatives. 426 427 <p>If <code>list</code> is empty, applicative <code>reduce</code> returns 428 <code>identity</code>. If <code>list</code> is nonempty but acyclic, applicative 429 <code>reduce</code> uses binary operation <code>binary</code> to merge all the 430 elements of <code>list</code> into a single object, using any associative 431 grouping of the elements. That is, the sequence of objects initially 432 found in <code>list</code> is repeatedly decremented in length by applying 433 <code>binary</code> to a list of any two consecutive objects, replacing 434 those two objects with the result at the point in the sequence where 435 they occurred; and when the sequence contains only one object, that 436 object is returned. If <code>list</code> is cyclic, the long form must be 437 used. The elements of the cycle are passed, one at a time (but just 438 once for each position in the cycle), as arguments to unary 439 applicative <code>precycle</code>; the finite, cyclic sequence of results 440 from <code>precycle</code> is reduced using binary applicative 441 <code>incycle</code>; and the result from reducing the cycle is passed as an 442 argument to unary applicative <code>postcycle</code>. Binary operation 443 <code>binary</code> is used to reduce the sequence consisting of the 444 elements of the acyclic prefix of <code>list</code> followed by the result 445 returned by <code>postcycle</code>. The only constraint on the order of 446 calls to the applicatives is that each call must be made before its 447 result is needed (thus, parts of the reduction of the acyclic prefix 448 may occur before the contribution from the cycle has been completed). 449 450 <p>Each call to <code>binary</code>, <code>precycle</code>, <code>incycle</code>, or 451 <code>postcycle</code> uses the dynamic environment of the call to 452 <code>reduce</code>. 453 454 <p>If <code>list</code> is acyclic with length <code>n >= 1</code>, 455 <code>binary</code> is called <code>n - 1</code> times. If <code>list</code> is cyclic 456 with acyclic prefix length <code>a</code> and cycle length <code>c</code>, 457 <code>binary</code> is called <code>a</code> times; <code>precycle</code>, <code>c</code> 458 times; <code>incycle</code>, <code>c - 1</code> times; and <code>postcycle</code>, once. 459 </p></blockquote></div> 460 461 <div class="defun"> 462 — Applicative: <b>append!</b> (<var>append! . lists</var>)<var><a name="index-append_0021-100"></a></var><br> 463 <blockquote><p> <code>lists</code> must be a nonempty list; its first element must be an 464 acyclic nonempty list, and all of its elements except the last element 465 (if any) must be acyclic lists. 466 467 <p>The <code>append!</code> applicative sets the cdr of the last pair in each 468 nonempty list argument to refer to the next non-nil argument, except 469 that if there is a last non-nil argument, it isn’t mutated. It is an 470 error for any two of the list arguments to have the same last pair. 471 The result returned by this applicative is inert. 472 473 <p>The following equivalences hold: 474 <pre class="example"> (append! v) == #inert 475 (append! u v . w) == ($sequence (append! u v) (append! u . w)) 476 </pre> 477 </blockquote></div> 478 479 <div class="defun"> 480 — Applicative: <b>copy-es</b> (<var>copy-es object</var>)<var><a name="index-copy_002des-101"></a></var><br> 481 <blockquote><p> Briefly, applicative <code>copy-es</code> returns an object initially 482 <code>equal?</code> to <code>object</code> with a freshly constructed evaluation 483 <!-- TODO add xref to evaluation structure --> 484 structure made up of mutable pairs. If <code>object</code> is not a pair, 485 the applicative returns <code>object</code>. If <code>object</code> is a pair, 486 the applicative returns a freshly constructed pair whose car and cdr 487 would be suitable results for <code>(copy-es (car object))</code> and 488 <code>(copy-es (cdr object))</code>, respectively. Further, the evaluation 489 <!-- TODO add xref to isomorphic --> 490 structure of the returned value is structurally isomorphic to that of 491 <code>object</code> at the time of copying, with corresponding non-pair 492 referents being <code>eq?</code>. 493 <!-- TODO add xref/comp to copy-es-immutable and the reverse too! --> 494 <!-- TODO add xref to eq?/equal? --> 495 </p></blockquote></div> 496 497 <div class="defun"> 498 — Applicative: <b>assq</b> (<var>assq object pairs</var>)<var><a name="index-assq-102"></a></var><br> 499 <blockquote><p> Applicative <code>assq</code> returns the first element of <code>pairs</code> 500 whose car is <code>eq?</code> to <code>object</code>. If there is no such element 501 in <code>pairs</code>, nil is returned. 502 <!-- TODO add xref/comp to assoc --> 503 <!-- TODO add xref to eq? --> 504 </p></blockquote></div> 505 506 <div class="defun"> 507 — Applicative: <b>memq?</b> (<var>memq? object list</var>)<var><a name="index-memq_003f-103"></a></var><br> 508 <blockquote><p> Applicative <code>memq?</code> is a predicate that returns true iff some 509 element of <code>list</code> is <code>eq?</code> to <code>object</code>. 510 <!-- TODO add xref/comp to member? --> 511 <!-- TODO add xref to eq? --> 512 </p></blockquote></div> 513 514 <!-- *-texinfo-*- --> 515 </body></html> 516