an open source interpreter for the Kernel Programming Language.
git clone http://git.hanabi.in/repos/klisp.git
Log | Files | Refs | README

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:&nbsp;<a rel="next" accesskey="n" href="Environments.html#Environments">Environments</a>,
     30 Previous:&nbsp;<a rel="previous" accesskey="p" href="Control.html#Control">Control</a>,
     31 Up:&nbsp;<a rel="up" accesskey="u" href="index.html#Top">Top</a>
     32 <hr>
     33 </div>
     35 <!-- node-name,  next,  previous,  up -->
     36 <h2 class="chapter">7 Pairs and lists</h2>
     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.
     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.
     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>.
     62 <div class="defun">
     63 &mdash; 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>
     68 <div class="defun">
     69 &mdash; 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>
     74 <div class="defun">
     75 &mdash; Applicative: <b>immutable-pair?</b> (<var>immutable-pair? objects</var>)<var><a name="index-immutable_002dpair_003f-45"></a></var><br>
     76 &mdash; 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.
     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>
     85 <div class="defun">
     86 &mdash; 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>
     93 <div class="defun">
     94 &mdash; Applicative: <b>set-car!</b> (<var>set-car! pair object</var>)<var><a name="index-set_002dcar_0021-48"></a></var><br>
     95 &mdash; 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.
     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>
    103 <div class="defun">
    104 &mdash; 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 &ldquo;-es-&rdquo; in the name is short for &ldquo;evaluation structure&rdquo;.
    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.
    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>.
    124         <p>NOTE: In Kernel it's undefined whether immutable pairs are copied or
    125 left &ldquo;as is&rdquo; in the result.  klisp doesn't copy immutable pairs, but
    126 that behaviour should not be depended upon. 
    127 </p></blockquote></div>
    129 <div class="defun">
    130 &mdash; 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>.
    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>
    137 <div class="defun">
    138 &mdash; 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.
    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>
    147 <div class="defun">
    148 &mdash; Applicative: <b>car</b> (<var>car pair</var>)<var><a name="index-car-53"></a></var><br>
    149 &mdash; 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>
    153 <div class="defun">
    154 &mdash; Applicative: <b>caar</b> (<var>caar pair</var>)<var><a name="index-caar-55"></a></var><br>
    155 &mdash; Applicative: <b>cadr</b> (<var>cadr pair</var>)<var><a name="index-cadr-56"></a></var><br>
    156 &mdash; Applicative: <b>cdar</b> (<var>cdar pair</var>)<var><a name="index-cdar-57"></a></var><br>
    157 &mdash; Applicative: <b>cddr</b> (<var>cddr pair</var>)<var><a name="index-cddr-58"></a></var><br>
    158 &mdash; Applicative: <b>caaar</b> (<var>caaar pair</var>)<var><a name="index-caaar-59"></a></var><br>
    159 &mdash; Applicative: <b>caadr</b> (<var>caadr pair</var>)<var><a name="index-caadr-60"></a></var><br>
    160 &mdash; Applicative: <b>cadar</b> (<var>cadar pair</var>)<var><a name="index-cadar-61"></a></var><br>
    161 &mdash; Applicative: <b>caddr</b> (<var>caddr pair</var>)<var><a name="index-caddr-62"></a></var><br>
    162 &mdash; Applicative: <b>cdaar</b> (<var>cdaar pair</var>)<var><a name="index-cdaar-63"></a></var><br>
    163 &mdash; Applicative: <b>cdadr</b> (<var>cdadr pair</var>)<var><a name="index-cdadr-64"></a></var><br>
    164 &mdash; Applicative: <b>cddar</b> (<var>cddar pair</var>)<var><a name="index-cddar-65"></a></var><br>
    165 &mdash; Applicative: <b>cdddr</b> (<var>cdddr pair</var>)<var><a name="index-cdddr-66"></a></var><br>
    166 &mdash; Applicative: <b>caaaar</b> (<var>caaaar pair</var>)<var><a name="index-caaaar-67"></a></var><br>
    167 &mdash; Applicative: <b>caaadr</b> (<var>caaadr pair</var>)<var><a name="index-caaadr-68"></a></var><br>
    168 &mdash; Applicative: <b>caadar</b> (<var>caadar pair</var>)<var><a name="index-caadar-69"></a></var><br>
    169 &mdash; Applicative: <b>caaddr</b> (<var>caaddr pair</var>)<var><a name="index-caaddr-70"></a></var><br>
    170 &mdash; Applicative: <b>cadaar</b> (<var>cadaar pair</var>)<var><a name="index-cadaar-71"></a></var><br>
    171 &mdash; Applicative: <b>cadadr</b> (<var>cadadr pair</var>)<var><a name="index-cadadr-72"></a></var><br>
    172 &mdash; Applicative: <b>caddar</b> (<var>caddar pair</var>)<var><a name="index-caddar-73"></a></var><br>
    173 &mdash; Applicative: <b>cadddr</b> (<var>cadddr pair</var>)<var><a name="index-cadddr-74"></a></var><br>
    174 &mdash; Applicative: <b>cdaaar</b> (<var>cdaaar pair</var>)<var><a name="index-cdaaar-75"></a></var><br>
    175 &mdash; Applicative: <b>cdaadr</b> (<var>cdaadr pair</var>)<var><a name="index-cdaadr-76"></a></var><br>
    176 &mdash; Applicative: <b>cdadar</b> (<var>cdadar pair</var>)<var><a name="index-cdadar-77"></a></var><br>
    177 &mdash; Applicative: <b>cdaddr</b> (<var>cdaddr pair</var>)<var><a name="index-cdaddr-78"></a></var><br>
    178 &mdash; Applicative: <b>cddaar</b> (<var>cddaar pair</var>)<var><a name="index-cddaar-79"></a></var><br>
    179 &mdash; Applicative: <b>cddadr</b> (<var>cddadr pair</var>)<var><a name="index-cddadr-80"></a></var><br>
    180 &mdash; Applicative: <b>cdddar</b> (<var>cdddar pair</var>)<var><a name="index-cdddar-81"></a></var><br>
    181 &mdash; 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 &ldquo;a’s&rdquo; and &ldquo;d’s&rdquo; in the same order as they would appear if all
    186 the individual &ldquo;car’s&rdquo; and &ldquo;cdr’s&rdquo; 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>
    191 <div class="defun">
    192 &mdash; 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.
    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.
    199         <p>SOURCE NOTE: this is taken from r7rs. 
    200 </p></blockquote></div>
    202 <div class="defun">
    203 &mdash; 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>.
    209         <p>SOURCE NOTE: this is taken from r7rs. 
    210 </p></blockquote></div>
    212 <div class="defun">
    213 &mdash; 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.
    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.
    222         <p>SOURCE NOTE: this is taken from r7rs. 
    223 </p></blockquote></div>
    225 <div class="defun">
    226 &mdash; 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>
    254 <div class="defun">
    255 &mdash; 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.
    259         <p>The <code>list-tail</code> applicative follows <code>k</code> cdr references
    260 starting from <code>object</code>.
    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>
    268 <div class="defun">
    269 &mdash; 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.
    273         <p>If <code>k2 = 0</code>, the applicative does nothing. If <code>k2 &gt; 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>
    281 <div class="defun">
    282 &mdash; 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.
    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>
    307 <div class="defun">
    308 &mdash; 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>
    317 <div class="defun">
    318 &mdash; 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>.
    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>
    331 <div class="defun">
    332 &mdash; 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>.
    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>
    355 <div class="defun">
    356 &mdash; 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 -->
    366         <p>For example:
    367      <pre class="example">          (list-neighbors (list 1 2 3 4)) &rArr; ((1 2) (2 3) (3 4))
    368 </pre>
    369         </blockquote></div>
    371 <div class="defun">
    372 &mdash; 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>
    386 <div class="defun">
    387 &mdash; 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>
    397 <div class="defun">
    398 &mdash; 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>
    407 <div class="defun">
    408 &mdash; 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>
    414 <div class="defun">
    415 &mdash; 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>
    420 <div class="defun">
    421 &mdash; 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.
    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).
    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>.
    454         <p>If <code>list</code> is acyclic with length <code>n &gt;= 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>
    461 <div class="defun">
    462 &mdash; 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.
    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.
    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>
    479 <div class="defun">
    480 &mdash; 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>
    497 <div class="defun">
    498 &mdash; 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>
    506 <div class="defun">
    507 &mdash; 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>
    514 <!-- *-texinfo-*- -->
    515    </body></html>