clqr-conses.tex

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