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