clqr-conses.tex

   1 % Copyright (C) 2008, 2009, 2010, 2011 Bert Burgemeister
   2 %
   3 % Permission is granted to copy, distribute and/or modify this
   4 % document under the terms of the GNU Free Documentation License,
   5 % Version 1.2 or any later version published by the Free Software
   6 % Foundation; with no Invariant Sections, no Front-Cover Texts and
   7 % no Back-Cover Texts. For details see file COPYING.
   8 %
   9
  10 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  11 \section{Conses}
  12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  13
  14 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  15 \subsection{Predicates}
  16 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  17 \begin{LIST}{1cm}
  18
  19   \IT{\arrGOO{(\FU*{CONSP} \VAR{ foo})\\
  20       (\FU*{LISTP} \VAR{ foo})}{.}}
  21   {
  22     Return \retval{\T} if \VAR{foo} is of indicated type.
  23     }
  24
  25   \IT{\arrGOO{(\FU*{ENDP} \VAR{ list})\\
  26       (\FU*{NULL} \VAR{ foo})}{.}\qquad\qquad}
  27   {
  28   Return \retval{\T} if \VAR{list}/\VAR{foo} is \NIL.
  29   }
  30
  31   \IT{(\FU*{ATOM} \VAR{foo})\qquad\qquad}
  32   {Return \retval{\T} if \VAR{foo} is not a
  33   \kwd{cons}.
  34   }
  35
  36   \IT{(\FU*{TAILP} \VAR{foo} \VAR{list})}
  37   {
  38   Return \retval{\T} if \VAR{foo} is a tail of \VAR{list}.
  39   }
  40
  41   \IT{(\FU*{MEMBER} \VAR{foo} \VAR{list}
  42     \orGOO{\xorGOO{%
  43         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
  44         \kwd{:test-not} \VAR{ function}}{.}\\
  45       \kwd{:key} \VAR{ function}}{\}})}
  46   {
  47   Return \retval{tail of \VAR{list}} starting with
  48   its first element matching \VAR{foo}. Return \retval{\NIL} if
  49   there is no such element.
  50   }
  51
  52   \IT{(\xorGOO{\FU*{MEMBER-IF}\\
  53       \FU*{MEMBER-IF-NOT}}{\}}
  54     \VAR{test} \VAR{list}
  55     \Op{\kwd{:key} \VAR{function}})}
  56   {
  57   Return \retval{tail of \VAR{list}} starting with
  58   its first element satisfying \VAR{test}. Return \retval{\NIL} if
  59   there is no such element.
  60   }
  61
  62   \IT{(\FU*{SUBSETP} \VAR{list-a} \VAR{list-b}
  63     \orGOO{\xorGOO{%
  64         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
  65         \kwd{:test-not} \VAR{ function}}{.}\\
  66       \kwd{:key} \VAR{ function}}{\}})}
  67   {
  68   Return \retval{\T} if \VAR{list-a} is a subset of
  69   \VAR{list-b}.
  70   }
  71
  72 \end{LIST}
  73
  74
  75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  76 \subsection{Lists}
  77 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  78 \begin{LIST}{1cm}
  79
  80   \IT{(\FU*{CONS} \VAR{foo} \VAR{bar})}
  81   {
  82   Return new cons \retval{(\VAR{foo} \kwd {.} \VAR{bar})}.
  83   }
  84
  85   \IT{(\FU*{LIST} \OPn{\VAR{foo}})}
  86   {Return \retval{list of \VAR{foo}s}.
  87     }
  88
  89   \IT{(\FU*{LIST\A} \RP{\VAR{foo}})}
  90   {Return \retval{list of \VAR{foo}s}
  91   with last \VAR{foo} becoming cdr of last cons. Return
  92   \retval{\VAR{foo}} if only one \VAR{foo} given.
  93   }
  94
  95   \IT{(\FU*{MAKE-LIST} \VAR{num} \Op{\kwd{:initial-element}
  96       \VAR{foo}\DF{\NIL}})}
  97   {
  98     New \retval{list} with \VAR{num} elements set to \VAR{foo}.
  99   }
 100
 101   \IT{(\FU*{LIST-LENGTH} \VAR{list})}
 102   {\retval{Length} of \VAR{list};
 103   \retval{\NIL} for circular \VAR{list}.
 104   }
 105
 106   \IT{(\FU*{CAR} \VAR{list})\qquad\qquad}
 107   {
 108   \retval{Car of \VAR{list}} or \retval{\NIL} if \VAR{list} is
 109   \NIL. \kwd{SETF}able.
 110   }
 111
 112   \IT{\arrGOO{(\FU*{CDR} \VAR{ list})\qquad\\
 113       (\FU*{REST} \VAR{ list})}{.}}
 114   {
 115   \retval{Cdr of \VAR{list}} or \retval{\NIL} if \VAR{list}
 116   is \NIL. \kwd{SETF}able.
 117   }
 118
 119   \IT{(\FU*{NTHCDR} \VAR{n list})}
 120   {Return \retval{tail of \VAR{list}} after calling \FU{cdr} \VAR{n} times.
 121     }
 122
 123   \IT{(\Goo{\FU*{FIRST}\XOR\FU*{SECOND}\XOR\FU*{THIRD}\XOR\FU*{FOURTH}\XOR\FU*{FIFTH}\XOR\FU*{SIXTH}\XOR\dots\XOR\FU*{NINTH}\XOR\FU*{TENTH}}
 124     \VAR{list})}
 125   {
 126   \index{SEVENTH}%
 127   \index{EIGHTH}%
 128   Return \retval{nth element of \VAR{list}} if any,
 129   or \retval{\NIL} otherwise. \kwd{SETF}able.
 130   }
 131
 132   \IT{(\FU*{NTH} \VAR{n list})}
 133   {
 134     Zero-indexed \retval{\VAR{n}th element} of \VAR{list}. \kwd{setf}able.
 135   }
 136
 137   \IT{(\FU{C}\VAR{X}\kwd{R} \VAR{list})}
 138   {
 139   \index{CAAR}%
 140   \index{CADR}%
 141   \index{CDAR}%
 142   \index{CDDR}%
 143   With \VAR{X} being one to four
 144   \kwd{a}s and \kwd{d}s representing \FU{CAR}s and \FU{CDR}s, e.g.
 145   (\FU{CADR} \VAR{bar}) is equivalent to (\FU{CAR} (\FU{CDR}
 146   \VAR{bar})).
 147   \kwd{SETF}able.
 148   }
 149
 150   \IT{(\FU*{LAST} \VAR{list} \Op{\VAR{num}\DF{\LIT{1}}})}
 151   {
 152   Return list of \retval{last \VAR{num}
 153     conses} of \VAR{list}.
 154   }
 155
 156   \IT{(\xorGOO{\FU*{BUTLAST }  \VAR{list}\\
 157       \FU*{NBUTLAST }  \DES{\VAR{list}}}{\}}
 158     \Op{\VAR{num}\DF{\LIT{1}}})}
 159   {
 160     \retval{\VAR{list}} excluding last \VAR{num}
 161     conses.
 162   }
 163
 164   \IT{(\xorGOO{\FU*{RPLACA}\\
 165     \FU*{RPLACD}}{\}} \DES{\VAR{cons}} \VAR{object})}
 166   {
 167   Replace car, or cdr, respectively, of \retval{\VAR{cons}} with \VAR{object}.
 168   }
 169
 170   \IT{(\FU*{LDIFF} \VAR{list} \VAR{foo})}
 171   {
 172   If \VAR{foo} is a tail of \VAR{list}, return \retval{preceding
 173     part of \VAR{list}}. Otherwise return \retval{\VAR{list}}.
 174   }
 175
 176   \IT{(\FU*{ADJOIN} \VAR{foo} \VAR{list}
 177     \orGOO{\xorGOO{%
 178         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 179         \kwd{:test-not} \VAR{ function}}{.}\\
 180       \kwd{:key} \VAR{ function}}{\}})}
 181   {Return \retval{\VAR{list}} if \VAR{foo} is
 182   already member of \VAR{list}. If not, return \retval{(\FU{CONS}
 183     \VAR{foo} \VAR{list})}.
 184   }
 185
 186   \IT{(\MC*{POP} \DES{\VAR{place}})}
 187   {
 188     Set \VAR{place} to (\FU{CDR} \VAR{place}), return
 189     \retval{(\FU{CAR} \VAR{place})}.
 190   }
 191
 192   \IT{(\MC*{PUSH} \VAR{foo} \DES{\VAR{place}})}
 193   {
 194     Set \VAR{place} to \retval{(\FU{cons} \VAR{foo} \VAR{place})}.
 195   }
 196
 197   \IT{(\MC*{PUSHNEW} \VAR{foo} \DES{\VAR{place}}
 198     \orGOO{\xorGOO{%
 199         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 200         \kwd{:test-not} \VAR{ function}}{.}\\
 201       \kwd{:key} \VAR{ function}}{\}})}
 202   {
 203     Set \VAR{place} to \retval{(\FU{adjoin} \VAR{foo} \VAR{place})}.
 204   }
 205
 206   \IT{\arrGOO{(\FU*{APPEND } \Op{\OPn{\VAR{proper-list}}
 207         \VAR{ foo}\DF{\NIL}})\\
 208       (\FU*{NCONC } \Op{\OPn{\DES{\VAR{non-circular-list}}}
 209         \VAR{ foo}\DF{\NIL}})}{.}}
 210   {
 211     Return \retval{concatenated list} or, with only one argument,
 212     \retval{\VAR{foo}}. \VAR{foo} can be of any type.
 213   }
 214
 215   \IT{\arrGOO{(\FU*{REVAPPEND} \VAR{ list} \VAR{ foo})\\
 216       (\FU*{NRECONC }
 217       \DES{\VAR{list}} \VAR{ foo})}{.}}
 218   {
 219     Return \retval{concatenated list} after reversing order in
 220     \VAR{list}.
 221   }
 222
 223   \IT{(\xorGOO{\FU*{MAPCAR}\\
 224       \FU*{MAPLIST}}{\}} \VAR{function} \RP{\VAR{list}})}
 225   {
 226     Return \retval{list of return values} of \VAR{function}
 227     successively invoked with corresponding arguments, either cars or
 228     cdrs, respectively, from each \VAR{list}.
 229   }
 230
 231   \IT{(\xorGOO{\FU*{MAPCAN}\\
 232       \FU*{MAPCON}}{\}} \VAR{function} \RP{\VAR{list}})}
 233   {
 234     Return list of \retval{concatenated return values} of
 235     \VAR{function} successively invoked with corresponding arguments,
 236     either cars or cdrs, respectively, from each
 237     \VAR{list}. \VAR{function} should return a list.
 238   }
 239
 240   \IT{(\xorGOO{\FU*{MAPC}\\
 241       \FU*{MAPL}}{\}} \VAR{function} \RP{\VAR{list}})}
 242   {
 243     Return \retval{first \VAR{list}} after successively applying
 244     \VAR{function} to corresponding arguments, either cars or cdrs,
 245     respectively, from each \VAR{list}. \VAR{function} should have
 246     some side effects.
 247   }
 248
 249   \IT{(\FU*{COPY-LIST} \VAR{list})}
 250   {
 251     Return \retval{copy} of \VAR{list} with shared elements.
 252   }
 253
 254 \end{LIST}
 255
 256
 257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 258 \subsection{Association Lists}
 259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 260 \label{section:Association Lists}
 261 \begin{LIST}{1cm}
 262
 263   \IT{(\FU*{PAIRLIS} \VAR{keys} \VAR{values} \Op{\VAR{alist}\DF{\NIL}})}
 264   {
 265     Prepend to \retval{\VAR{alist}} an association list made from
 266     lists \VAR{keys} and \VAR{values}.
 267   }
 268
 269   \IT{(\FU*{ACONS} \VAR{key} \VAR{value} \VAR{alist})}
 270   {
 271     Return \retval{\VAR{alist}} with a (\VAR{key} \kwd{.} \VAR{value})
 272     pair added.
 273   }
 274
 275   \IT{\arrGOO{(\xorGOO{\FU*{ASSOC}\\
 276         \FU*{RASSOC}}{\}}
 277       \VAR{ foo} \VAR{ alist }
 278       \orGOO{\xorGOO{%
 279           \kwd{:test} \VAR{ test}\DF{\kwd{\#'eql}}\\
 280           \kwd{:test-not} \VAR{ test}}{.}\\
 281         \kwd{:key} \VAR{ function}
 282       }{\}})\\
 283     (\xorGOO{\FU*{ASSOC-IF}\Op{\kwd{-NOT}}\\
 284       \FU*{RASSOC-IF}\Op{\kwd{-NOT}}}{\}} \VAR{ test} \VAR{ alist }
 285       \Op{\kwd{:key} \VAR{ function}})}{.}}
 286   {\index{ASSOC-IF-NOT}\index{RASSOC-IF-NOT}%
 287     First \retval{cons} whose car, or cdr, respectively, satisfies
 288     \VAR{test}.
 289   }
 290
 291   \IT{(\FU*{COPY-ALIST} \VAR{alist})}
 292   {
 293     Return \retval{copy} of \VAR{alist}.
 294   }
 295
 296 \end{LIST}
 297
 298
 299 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 300 \subsection{Trees}
 301 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 302 \begin{LIST}{1cm}
 303
 304   \IT{(\FU*{TREE-EQUAL} \VAR{foo} \VAR{bar}
 305     \xorGOO{\kwd{:test} \VAR{ test}\DF{\kwd{\#'eql}}\\
 306       \kwd{:test-not} \VAR{ test}}{\}})}
 307   {
 308     Return \retval{\T} if trees \VAR{foo} and \VAR{bar} have same
 309     shape and leaves satisfying \VAR{test}.
 310   }
 311
 312   \IT{(\xorGOO{\FU*{SUBST} \VAR{ new} \VAR{ old } \VAR{tree}\\
 313       \FU*{NSUBST} \VAR{ new} \VAR{ old } \DES{\VAR{tree}}}{\}}
 314     \orGOO{\xorGOO{%
 315         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 316         \kwd{:test-not} \VAR{ function}}{.}\\
 317       \kwd{:key} \VAR{ function}%
 318     }{\}})}
 319   {
 320     Make \retval{copy of \VAR{tree}} with each subtree or leaf
 321     matching \VAR{old} replaced by \VAR{new}.
 322   }
 323
 324   \IT{(\xorGOO{\FU{SUBST-IF\Op{-NOT}} \VAR{ new} \VAR{ test } \VAR{tree}\\
 325       \FU{NSUBST-IF\Op{-NOT}} \VAR{ new} \VAR{ test } \DES{\VAR{tree}}}{\}}
 326     \Op{\kwd{:key} \VAR{function}})}
 327   {
 328   \index{SUBST-IF}%
 329   \index{SUBST-IF-NOT}%
 330   \index{NSUBST-IF}%
 331   \index{NSUBST-IF-NOT}%
 332   Make \retval{copy of \VAR{tree}} with each subtree or leaf
 333   satisfying \VAR{test} replaced by \VAR{new}.
 334   }
 335
 336   \IT{(\xorGOO{\FU*{SUBLIS} \VAR{ association-list } \VAR{tree} \\
 337       \FU*{NSUBLIS} \VAR{ association-list } \DES{\VAR{tree}} }{\}}
 338     \orGOO{\xorGOO{%
 339         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 340         \kwd{:test-not} \VAR{ function}}{.}\\
 341       \kwd{:key} \VAR{ function}%
 342     }{\}})}
 343   {
 344   Make \retval{copy of \VAR{tree}} with each subtree or leaf matching
 345   a key in \VAR{association-list} replaced by that key's value.
 346   }
 347
 348   \IT{(\FU*{COPY-TREE} \VAR{tree})}
 349   {
 350     \retval{Copy of \VAR{tree}} with same shape and leaves.
 351   }
 352
 353 \end{LIST}
 354
 355
 356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 357 \subsection{Sets}
 358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 359 \begin{LIST}{1cm}
 360
 361   \IT{(\xorGOO{%
 362       \arrGOO{%
 363         \FU*{INTERSECTION}\\
 364         \FU*{SET-DIFFERENCE}\\
 365         \FU*{UNION}\\
 366         \FU*{SET-EXCLUSIVE-OR}%
 367       }{\}} \VAR{ a} \VAR{ b}\\
 368       \arrGOO{%
 369         \FU*{NINTERSECTION}\\
 370         \FU*{NSET-DIFFERENCE}%
 371       }{\}} \text{ }\DES{\VAR{a}}\text{ } \VAR{b}\\
 372       \arrGOO{%
 373         \FU*{NUNION}\\
 374         \FU*{NSET-EXCLUSIVE-OR}%
 375       }{\}} \text{ }\DES{\VAR{a}}\text{ } \DES{\VAR{b}}\text{ }
 376     }{\}}
 377     \orGOO{\xorGOO{%
 378         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 379         \kwd{:test-not} \VAR{ function}}{.}\\
 380       \kwd{:key} \VAR{ function}}{\}})}
 381   {
 382   Return \retval{$a\cap b$}, \retval{$a\setminus b$}, \retval{$a\cup b$}, or
 383   \retval{$a\,\triangle\, b$}, respectively, of lists \VAR{a} and \VAR{b}.
 384   }
 385
 386 \end{LIST}
 387
 388
 389 %%% Local Variables:
 390 %%% mode: latex
 391 %%% TeX-master: "clqr"
 392 %%% End: