clqr-conses.tex

   1 % Copyright (C) 2008, 2009 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   {Return zero-indexed \retval{\VAR{n}th element} of \VAR{list}. \kwd{setf}able.
 134     }
 135
 136   \IT{(\FU{C}\VAR{X}\kwd{R} \VAR{list})}
 137   {
 138   \index{CAAR}%
 139   \index{CADR}%
 140   \index{CDAR}%
 141   \index{CDDR}%
 142   With \VAR{X} being one to four
 143   \kwd{a}s and \kwd{d}s representing \FU{CAR}s and \FU{CDR}s, e.g.
 144   (\FU{CADR} \VAR{bar}) is equivalent to (\FU{CAR} (\FU{CDR}
 145   \VAR{bar})).
 146   \kwd{SETF}able.
 147   }
 148
 149   \IT{(\FU*{LAST} \VAR{list} \Op{\VAR{num}\DF{\LIT{1}}})}
 150   {
 151   Return list of \retval{last \VAR{num}
 152     conses} of \VAR{list}.
 153   }
 154
 155   \IT{(\xorGOO{\FU*{BUTLAST }  \VAR{list}\\
 156       \FU*{NBUTLAST }  \DES{\VAR{list}}}{\}}
 157     \Op{\VAR{num}\DF{\LIT{1}}})}
 158   {
 159   Return \retval{\VAR{list}} excluding last \VAR{num}
 160     conses.
 161   }
 162
 163   \IT{(\xorGOO{\FU*{RPLACA}\\
 164     \FU*{RPLACD}}{\}} \DES{\VAR{cons}} \VAR{object})}
 165   {
 166   Replace car, or cdr, respectively, of \retval{\VAR{cons}} with \VAR{object}.
 167   }
 168
 169   \IT{(\FU*{LDIFF} \VAR{list} \VAR{foo})}
 170   {
 171   If \VAR{foo} is a tail of \VAR{list}, return \retval{preceding
 172     part of \VAR{list}}. Otherwise return \retval{\VAR{list}}.
 173   }
 174
 175   \IT{(\FU*{ADJOIN} \VAR{foo} \VAR{list}
 176     \orGOO{\xorGOO{%
 177         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 178         \kwd{:test-not} \VAR{ function}}{.}\\
 179       \kwd{:key} \VAR{ function}}{\}})}
 180   {Return \retval{\VAR{list}} if \VAR{foo} is
 181   already member of \VAR{list}. If not, return \retval{(\FU{CONS}
 182     \VAR{foo} \VAR{list})}.
 183   }
 184
 185   \IT{(\MC*{POP} \DES{\VAR{place}})}
 186   {
 187   Set \VAR{place} to (\FU{CDR} \VAR{place}), return
 188   \retval{(\FU{CAR} \VAR{place})}.
 189   }
 190
 191   \IT{(\MC*{PUSH} \VAR{foo} \DES{\VAR{place}})}
 192   {Set \VAR{place} to
 193   \retval{(\FU{cons} \VAR{foo} \VAR{place})}.
 194   }
 195
 196   \IT{(\MC*{PUSHNEW} \VAR{foo} \DES{\VAR{place}}
 197     \orGOO{\xorGOO{%
 198         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 199         \kwd{:test-not} \VAR{ function}}{.}\\
 200       \kwd{:key} \VAR{ function}}{\}})}
 201   {Set \VAR{place} to
 202   \retval{(\FU{adjoin} \VAR{foo} \VAR{place})}.
 203   }
 204
 205   \IT{\arrGOO{(\FU*{APPEND } \Op{\OPn{\VAR{list}} \VAR{ foo}})\\
 206       (\FU*{NCONC } \Op{\OPn{\DES{\VAR{list}}} \VAR{ foo}})}{.}}
 207   {
 208   Return \retval{concatenated list}. \VAR{foo} can be of any type.
 209   }
 210
 211   \IT{\arrGOO{(\FU*{REVAPPEND} \VAR{ list} \VAR{ foo})\\
 212       (\FU*{NRECONC }
 213       \DES{\VAR{list}} \VAR{ foo})}{.}}
 214   {
 215   Return \retval{concatenated list} after reversing order in
 216   \VAR{list}.
 217   }
 218
 219   \IT{(\xorGOO{\FU*{MAPCAR}\\
 220       \FU*{MAPLIST}}{\}} \VAR{function} \RP{\VAR{list}})}
 221   {
 222   Return \retval{list of return values} of \VAR{function} successively
 223   invoked with corresponding arguments, either cars or cdrs, respectively,
 224   from each \VAR{list}.
 225   }
 226
 227   \IT{(\xorGOO{\FU*{MAPCAN}\\
 228       \FU*{MAPCON}}{\}} \VAR{function} \RP{\VAR{list}})}
 229   {
 230   Return list of
 231   \retval{concatenated return values} of
 232   \VAR{function} successively invoked with corresponding arguments,
 233   either cars or cdrs, respectively,
 234   from each \VAR{list}. \VAR{function} should return a list.
 235   }
 236
 237   \IT{(\xorGOO{\FU*{MAPC}\\
 238       \FU*{MAPL}}{\}} \VAR{function} \RP{\VAR{list}})}
 239   {
 240   Return \retval{first \VAR{list}} after successively applying
 241   \VAR{function} to corresponding arguments, either cars or cdrs,
 242   respectively, from each \VAR{list}. \VAR{function} should have some side
 243   effects.
 244   }
 245
 246   \IT{(\FU*{COPY-LIST} \VAR{list})}
 247   {
 248   Return \retval{copy} of \VAR{list} with shared elements.
 249   }
 250
 251 \end{LIST}
 252
 253
 254 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 255 \subsection{Association Lists}
 256 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 257 \label{section:Association Lists}
 258 \begin{LIST}{1cm}
 259
 260   \IT{(\FU*{PAIRLIS} \VAR{keys} \VAR{values} \Op{\VAR{alist}\DF{\NIL}})}
 261   {
 262     Prepend to \retval{\VAR{alist}} an association list made from lists \VAR{keys} and \VAR{values}.
 263   }
 264
 265   \IT{(\FU*{ACONS} \VAR{key} \VAR{value} \VAR{alist})}
 266   {
 267   Return \retval{\VAR{alist}} with a (\VAR{key} \kwd{.} \VAR{value}) pair added.
 268   }
 269
 270   \IT{\arrGOO{(\xorGOO{\FU*{ASSOC}\\
 271         \FU*{RASSOC}}{\}}
 272       \VAR{ foo} \VAR{ alist }
 273       \orGOO{\xorGOO{%
 274           \kwd{:test} \VAR{ test}\DF{\kwd{\#'eql}}\\
 275           \kwd{:test-not} \VAR{ test}}{.}\\
 276         \kwd{:key} \VAR{ function}
 277       }{\}})\\
 278     (\xorGOO{\FU*{ASSOC-IF}\Op{\kwd{-NOT}}\\
 279       \FU*{RASSOC-IF}\Op{\kwd{-NOT}}}{\}} \VAR{ test} \VAR{ alist }
 280       \Op{\kwd{:key} \VAR{ function}})}{.}}
 281   {
 282 \index{ASSOC-IF-NOT}\index{RASSOC-IF-NOT}%
 283   First \retval{cons} whose car, or cdr, respectively, satisfies \VAR{test}.
 284   }
 285
 286   \IT{(\FU*{COPY-ALIST} \VAR{alist})}
 287   {
 288   Return \retval{copy} of \VAR{alist}.
 289   }
 290
 291 \end{LIST}
 292
 293
 294 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 295 \subsection{Trees}
 296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 297 \begin{LIST}{1cm}
 298
 299   \IT{(\FU*{TREE-EQUAL} \VAR{foo} \VAR{bar}
 300     \xorGOO{\kwd{:test} \VAR{ test}\DF{\kwd{\#'eql}}\\
 301       \kwd{:test-not} \VAR{ test}}{\}})}
 302   {
 303   Return \retval{\T} if trees \VAR{foo} and \VAR{bar} have same
 304   shape and leaves satisfying \VAR{test}.
 305   }
 306
 307   \IT{(\xorGOO{\FU*{SUBST} \VAR{ new} \VAR{ old } \VAR{tree}\\
 308       \FU*{NSUBST} \VAR{ new} \VAR{ old } \DES{\VAR{tree}}}{\}}
 309     \orGOO{\xorGOO{%
 310         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 311         \kwd{:test-not} \VAR{ function}}{.}\\
 312       \kwd{:key} \VAR{ function}%
 313     }{\}})}
 314   {
 315   Make \retval{copy of
 316     \VAR{tree}} with each subtree or leaf matching \VAR{old} replaced by
 317   \VAR{new}.
 318   }
 319
 320   \IT{(\xorGOO{\FU{SUBST-IF\Op{-NOT}} \VAR{ new} \VAR{ test } \VAR{tree}\\
 321       \FU{NSUBST-IF\Op{-NOT}} \VAR{ new} \VAR{ test } \DES{\VAR{tree}}}{\}}
 322     \Op{\kwd{:key} \VAR{function}})}
 323   {
 324   \index{SUBST-IF}%
 325   \index{SUBST-IF-NOT}%
 326   \index{NSUBST-IF}%
 327   \index{NSUBST-IF-NOT}%
 328   Make \retval{copy of \VAR{tree}} with each subtree or leaf
 329   satisfying \VAR{test} replaced by \VAR{new}.
 330   }
 331
 332   \IT{(\xorGOO{\FU*{SUBLIS} \VAR{ association-list } \VAR{tree} \\
 333       \FU*{NSUBLIS} \VAR{ association-list } \DES{\VAR{tree}} }{\}}
 334     \orGOO{\xorGOO{%
 335         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 336         \kwd{:test-not} \VAR{ function}}{.}\\
 337       \kwd{:key} \VAR{ function}%
 338     }{\}})}
 339   {
 340   Make \retval{copy of \VAR{tree}} with each subtree or leaf matching
 341   a key in \VAR{association-list} replaced by that key's value.
 342   }
 343
 344   \IT{(\FU*{COPY-TREE} \VAR{tree})}
 345   {
 346     \retval{Copy of \VAR{tree}} with same shape and leaves.
 347   }
 348
 349 \end{LIST}
 350
 351
 352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 353 \subsection{Sets}
 354 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 355 \begin{LIST}{1cm}
 356
 357   \IT{(\xorGOO{%
 358       \arrGOO{%
 359         \FU*{INTERSECTION}\\
 360         \FU*{SET-DIFFERENCE}\\
 361         \FU*{UNION}\\
 362         \FU*{SET-EXCLUSIVE-OR}%
 363       }{\}} \VAR{ a} \VAR{ b}\\
 364       \arrGOO{%
 365         \FU*{NINTERSECTION}\\
 366         \FU*{NSET-DIFFERENCE}%
 367       }{\}} \text{ }\DES{\VAR{a}}\text{ } \VAR{b}\\
 368       \arrGOO{%
 369         \FU*{NUNION}\\
 370         \FU*{NSET-EXCLUSIVE-OR}%
 371       }{\}} \text{ }\DES{\VAR{a}}\text{ } \DES{\VAR{b}}\text{ }
 372     }{\}}
 373     \orGOO{\xorGOO{%
 374         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 375         \kwd{:test-not} \VAR{ function}}{.}\\
 376       \kwd{:key} \VAR{ function}}{\}})}
 377   {
 378   Return \retval{$a\cap b$}, \retval{$a\setminus b$}, \retval{$a\cup b$}, or
 379   \retval{$a\,\triangle\, b$}, respectively, of lists \VAR{a} and \VAR{b}.
 380   }
 381
 382 \end{LIST}
 383
 384
 385 %%% Local Variables:
 386 %%% mode: latex
 387 %%% TeX-master: "clqr"
 388 %%% End: