clqr-conses.tex

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