clqr-conses.tex

   1 % Copyright (C) 2008, 2009, 2010 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   {Set \VAR{place} to
 194   \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   {Set \VAR{place} to
 203   \retval{(\FU{adjoin} \VAR{foo} \VAR{place})}.
 204   }
 205
 206   \IT{\arrGOO{(\FU*{APPEND } \Op{\OPn{\VAR{list}} \VAR{ foo}})\\
 207       (\FU*{NCONC } \Op{\OPn{\DES{\VAR{list}}} \VAR{ foo}})}{.}}
 208   {
 209   Return \retval{concatenated list}. \VAR{foo} can be of any type.
 210   }
 211
 212   \IT{\arrGOO{(\FU*{REVAPPEND} \VAR{ list} \VAR{ foo})\\
 213       (\FU*{NRECONC }
 214       \DES{\VAR{list}} \VAR{ foo})}{.}}
 215   {
 216   Return \retval{concatenated list} after reversing order in
 217   \VAR{list}.
 218   }
 219
 220   \IT{(\xorGOO{\FU*{MAPCAR}\\
 221       \FU*{MAPLIST}}{\}} \VAR{function} \RP{\VAR{list}})}
 222   {
 223   Return \retval{list of return values} of \VAR{function} successively
 224   invoked with corresponding arguments, either cars or cdrs, respectively,
 225   from each \VAR{list}.
 226   }
 227
 228   \IT{(\xorGOO{\FU*{MAPCAN}\\
 229       \FU*{MAPCON}}{\}} \VAR{function} \RP{\VAR{list}})}
 230   {
 231   Return list of
 232   \retval{concatenated return values} of
 233   \VAR{function} successively invoked with corresponding arguments,
 234   either cars or cdrs, respectively,
 235   from each \VAR{list}. \VAR{function} should return a list.
 236   }
 237
 238   \IT{(\xorGOO{\FU*{MAPC}\\
 239       \FU*{MAPL}}{\}} \VAR{function} \RP{\VAR{list}})}
 240   {
 241   Return \retval{first \VAR{list}} after successively applying
 242   \VAR{function} to corresponding arguments, either cars or cdrs,
 243   respectively, from each \VAR{list}. \VAR{function} should have some side
 244   effects.
 245   }
 246
 247   \IT{(\FU*{COPY-LIST} \VAR{list})}
 248   {
 249   Return \retval{copy} of \VAR{list} with shared elements.
 250   }
 251
 252 \end{LIST}
 253
 254
 255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 256 \subsection{Association Lists}
 257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 258 \label{section:Association Lists}
 259 \begin{LIST}{1cm}
 260
 261   \IT{(\FU*{PAIRLIS} \VAR{keys} \VAR{values} \Op{\VAR{alist}\DF{\NIL}})}
 262   {
 263     Prepend to \retval{\VAR{alist}} an association list made from lists \VAR{keys} and \VAR{values}.
 264   }
 265
 266   \IT{(\FU*{ACONS} \VAR{key} \VAR{value} \VAR{alist})}
 267   {
 268   Return \retval{\VAR{alist}} with a (\VAR{key} \kwd{.} \VAR{value}) pair added.
 269   }
 270
 271   \IT{\arrGOO{(\xorGOO{\FU*{ASSOC}\\
 272         \FU*{RASSOC}}{\}}
 273       \VAR{ foo} \VAR{ alist }
 274       \orGOO{\xorGOO{%
 275           \kwd{:test} \VAR{ test}\DF{\kwd{\#'eql}}\\
 276           \kwd{:test-not} \VAR{ test}}{.}\\
 277         \kwd{:key} \VAR{ function}
 278       }{\}})\\
 279     (\xorGOO{\FU*{ASSOC-IF}\Op{\kwd{-NOT}}\\
 280       \FU*{RASSOC-IF}\Op{\kwd{-NOT}}}{\}} \VAR{ test} \VAR{ alist }
 281       \Op{\kwd{:key} \VAR{ function}})}{.}}
 282   {
 283 \index{ASSOC-IF-NOT}\index{RASSOC-IF-NOT}%
 284   First \retval{cons} whose car, or cdr, respectively, satisfies \VAR{test}.
 285   }
 286
 287   \IT{(\FU*{COPY-ALIST} \VAR{alist})}
 288   {
 289   Return \retval{copy} of \VAR{alist}.
 290   }
 291
 292 \end{LIST}
 293
 294
 295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 296 \subsection{Trees}
 297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 298 \begin{LIST}{1cm}
 299
 300   \IT{(\FU*{TREE-EQUAL} \VAR{foo} \VAR{bar}
 301     \xorGOO{\kwd{:test} \VAR{ test}\DF{\kwd{\#'eql}}\\
 302       \kwd{:test-not} \VAR{ test}}{\}})}
 303   {
 304   Return \retval{\T} if trees \VAR{foo} and \VAR{bar} have same
 305   shape and leaves satisfying \VAR{test}.
 306   }
 307
 308   \IT{(\xorGOO{\FU*{SUBST} \VAR{ new} \VAR{ old } \VAR{tree}\\
 309       \FU*{NSUBST} \VAR{ new} \VAR{ old } \DES{\VAR{tree}}}{\}}
 310     \orGOO{\xorGOO{%
 311         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 312         \kwd{:test-not} \VAR{ function}}{.}\\
 313       \kwd{:key} \VAR{ function}%
 314     }{\}})}
 315   {
 316   Make \retval{copy of
 317     \VAR{tree}} with each subtree or leaf matching \VAR{old} replaced by
 318   \VAR{new}.
 319   }
 320
 321   \IT{(\xorGOO{\FU{SUBST-IF\Op{-NOT}} \VAR{ new} \VAR{ test } \VAR{tree}\\
 322       \FU{NSUBST-IF\Op{-NOT}} \VAR{ new} \VAR{ test } \DES{\VAR{tree}}}{\}}
 323     \Op{\kwd{:key} \VAR{function}})}
 324   {
 325   \index{SUBST-IF}%
 326   \index{SUBST-IF-NOT}%
 327   \index{NSUBST-IF}%
 328   \index{NSUBST-IF-NOT}%
 329   Make \retval{copy of \VAR{tree}} with each subtree or leaf
 330   satisfying \VAR{test} replaced by \VAR{new}.
 331   }
 332
 333   \IT{(\xorGOO{\FU*{SUBLIS} \VAR{ association-list } \VAR{tree} \\
 334       \FU*{NSUBLIS} \VAR{ association-list } \DES{\VAR{tree}} }{\}}
 335     \orGOO{\xorGOO{%
 336         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 337         \kwd{:test-not} \VAR{ function}}{.}\\
 338       \kwd{:key} \VAR{ function}%
 339     }{\}})}
 340   {
 341   Make \retval{copy of \VAR{tree}} with each subtree or leaf matching
 342   a key in \VAR{association-list} replaced by that key's value.
 343   }
 344
 345   \IT{(\FU*{COPY-TREE} \VAR{tree})}
 346   {
 347     \retval{Copy of \VAR{tree}} with same shape and leaves.
 348   }
 349
 350 \end{LIST}
 351
 352
 353 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 354 \subsection{Sets}
 355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 356 \begin{LIST}{1cm}
 357
 358   \IT{(\xorGOO{%
 359       \arrGOO{%
 360         \FU*{INTERSECTION}\\
 361         \FU*{SET-DIFFERENCE}\\
 362         \FU*{UNION}\\
 363         \FU*{SET-EXCLUSIVE-OR}%
 364       }{\}} \VAR{ a} \VAR{ b}\\
 365       \arrGOO{%
 366         \FU*{NINTERSECTION}\\
 367         \FU*{NSET-DIFFERENCE}%
 368       }{\}} \text{ }\DES{\VAR{a}}\text{ } \VAR{b}\\
 369       \arrGOO{%
 370         \FU*{NUNION}\\
 371         \FU*{NSET-EXCLUSIVE-OR}%
 372       }{\}} \text{ }\DES{\VAR{a}}\text{ } \DES{\VAR{b}}\text{ }
 373     }{\}}
 374     \orGOO{\xorGOO{%
 375         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 376         \kwd{:test-not} \VAR{ function}}{.}\\
 377       \kwd{:key} \VAR{ function}}{\}})}
 378   {
 379   Return \retval{$a\cap b$}, \retval{$a\setminus b$}, \retval{$a\cup b$}, or
 380   \retval{$a\,\triangle\, b$}, respectively, of lists \VAR{a} and \VAR{b}.
 381   }
 382
 383 \end{LIST}
 384
 385
 386 %%% Local Variables:
 387 %%% mode: latex
 388 %%% TeX-master: "clqr"
 389 %%% End: