clqr-sequences.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{Sequences}
  12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  13 \label{section:Sequences}
  14
  15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  16 \subsection{Sequence Predicates}
  17 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  18 \begin{LIST}{1cm}
  19
  20   \IT{(\xorGOO{\FU*{EVERY}\\
  21       \FU*{NOTEVERY}}{\}} \VAR{test}
  22     \RP{\VAR{sequence}})}
  23   {
  24   Return \retval{\NIL} or \retval{\T}, respectively, as soon as \VAR{test} on
  25   any set of corresponding elements of \VAR{sequence}s returns \NIL.
  26   }
  27
  28   \IT{(\xorGOO{\FU*{SOME}\\
  29       \FU*{NOTANY}}{\}} \VAR{test}
  30     \RP{\VAR{sequence}})}
  31   {
  32   Return \retval{value of \VAR{test}} or \retval{\NIL}, respectively, as soon
  33   as \VAR{test} on any set of elements of \VAR{sequence}s returns non-\NIL.
  34   }
  35
  36   \IT{(\FU*{MISMATCH} \VAR{sequence-a} \VAR{sequence-b}
  37     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
  38       \kwd{:test} \VAR{ function}\\
  39       \kwd{:test-not} \VAR{ function}\\
  40       \kwd{:start1} \VAR{ start-a}\DF{0}\\
  41       \kwd{:start2} \VAR{ start-b}\DF{0}\\
  42       \kwd{:end1}  \VAR{ end-a}\DF{\NIL}\\
  43       \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
  44       \kwd{:key} \VAR{ function}}{\}})}
  45   {
  46   Return \retval{position in \VAR{sequence-a}} where
  47   \VAR{sequence-a} and \VAR{sequence-b} begin to
  48   mismatch. Return \retval{\NIL} if
  49   they match entirely.
  50   }
  51
  52 \end{LIST}
  53
  54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  55 \subsection{Sequence Functions}
  56 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  57
  58 \begin{LIST}{1cm}
  59
  60   \IT{(\FU*{MAKE-SEQUENCE} \VAR{sequence-type} \VAR{size}
  61     \Op{\kwd{:initial-element} \VAR{foo}})}
  62   {
  63   Make \retval{sequence} of \VAR{sequence-type} with \VAR{size} elements.
  64   }
  65
  66   \IT{(\FU*{CONCATENATE} \VAR{type} \OPn{\VAR{sequence}})}
  67   {
  68   Return \retval{concatenated sequence} of \VAR{type}.
  69   }
  70
  71   \IT{(\FU*{MERGE} \VAR{type} \VAR{sequence-a}  \VAR{sequence-b}
  72     \VAR{test} \Op{\kwd{:key} \VAR{function}})}
  73   {
  74   Return \retval{interleaved sequence} of \VAR{type}. \VAR{sequence-a}
  75   and \VAR{sequence-b} are possibly modified. Merged sequence  will be
  76   sorted if both  \VAR{sequence-a} and \VAR{sequence-b} are sorted.
  77   }
  78
  79   \IT{(\FU*{FILL} \VAR{sequence} \VAR{foo}
  80     \orGOO{\kwd{:start} \VAR{ start}\DF{0}\\
  81       \kwd{:end} \VAR{ end}\DF{\NIL}}{\}})}
  82   {
  83   Return \retval{\VAR{sequence}} after setting elements between \VAR{start}
  84   and \VAR{end} to \VAR{foo}.
  85   }
  86
  87   \IT{(\FU*{LENGTH} \VAR{sequence})}
  88   {Return \retval{length of
  89     \VAR{sequence}} (being value of fill pointer if applicable).
  90     }
  91
  92   \IT{(\FU*{COUNT} \VAR{foo} \VAR{sequence}
  93     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
  94       \kwd{:test} \VAR{ function}\\
  95       \kwd{:test-not} \VAR{ function}\\
  96       \kwd{:start} \VAR{ start}\DF{0}\\
  97       \kwd{:end} \VAR{ end}\DF{\NIL}\\
  98       \kwd{:key} \VAR{ function}}{\}})}
  99   {
 100   Return \retval{number of \VAR{foo}s in \VAR{sequence}} between \VAR{start}
 101   and \VAR{end} satisfying tests.
 102   }
 103
 104   \IT{(\xorGOO{\FU*{COUNT-IF}\\
 105       \FU*{COUNT-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
 106     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 107       \kwd{:start} \VAR{ start}\DF{0}\\
 108       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 109       \kwd{:key} \VAR{ function}}{\}})}
 110   {
 111   Return \retval{number of elements in \VAR{sequence}} between \VAR{start}
 112   and \VAR{end} satisfying \VAR{test}.
 113   }
 114
 115   \IT{(\FU*{ELT} \VAR{sequence} \VAR{index})}
 116   {Return \retval{element of
 117     \VAR{sequence}} pointed to by zero-indexed \VAR{index}. \kwd{setf}able.
 118     }
 119
 120   \IT{(\FU*{SUBSEQ} \VAR{sequence} \VAR{start}
 121     \Op{\VAR{end}\DF{\NIL}})}
 122   {
 123   Return \retval{subsequence of \VAR{sequence}} between \VAR{start}
 124     and \VAR{end}. \kwd{setf}able.
 125     }
 126
 127   \IT{(\xorGOO{\FU*{SORT}\\
 128       \FU*{STABLE-SORT}}{\}} \VAR{sequence} \VAR{test}
 129     \Op{\kwd{:key} \VAR{function}})}
 130   {
 131   Return \retval{\VAR{sequence} sorted}. \VAR{sequence} is modified. Order
 132   of elements considered equal is not guaranteed/retained, respectively.
 133   }
 134
 135   \IT{\arrGOO{(\FU*{REVERSE} \VAR{ sequence})\\(\FU*{NREVERSE} \VAR{
 136         sequence})}{.}}
 137   {
 138   Return \retval{\VAR{sequence} in reverse order}. \VAR{sequence} is
 139   unmodified/possibly modified, respectively.
 140   }
 141
 142   \IT{(\xorGOO{\FU*{FIND}\\
 143       \FU*{POSITION}}{\}} \VAR{foo} \VAR{sequence}
 144     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 145       \kwd{:test} \VAR{ function}\\
 146       \kwd{:test-not} \VAR{ function}\\
 147       \kwd{:start} \VAR{ start}\DF{0}\\
 148       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 149       \kwd{:key} \VAR{ function}}{\}})}
 150   {
 151   Return \retval{first element} found in \VAR{sequence}, or
 152   its \retval{position} relative to \VAR{sequence}'s start, respectively,
 153   between \VAR{start} and \VAR{end} satisfying tests.
 154   }
 155
 156   \IT{(\xorGOO{\FU*{FIND-IF}\\\FU*{FIND-IF-NOT}\\\FU*{POSITION-IF}\\\FU*{POSITION-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
 157     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 158       \kwd{:start} \VAR{ start}\DF{0}\\
 159       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 160       \kwd{:key} \VAR{ function}}{\}})}
 161   {
 162   Return \retval{first element in \VAR{sequence}}, or
 163   \retval{its position} relative to \VAR{sequence}'s start, respectively, between \VAR{start}
 164   and \VAR{end} satisfying \VAR{test}.
 165   }
 166
 167   \IT{(\FU*{SEARCH} \VAR{sequence-a} \VAR{sequence-b}
 168     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 169       \kwd{:test} \VAR{ function}\\
 170       \kwd{:test-not} \VAR{ function}\\
 171       \kwd{:start1} \VAR{ start-a}\DF{0}\\
 172       \kwd{:start2} \VAR{ start-b}\DF{0}\\
 173       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 174       \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
 175       \kwd{:key} \VAR{ function}}{\}})}
 176   {
 177   Search \VAR{sequence-b} for a subsequence matching
 178   \VAR{sequence-a}. Return \retval{position} in \VAR{sequence-b}, or
 179   \retval{\NIL}.
 180   }
 181
 182   \IT{(\xorGOO{\FU*{REMOVE}\\\FU*{DELETE}}{\}} \VAR{foo} \VAR{sequence}
 183     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 184       \kwd{:test} \VAR{ function}\\
 185       \kwd{:test-not} \VAR{ function}\\
 186       \kwd{:start} \VAR{ start}\DF{0}\\
 187       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 188       \kwd{:key} \VAR{ function}\\
 189       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 190   {
 191   Make \retval{copy of \VAR{sequence}} without elements matching
 192   \VAR{foo}. \VAR{sequence} is unmodified/possibly modified, respectively.
 193   }
 194
 195   \IT{(\xorGOO{\FU*{REMOVE-IF}\\\FU*{REMOVE-IF-NOT}\\
 196       \FU*{DELETE-IF}\\\FU*{DELETE-IF-NOT}}{\}}
 197     \VAR{test} \VAR{sequence}
 198     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 199       \kwd{:start} \VAR{ start}\DF{0}\\
 200       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 201       \kwd{:key} \VAR{ function}\\
 202       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 203   {
 204   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count}) elements
 205   satisfying test removed.
 206   \VAR{sequence} is unmodified/possibly modified, respectively.
 207   }
 208
 209   \IT{(\xorGOO{\FU*{REMOVE-DUPLICATES}\\\FU*{DELETE-DUPLICATES}}{\}} \VAR{sequence}
 210     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 211       \kwd{:test} \VAR{ function}\\
 212       \kwd{:test-not} \VAR{ function}\\
 213       \kwd{:start} \VAR{ start}\DF{0}\\
 214       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 215       \kwd{:key} \VAR{ function}}{\}})}
 216   {
 217   Make \retval{copy of
 218     \VAR{sequence}} without duplicates. \VAR{sequence} is unmodified/possibly
 219   modified, respectively.
 220   }
 221
 222   \IT{(\xorGOO{\FU*{SUBSTITUTE}\\
 223       \FU*{NSUBSTITUTE}}{\}} \VAR{new}
 224     \VAR{old} \VAR{sequence}
 225     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 226       \kwd{:test} \VAR{ function}\\
 227       \kwd{:test-not} \VAR{ function}\\
 228       \kwd{:start} \VAR{ start}\DF{0}\\
 229       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 230       \kwd{:key} \VAR{ function}\\
 231       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 232   {
 233   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 234   \VAR{old}s replaced by \VAR{new}. \VAR{sequence} is
 235   unmodified/possibly modified, respectively.
 236   }
 237
 238   \IT{(\xorGOO{\FU*{SUBSTITUTE-IF}\\\FU*{SUBSTITUTE-IF-NOT}\\
 239       \FU*{NSUBSTITUTE-IF}\\\FU*{NSUBSTITUTE-IF-NOT}}{\}}
 240     \VAR{new} \VAR{test} \VAR{sequence}
 241     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 242       \kwd{:start} \VAR{ start}\DF{0}\\
 243       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 244       \kwd{:key} \VAR{ function}\\
 245       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 246   {
 247   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 248   elements satisfying test replaced by
 249   \VAR{new}. \VAR{sequence} is unmodified/possibly modified, respectively.
 250   }
 251
 252   \IT{(\FU*{REPLACE} \VAR{sequence-a} \VAR{sequence-b}
 253     \orGOO{\kwd{:start1} \VAR{ start-a}\DF{0}\\
 254       \kwd{:start2} \VAR{ start-b}\DF{0}\\
 255       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 256       \kwd{:end2} \VAR{ end-b}\DF{\NIL}}{\}})}
 257   {
 258     Destructively replace elements of \retval{\VAR{sequence-a}} with elements of
 259     \VAR{sequence-b}.
 260     }
 261
 262   \IT{(\FU*{MAP} \VAR{type} \VAR{function} \RP{\VAR{sequence}})}
 263   {
 264   Apply \VAR{function} successively to corresponding elements of the
 265   \VAR{sequence}s. Return values as a \retval{sequence} of
 266     \VAR{type}. If \VAR{type} is \NIL, return \retval{\NIL}.
 267   }
 268
 269   \IT{(\FU*{MAP-INTO} \VAR{result-sequence} \VAR{function}
 270     \RP{\VAR{sequence}})}
 271   {
 272   Store into \retval{\VAR{result-sequence}} successively values of
 273   \VAR{function} applied to corresponding elements of the \VAR{sequence}s.
 274   }
 275
 276   \IT{(\FU*{REDUCE} \VAR{function} \VAR{sequence}
 277     \orGOO{\kwd{:initial-value} \VAR{ foo}\DF{\NIL}\\
 278       \kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 279       \kwd{:start} \VAR{ start}\DF{0}\\
 280       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 281       \kwd{:key} \VAR{ function}}{\}})}
 282   {
 283   Starting with the first two elements of \VAR{sequence}, apply
 284   \VAR{function} successively to its last return value together with the next
 285   element of \VAR{sequence}. Return \retval{last value} of {function}.
 286   }
 287
 288   \IT{(\FU*{COPY-SEQ} \VAR{sequence})}
 289   {
 290   Return \retval{copy of \VAR{sequence}} with the same elements.
 291   }
 292
 293
 294 \end{LIST}
 295
 296