clqr-conses.tex

   1 % Copyright (C) 2008 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{(\FU*{ENDP} \VAR{list})}
  26   {
  27   Return \retval{\T} if \VAR{list} is \NIL.
  28   }
  29
  30   \IT{(\FU*{NULL} \VAR{foo})}
  31   {Return \retval{\T} if \VAR{foo} is \NIL.
  32     }
  33
  34   \IT{(\FU*{ATOM} \VAR{foo})}
  35   {Return \retval{\T} if \VAR{foo} is not a
  36   \kwd{cons}.
  37   }
  38
  39   \IT{(\FU*{TAILP} \VAR{foo} \VAR{list})}
  40   {
  41   Return \retval{\T} if \VAR{foo} is a tail of \VAR{list}.
  42   }
  43
  44   \IT{(\FU*{MEMBER} \VAR{foo} \VAR{list}
  45     \orGOO{\kwd{:test} \VAR{ function}\\
  46       \kwd{:test-not} \VAR{ function}\\
  47       \kwd{:key} \VAR{ function}}{\}})}
  48   {
  49   Return \retval{tail of \VAR{list}} starting with
  50   its first element matching \VAR{foo}. Return \retval{\NIL} if
  51   there is no such element.
  52   }
  53
  54   \IT{(\xorGOO{\FU*{MEMBER-IF}\\
  55       \FU*{MEMBER-IF-NOT}}{\}}
  56     \VAR{test} \VAR{list}
  57     \Op{\kwd{:key} \VAR{function}})}
  58   {
  59   Return \retval{tail of \VAR{list}} starting with
  60   its first element satisfying \VAR{test}. Return \retval{\NIL} if
  61   there is no such element.
  62   }
  63
  64   \IT{(\FU*{SUBSETP} \VAR{list-a} \VAR{list-b}
  65     \orGOO{\kwd{:test} \VAR{ function}\\
  66       \kwd{:test-not} \VAR{ function}\\
  67       \kwd{:key} \VAR{ function}}{\}})}
  68   {
  69   Return \retval{\T} if \VAR{list-a} is a subset of
  70   \VAR{list-b}.
  71   }
  72
  73 \end{LIST}
  74
  75
  76 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  77 \subsection{Lists}
  78 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  79 \begin{LIST}{1cm}
  80
  81   \IT{(\FU*{CONS} \VAR{foo} \VAR{bar})}
  82   {
  83   Return new cons \retval{(\VAR{foo} \kwd {.} \VAR{bar})}.
  84   }
  85
  86   \IT{(\FU*{LIST} \OPn{\VAR{foo}})}
  87   {Return \retval{list of \VAR{foo}s}.
  88     }
  89
  90   \IT{(\FU*{LIST\A} \RP{\VAR{foo}})}
  91   {Return \retval{list of \VAR{foo}s}
  92   with last \VAR{foo} becoming cdr of last cons. Return
  93   \retval{\VAR{foo}} if only one \VAR{foo} given.
  94   }
  95
  96   \IT{(\FU*{MAKE-LIST} \VAR{num} \Op{\kwd{:initial-element}
  97       \VAR{foo}\DF{\NIL}})}
  98   {
  99     New \retval{list} with \VAR{num} elements set to \VAR{foo}.
 100   }
 101
 102   \IT{(\FU*{LIST-LENGTH} \VAR{list})}
 103   {\retval{Length} of \VAR{list};
 104   \retval{\NIL} for circular \VAR{list}.
 105   }
 106
 107   \IT{(\FU*{CAR} \VAR{list})}
 108   {
 109   \retval{car of \VAR{list}} or \retval{\NIL} if \VAR{list} is
 110   \NIL. \kwd{SETF}able.
 111   }
 112
 113   \IT{\arrGOO{(\FU*{CDR} \VAR{ list})\\
 114       (\FU*{REST} \VAR{ list})}{.}}
 115   {
 116   \retval{cdr of \VAR{list}} or \retval{\NIL} if \VAR{list}
 117   is \NIL. \kwd{SETF}able.
 118   }
 119
 120   \IT{(\FU*{NTHCDR} \VAR{n list})}
 121   {Return \retval{tail of \VAR{list}} after calling \FU{cdr} \VAR{n} times.
 122     }
 123
 124   \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}}
 125     \VAR{list})}
 126   {
 127   \index{SEVENTH}%
 128   \index{EIGHTH}%
 129   Return \retval{nth element of \VAR{list}} if any,
 130   or \retval{\NIL} otherwise. \kwd{SETF}able.
 131   }
 132
 133   \IT{(\FU*{NTH} \VAR{n list})}
 134   {Return zero-indexed \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   Return \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} \orGOO{\kwd{:test}
 177       \VAR{ function}\\
 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{(\FU*{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{(\FU*{PUSH} \VAR{foo} \DES{\VAR{place}})}
 192   {Set \VAR{place} to
 193   \retval{(\FU{cons} \VAR{foo} \VAR{place})}.
 194   }
 195
 196   \IT{(\FU*{PUSHNEW} \VAR{foo} \DES{\VAR{place}}  \orGOO{\kwd{:test}
 197       \VAR{ function}\\
 198       \kwd{:test-not} \VAR{ function}\\
 199       \kwd{:key} \VAR{ function}}{\}})}
 200   {Set \VAR{place} to
 201   \retval{(\FU{adjoin} \VAR{foo} \VAR{place})}.
 202   }
 203
 204   \IT{\arrGOO{(\FU*{APPEND } \Op{\OPn{\VAR{list}} \VAR{ foo}})\\
 205       (\FU*{NCONC } \Op{\OPn{\DES{\VAR{list}}} \VAR{ foo}})}{.}}
 206   {
 207   Return \retval{concatenated list}. \VAR{foo} can be of any type.
 208   }
 209
 210   \IT{\arrGOO{(\FU*{REVAPPEND} \VAR{ list} \VAR{ foo})\\
 211       (\FU*{NRECONC }
 212       \DES{\VAR{list}} \VAR{ foo})}{.}}
 213   {
 214   Return \retval{concatenated list} after reversing order in
 215   \VAR{list}.
 216   }
 217
 218   \IT{(\xorGOO{\FU*{MAPCAR}\\
 219       \FU*{MAPLIST}}{\}} \VAR{function} \RP{\VAR{list}})}
 220   {
 221   Return \retval{list of return values} of \VAR{function} successively
 222   invoked with corresponding arguments, either cars or cdrs, respectively,
 223   from each \VAR{list}.
 224   }
 225
 226   \IT{(\xorGOO{\FU*{MAPCAN}\\
 227       \FU*{MAPCON}}{\}} \VAR{function} \RP{\VAR{list}})}
 228   {
 229   Return list of
 230   \retval{concatenated return values} of
 231   \VAR{function} successively invoked with corresponding arguments,
 232   either cars or cdrs, respectively,
 233   from each \VAR{list}. \VAR{function} should return a list.
 234   }
 235
 236   \IT{(\xorGOO{\FU*{MAPC}\\
 237       \FU*{MAPL}}{\}} \VAR{function} \RP{\VAR{list}})}
 238   {
 239   Return \retval{first \VAR{list}} after successively applying
 240   \VAR{function} to corresponding arguments, either cars or cdrs,
 241   respectively, from each \VAR{list}. \VAR{function} should have some side
 242   effects.
 243   }
 244
 245   \IT{(\FU*{COPY-LIST} \VAR{list})}
 246   {
 247   Return \retval{copy} of \VAR{list}.
 248   }
 249
 250 \end{LIST}
 251
 252
 253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 254 \subsection{Association Lists}
 255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 256 \label{section:Association Lists}
 257 \begin{LIST}{1cm}
 258
 259   \IT{(\FU*{PAIRLIS} \VAR{keys} \VAR{values} \Op{\VAR{alist}\DF{\NIL}})}
 260   {
 261     Prepend to \retval{\VAR{alist}} an association list made from lists \VAR{keys} and \VAR{values}.
 262   }
 263
 264   \IT{(\FU*{ACONS} \VAR{key} \VAR{value} \VAR{alist})}
 265   {
 266   Return \retval{\VAR{alist}} with a (\VAR{key} \kwd{.} \VAR{value}) pair added.
 267   }
 268
 269   \IT{\arrGOO{(\xorGOO{\FU*{ASSOC}\\
 270         \FU*{RASSOC}}{\}}
 271       \VAR{ foo} \VAR{ alist }
 272       \xorGOO{\kwd{:key} \VAR{ function}\\
 273         \kwd{:test} \VAR{ test}\\
 274         \kwd{:test-not} \VAR{ test}
 275       }{\}})\\
 276     (\xorGOO{\FU*{ASSOC-IF}\Op{\kwd{-NOT}}\\
 277       \FU*{RASSOC-IF}\Op{\kwd{-NOT}}}{\}} \VAR{ test} \VAR{ alist }
 278       \Op{\kwd{:key} \VAR{ function}})}{.}}
 279   {
 280 \index{ASSOC-IF-NOT}\index{RASSOC-IF-NOT}%
 281   First \retval{cons} whose car, or cdr, respectively, satisfies \VAR{test}.
 282   }
 283
 284   \IT{(\FU*{COPY-ALIST} \VAR{alist})}
 285   {
 286   Return \retval{copy} of \VAR{alist}.
 287   }
 288
 289 \end{LIST}
 290
 291
 292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 293 \subsection{Trees}
 294 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 295 \begin{LIST}{1cm}
 296
 297   \IT{(\FU*{TREE-EQUAL} \VAR{foo} \VAR{bar}
 298     \orGOO{\kwd{:test} \VAR{ function}\\
 299       \kwd{:test-not} \VAR{ function}}{\}})}
 300   {
 301   Return \retval{\T} if trees \VAR{foo} and \VAR{bar} have same
 302   shape and \kwd{eql} leaves.
 303   }
 304
 305   \IT{(\xorGOO{\FU*{SUBST} \VAR{ new} \VAR{ old } \VAR{tree}\\
 306       \FU*{NSUBST} \VAR{ new} \VAR{ old } \DES{\VAR{tree}}}{\}}
 307     \orGOO{\kwd{:key} \VAR{ function}\\
 308       \kwd{:test} \VAR{ function}\\
 309       \kwd{:test-not} \VAR{ function}}{\}})}
 310   {
 311   Make \retval{copy of
 312     \VAR{tree}} with each subtree or leaf matching \VAR{old} replaced by
 313   \VAR{new}.
 314   }
 315
 316   \IT{(\xorGOO{\FU{SUBST-IF\Op{-NOT}} \VAR{ new} \VAR{ test } \VAR{tree}\\
 317       \FU{NSUBST-IF\Op{-NOT}} \VAR{ new} \VAR{ test } \DES{\VAR{tree}}}{\}}
 318     \Op{\kwd{:key} \VAR{function}})}
 319   {
 320   \index{SUBST-IF}%
 321   \index{SUBST-IF-NOT}%
 322   \index{NSUBST-IF}%
 323   \index{NSUBST-IF-NOT}%
 324   Make \retval{copy of \VAR{tree}} with each subtree or leaf
 325   satisfying \VAR{test} replaced by \VAR{new}.
 326   }
 327
 328   \IT{(\xorGOO{\FU*{SUBLIS} \VAR{ association-list } \VAR{tree} \\
 329       \FU*{NSUBLIS} \VAR{ association-list } \DES{\VAR{tree}} }{\}}
 330     \orGOO{%
 331       \kwd{:key} \VAR{ function}\\
 332       \kwd{:test} \VAR{ function}\\
 333       \kwd{:test-not} \VAR{ function}}{\}})}
 334   {
 335   Make \retval{copy of \VAR{tree}} with each subtree or leaf matching
 336   a key in \VAR{association-list} replaced by that key's value.
 337   }
 338
 339   \IT{(\FU*{COPY-TREE} \VAR{tree})}
 340   {
 341     \retval{Copy of \VAR{tree}} with same shape and leaves.
 342   }
 343
 344 \end{LIST}
 345
 346
 347 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 348 \subsection{Sets}
 349 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 350 \begin{LIST}{1cm}
 351
 352   \IT{(\xorGOO{%
 353       \arrGOO{%
 354         \FU*{UNION}\\
 355         \FU*{INTERSECTION}\\
 356         \FU*{SET-DIFFERENCE}\\
 357         \FU*{SET-EXCLUSIVE-OR}%
 358       }{\}} \VAR{ a} \VAR{ b}\\
 359       \arrGOO{%
 360         \FU*{NUNION}\\
 361         \FU*{NINTERSECTION}\\
 362         \FU*{NSET-DIFFERENCE}\\
 363         \FU*{NSET-EXCLUSIVE-OR}%
 364       }{\}} \text{ }\DES{\VAR{a}}\text{ } \DES{\VAR{b}}\text{ }
 365     }{\}}
 366     \orGOO{\kwd{:test} \VAR{ function}\\
 367       \kwd{:test-not} \VAR{ function}\\
 368       \kwd{:key} \VAR{ function}}{\}})}
 369   {
 370   Return \retval{$a\cup b$}, \retval{$a\cap b$}, \retval{$a\setminus b$}, or
 371   \retval{$a\,\triangle\, b$}, respectively, of lists \VAR{a} and \VAR{b}.
 372   }
 373
 374 \end{LIST}
 375
 376