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     Return \retval{\T} if \VAR{foo} is either \T\ or a cons/list.
  22
  23   \IT{(\FU*{ENDP} \VAR{list})}
  24   Return \retval{\T} if \VAR{list} is \LIT{()}.
  25
  26   \IT{(\FU*{ATOM} \VAR{foo})} Return \retval{\T} if \VAR{foo} is not a cons.
  27
  28   \IT{(\FU*{NULL} \VAR{foo})} Return \retval{\T} when \VAR{foo} is \NIL.
  29
  30   \IT{(\FU*{TAILP} \VAR{foo} \VAR{list})}
  31   Return \retval{\T} if \VAR{foo} is a tail of \VAR{list}. Return \retval{\NIL} otherwise.
  32
  33   \IT{(\xorGOO{\FU*{MEMBER}\\\FU*{MEMBER-IF}\kwd{
  34         \#'}\VAR{predicate}\\\FU*{MEMBER-IF-NOT}\kwd{ \#'}\VAR{predicate}}{\}}
  35     \VAR{foo} \VAR{list}
  36     \orGOO{\kwd{:test} \VAR{ function}\\
  37       \kwd{:test-not} \VAR{ function}\\
  38       \kwd{:key} \VAR{ function}}{\}})}
  39   Return \retval{tail of \VAR{list}} starting with
  40   first element of list matching \VAR{foo}. Return \retval{\NIL} otherwise.
  41
  42   \IT{(\FU*{SUBSETP} \VAR{foo-list} \VAR{bar-list}
  43     \orGOO{\kwd{:test} \VAR{ function}\\
  44       \kwd{:test-not} \VAR{ function}\\
  45       \kwd{:key} \VAR{ function}}{\}})}
  46   Return \retval{\T} if \VAR{foo-list} is a subset of
  47   \VAR{bar-list}. Return \retval{\NIL} otherwise.
  48
  49 \end{LIST}
  50
  51
  52 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  53 \subsection{Lists}
  54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  55 \begin{LIST}{1cm}
  56
  57   \IT{(\FU*{CONS} \VAR{foo} \VAR{bar})}
  58   Return \retval{new cons (\VAR{foo} \VAR{bar})}.
  59
  60   \IT{(\FU*{LIST} \OPn{\VAR{foo}})} Return \retval{list of \VAR{foo}s}.
  61
  62   \IT{(\FU*{LIST*} \RP{\VAR{foo}})} Return \retval{list of \VAR{foo}s}
  63   with last \VAR{foo} becoming cdr of last cons. Return
  64   \retval{\VAR{foo}} if only one \VAR{foo} given.
  65
  66   \IT{(\FU*{MAKE-LIST} \VAR{num} \Op{\kwd{:initial-element}
  67       \VAR{foo}\DF{\NIL}})} Return \retval{list with \VAR{num} elements}
  68   set to \VAR{foo}.
  69
  70   \IT{(\FU*{LIST-LENGTH} \VAR{list})} \retval{Length} of \VAR{list};
  71   \retval{\NIL} for circular \VAR{list}.
  72
  73   \IT{(\FU*{CAR} \VAR{ foo})}
  74   \retval{car of list \VAR{foo}} or \retval{\NIL} if \VAR{foo} is
  75   \NIL. \kwd{SETF}able.
  76
  77   \IT{\arrGOO{(\FU*{CDR} \VAR{ foo})\\
  78       (\FU*{REST} \VAR{ foo})}{\}}}
  79   \retval{cdr of list \VAR{foo}} or \retval{\NIL} if \VAR{foo}
  80   is \NIL. \kwd{SETF}able.
  81
  82   \IT{(\Goo{\FU*{FIRST}\XOR\FU*{SECOND}\XOR\FU*{THIRD}\XOR\dots\XOR\FU*{NINTH}\XOR\FU*{TENTH}}
  83     \VAR{foo})}
  84   \index{FOURTH}%
  85   \index{FIFTH}%
  86   \index{SIXTH}%
  87   \index{SEVENTH}%
  88   \index{EIGHTH}%
  89   Return \retval{nth element of list \VAR{foo}} if any,
  90   or \retval{\NIL} otherwise. \kwd{SETF}able.
  91
  92   \IT{(\FU{C}\VAR{X}\kwd{R} \VAR{foo})}
  93   \index{CAAR}
  94   \index{CADR}
  95   \index{CDAR}
  96   \index{CDDR}
  97   With \VAR{X} being one to four
  98   \kwd{a}s and \kwd{d}s representing \FU{CAR}s and \FU{CDR}s, e.g.
  99   (\FU{CADR} \VAR{bar}) is equivalent to (\FU{CAR} (\FU{CDR}
 100   \VAR{bar})).
 101   \kwd{SETF}able.
 102
 103   \IT{(\FU*{LAST} \VAR{foo} \Op{\VAR{num}})}
 104   Return list of \retval{last \VAR{num}
 105     conses} of list \VAR{foo}.
 106
 107   \IT{(\xorGOO{\FU*{BUTLAST}\\\FU*{NBUTLAST}}{\}} \VAR{foo} \Op{\VAR{num}})}
 108   Return \retval{list excluding last \VAR{num}
 109     conses} of list \VAR{foo}.
 110
 111   \IT{(\xorGOO{\FU*{RPLACA}\\
 112     \FU*{RPLACD}}{\}} \VAR{cons} \VAR{object})}
 113   Replace car, or cdr, resp., of \retval{\VAR{cons}} with \VAR{object}.
 114
 115   \IT{(\FU*{LDIFF} \VAR{list} \VAR{foo})}
 116   If \VAR{foo} is a tail of \VAR{list}, return \retval{preceding
 117     part of \VAR{list}}. Otherwise return \retval{\VAR{list}}.
 118
 119   \IT{(\kwd*{NTH} \VAR{n list})} Return \VAR{n}th element (zero-based) of \VAR{list}.
 120
 121   \IT{(\kwd*{NTHCDR} \VAR{n list})} Return \retval{tail of \VAR{list}} after calling \kwd{cdr} \VAR{n} times.
 122
 123   \IT{(\FU*{ADJOIN} \VAR{foo} \VAR{list} \orGOO{\kwd{:test}
 124       \VAR{ function}\\
 125       \kwd{:test-not} \VAR{ function}\\
 126       \kwd{:key} \VAR{ function}}{\}})}  Return \retval{\VAR{list}} if \VAR{foo} is
 127   already member of \VAR{list}. If not, return \retval{(\kwd{CONS}
 128     \VAR{foo} \VAR{list})}.
 129
 130   \IT{(\FU*{POP} \VAR{place})}
 131   Set \VAR{place} to \retval{(\kwd{CDR} \VAR{place})}, return
 132   \retval{(\kwd{CAR} \VAR{place})}
 133
 134   \IT{(\FU*{PUSH} \VAR{foo} \VAR{place})} Set \VAR{place} to
 135   \retval{(\kwd{cons} \VAR{foo} \VAR{place})}.
 136
 137   \IT{(\FU*{PUSHNEW} \VAR{foo} \VAR{place} )} Set \VAR{place} to
 138   \retval{(\kwd{adjoin} \VAR{foo} \VAR{place})}.
 139
 140   \IT{\arrGOO{(\FU*{APPEND} \OPn{\VAR{ list}})\\(\FU*{NCONC} \OPn{\VAR{ list}})}{\}}}
 141   Return \retval{concatenated list}. \VAR{list}s are unmodified/possibly
 142   modified, resp.
 143
 144   \IT{\arrGOO{(\FU*{REVAPPEND} \VAR{ list} \VAR{ foo})\\(\FU*{NRECONC}
 145       \VAR{ list} \VAR{ foo})}{\}}}
 146   Return \retval{concatenated list} after reversing order in
 147   \VAR{list}. \VAR{list} is unmodified/possibly
 148   modified, resp.
 149
 150   \IT{(\xorGOO{\FU*{MAPCAR}\\\FU*{MAPLIST}}{\}} \kwd{\#'}\VAR{function} \RP{\VAR{list}})}
 151   Return
 152   \retval{list of return values} of
 153   \VAR{function} successively invoked with corresponding arguments,
 154   either cars or cdrs, resp.,
 155   from each list.
 156
 157   \IT{(\xorGOO{\FU*{MAPCAN}\\\FU*{MAPCON}}{\}} \kwd{\#'}\VAR{function} \RP{\VAR{list}})}
 158   Return list of
 159   \retval{concatenated return values} of
 160   \VAR{function} successively invoked with corresponding arguments,
 161   either cars or cdrs, resp.,
 162   from each list. \VAR{function} should return a list.
 163
 164   \IT{(\xorGOO{\FU*{MAPC}\\\FU*{MAPL}}{\}} \kwd{\#'}\VAR{function} \RP{\VAR{list}})}
 165   Return
 166   \retval{first \VAR{list}} after successively applying
 167   \VAR{function} to corresponding arguments,
 168   either cars or cdrs, resp.,
 169   from each list. \VAR{function} should have some side effects.
 170
 171   \IT{(\FU*{COPY-LIST} \VAR{list})}
 172   Return \retval{copy} of \VAR{list}.
 173
 174 \end{LIST}
 175
 176
 177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 178 \subsection{Association Lists}
 179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 180 \label{section:Association Lists}
 181 \begin{LIST}{1cm}
 182
 183   \IT{(\FU*{PAIRLIS} \VAR{keys} \VAR{values})}
 184   Make \retval{association list} from lists \VAR{keys} and \VAR{values}.
 185
 186   \IT{(\FU*{ACONS} \VAR{key} \VAR{datum} \VAR{a-list})}
 187   Return \retval{\VAR{a-list}} with a (\VAR{key} . \VAR{value}) pair added.
 188
 189   \IT{\arrGOO{(\xorGOO{\FU*{ASSOC}\\
 190         \FU*{RASSOC}}{\}}%
 191       \VAR{foo} \VAR{ a-list}%
 192       \xorGOO{\kwd{:key} \VAR{ function}\\
 193         \kwd{:test} \VAR{ test}\\
 194         \kwd{:test-not} \VAR{ test}
 195       }{\}})\\
 196     (\xorGOO{\FU*{ASSOC-IF}\\
 197       \FU*{RASSOC-IF}\\
 198       \FU*{ASSOC-IF-NOT}\\
 199       \FU*{RASSOC-IF-NOT}}{\}}\VAR{test} \VAR{ a-list}%
 200       \Op{\kwd{:key} \VAR{ function}})}{\}}}
 201   First \retval{cons} whose car, or cdr, resp., satisfies \VAR{test}.
 202
 203   \IT{(\FU*{COPY-ALIST} \VAR{a-list})}
 204   Return \retval{copy} of \VAR{a-list}.
 205
 206 \end{LIST}
 207
 208
 209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 210 \subsection{Trees}
 211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 212 \begin{LIST}{1cm}
 213
 214   \IT{(\FU*{TREE-EQUAL} \VAR{foo} \VAR{bar}
 215     \orGOO{\kwd{:test} \VAR{ function}\\
 216       \kwd{:test-not} \VAR{ function}}{\}})}
 217   Return \retval{\T} if trees \VAR{foo} and \VAR{bar} have same
 218   shape and \kwd{eql} leaves, return \retval{\NIL} otherwise.
 219
 220   \IT{(\xorGOO{\FU*{SUBST}\\\FU*{NSUBST}}{\}} \VAR{new} \VAR{old} \VAR{tree}
 221     \orGOO{\kwd{:key} \VAR{ function}\\
 222       \kwd{:test} \VAR{ function}\\
 223       \kwd{:test-not} \VAR{ function}}{\}})}
 224   Make \retval{copy of
 225     \VAR{tree}} with all subtrees or leaves of \VAR{old} replaced by
 226   \VAR{new}. \VAR{tree} is unmodified/possibly modified, resp.
 227
 228   \IT{(\xorGOO{\FU{SUBST-IF\Op{-NOT}}\\\FU{NSUBST-IF\Op{-NOT}}}{\}}
 229     \VAR{new} \VAR{test} \VAR{tree}
 230     \Op{\kwd{:key} \VAR{function}})}
 231   \index{SUBST-IF}%
 232   \index{SUBST-IF-NOT}%
 233   \index{NSUBST-IF}%
 234   \index{NSUBST-IF-NOT}%
 235   Make \retval{copy of
 236     \VAR{tree}} with all subtrees or leaves
 237   satisfying test or not satisfying test, resp., replaced by
 238   \VAR{new}. \VAR{sequence} is unmodified/possibly modified, resp.
 239
 240   \IT{(\xorGOO{\FU*{SUBLIS}\\
 241       \FU*{NSUBLIS}}{\}}\VAR{a-list} \VAR{tree}\orGOO{%
 242       \kwd{:key} \VAR{ function}\\
 243       \kwd{:test} \VAR{ function}\\
 244       \kwd{:test-not} \VAR{ function}}{\}})}
 245   Make \retval{copy of \VAR{tree}} with all subtrees or leaves matching
 246   a key in \VAR{a-list} replaced by that key's object from \VAR{a-list}.
 247   \VAR{sequence} is unmodified/possibly modified, resp.
 248
 249   \IT{(\FU*{COPY-TREE} \VAR{tree})}
 250   Return \retval{copy of \VAR{tree}}.
 251
 252 \end{LIST}
 253
 254
 255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 256 \subsection{Sets}
 257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 258 \begin{LIST}{1cm}
 259
 260   \IT{(\xorGOO{\Goo{\FU*{UNION}\XOR\FU*{NUNION}}\\
 261       \Goo{\FU*{INTERSECTION}\XOR\FU*{NINTERSECTION}}\\
 262       \Goo{\FU*{SET-DIFFERENCE}\XOR\FU*{NSET-DIFFERENCE}}\\
 263       \Goo{\FU*{SET-EXCLUSIVE-OR}\XOR\FU*{NSET-EXCLUSIVE-OR}}}{\}}
 264     \VAR{a} \VAR{b}
 265     \orGOO{\kwd{:test} \VAR{ function}\\
 266       \kwd{:test-not} \VAR{ function}\\
 267       \kwd{:key} \VAR{ function}}{\}})}
 268   Return \retval{$a\cup b$}, \retval{$a\cap b$}, \retval{$a\setminus b$}, or
 269   \retval{$a\,\triangle\, b$}, resp., of lists \VAR{a} and \VAR{b}. Work
 270   non-destructively/destructively, resp.
 271
 272 \end{LIST}
 273
 274