clqr-sequences.tex

   1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   2 \section{Sequences}
   3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   4 \label{section:Sequences}
   5
   6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   7 \subsection{Sequence Predicates}
   8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   9 \begin{LIST}{1cm}
  10
  11   \IT{(\xorGOO{\FU*{EVERY}\\\FU*{NOTEVERY}}{\}} \VAR{test}
  12     \RP{\VAR{sequence}})}
  13   Return \retval{\NIL} or \retval{\T}, resp., as soon as \VAR{test} on
  14   any element of \VAR{sequence} returns \NIL.
  15
  16   \IT{(\xorGOO{\FU*{NOTANY}\\\FU*{SOME}}{\}} \VAR{test}
  17     \RP{\VAR{sequence}})}
  18   Return \retval{\NIL} or \retval{value of \VAR{test}}, resp., as soon
  19   as \VAR{test} on any element of \VAR{sequence} returns non-\NIL.
  20
  21   \IT{(\FU*{MISMATCH} \VAR{sequence-a} \VAR{sequence-b}
  22     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
  23       \kwd{:test} \VAR{ function}\\
  24       \kwd{:test-not} \VAR{ function}\\
  25       \kwd{:key} \VAR{ function}\\
  26       \kwd{:start1} \VAR{ start-sequence-a}\DF{0}\\
  27       \kwd{:end1}  \VAR{ end-sequence-a}\DF{\NIL}\\
  28       \kwd{:start2} \VAR{ start-sequence-b}\DF{0}\\
  29       \kwd{:end2} \VAR{ end-sequence-b}\DF{\NIL}}{\}})}
  30   Return \retval{position in \VAR{sequence-a}} where
  31   \VAR{sequence-a} and \VAR{sequence-b} begin to
  32   mismatch. Return \retval{\NIL} if
  33   they match entirely.
  34
  35 \end{LIST}
  36
  37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  38 \subsection{Sequence Functions}
  39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  40
  41 \begin{LIST}{1cm}
  42
  43   \IT{(\FU*{MAKE-SEQUENCE} \VAR{sequence-type} \VAR{size}
  44     \Op{\kwd{:initial-element} \VAR{foo}})}
  45   Make \retval{sequence} of \VAR{sequence-type} with \VAR{size} elements.
  46
  47   \IT{(\FU*{CONCATENATE} \VAR{type} \OPn{\VAR{sequence}})}
  48   Return \retval{concatenated sequence} of \VAR{type}.
  49
  50   \IT{(\FU*{MERGE} \VAR{type} \VAR{sequence-a}  \VAR{sequence-b} \VAR{test} \Op{\kwd{:key} \VAR{function}})}
  51   Return \retval{interleaved sequence} of \VAR{type}. \VAR{sequence-a}
  52   and \VAR{sequence-b} are possibly modified. Merged sequence  will be
  53   sorted if both  \VAR{sequence-a} and \VAR{sequence-b} are sorted.
  54
  55   \IT{(\FU*{FILL} \VAR{sequence} \VAR{foo}
  56     \orGOO{\kwd{:start} \VAR{ start}\DF{0}\\
  57       \kwd{:end} \VAR{ end}\DF{\NIL}}{\}})}
  58   Return \retval{\VAR{sequence}} with elements between \VAR{start}
  59   and \VAR{end} set to \VAR{foo}. \VAR{sequence} is modified.
  60
  61   \IT{(\FU*{LENGTH} \VAR{sequence})} Return \retval{length of
  62     \VAR{sequence}} (being value of fill pointer if applicable).
  63
  64   \IT{(\FU*{COUNT} \VAR{foo} \VAR{sequence}
  65     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
  66       \kwd{:test} \VAR{ function}\\
  67       \kwd{:test-not} \VAR{ function}\\
  68       \kwd{:start} \VAR{ start}\DF{0}\\
  69       \kwd{:end} \VAR{ end}\DF{\NIL}\\
  70       \kwd{:key} \VAR{ function}}{\}})}
  71   Return \retval{number of \VAR{foo}s in \VAR{sequence}} between \VAR{start}
  72   and \VAR{end} satisfying tests.
  73
  74   \IT{(\xorGOO{\FU*{COUNT-IF}\\
  75       \FU*{COUNT-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
  76     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
  77       \kwd{:start} \VAR{ start}\DF{0}\\
  78       \kwd{:end} \VAR{ end}\DF{\NIL}\\
  79       \kwd{:key} \VAR{ function}}{\}})}
  80   Return \retval{number of elements in \VAR{sequence}} between \VAR{start}
  81   and \VAR{end} satisfying \VAR{test}.
  82
  83   \IT{(\FU*{ELT} \VAR{sequence} \VAR{index})} Return \retval{element of
  84     \VAR{sequence}} pointed to by \VAR{index}. \kwd{setf}able.
  85
  86   \IT{(\FU*{SUBSEQ} \VAR{sequence} \VAR{start} \Op{\VAR{end}\DF{\NIL}})}
  87   Return \retval{subsequence of \VAR{sequence}} between \VAR{start}
  88     and \VAR{end}. \kwd{setf}able.
  89
  90   \IT{(\xorGOO{\FU*{SORT}\\\FU*{STABLE-SORT}}{\}} \VAR{sequence} \VAR{test}
  91     \Op{\kwd{:key} \VAR{function}})}
  92   Return \retval{sorted sequence}. \VAR{sequence} is modified. Order
  93   of elements considered equal is not guaranteed/retained, resp.
  94
  95   \IT{\arrGOO{(\FU*{REVERSE} \VAR{ sequence})\\(\FU*{NREVERSE} \VAR{ sequence})}{\}}}
  96   Return \retval{\VAR{sequence} in reverse order}. \VAR{sequence} is
  97   unmodified/possibly modified, resp.
  98
  99   \IT{(\xorGOO{\FU*{FIND}\\\FU*{POSITION}}{\}} \VAR{foo} \VAR{sequence}
 100     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 101       \kwd{:test} \VAR{ function}\\
 102       \kwd{:test-not} \VAR{ function}\\
 103       \kwd{:start} \VAR{ start}\DF{0}\\
 104       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 105       \kwd{:key} \VAR{ function}}{\}})}
 106   Return \retval{first element found in \VAR{sequence}}, or
 107   \retval{its position} relative to \VAR{sequence}'s start, resp., between \VAR{start}
 108   and \VAR{end} satisfying tests.
 109
 110   \IT{(\xorGOO{\FU*{FIND-IF}\\\FU*{FIND-IF-NOT}\\\FU*{POSITION-IF}\\\FU*{POSITION-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
 111     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 112       \kwd{:start} \VAR{ start}\DF{0}\\
 113       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 114       \kwd{:key} \VAR{ function}}{\}})}
 115   Return \retval{first element in \VAR{sequence}}, or
 116   \retval{its position} relative to \VAR{sequence}'s start, resp., between \VAR{start}
 117   and \VAR{end} satisfying \VAR{test}.
 118
 119   \IT{(\FU*{SEARCH} \VAR{sequence-a} \VAR{sequence-b}
 120     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 121       \kwd{:test} \VAR{ function}\\
 122       \kwd{:test-not} \VAR{ function}\\
 123       \kwd{:start1} \VAR{ start-a}\DF{0}\\
 124       \kwd{:start2} \VAR{ start-b}\DF{0}\\
 125       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 126       \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
 127       \kwd{:key} \VAR{ function}}{\}})}
 128   Search \VAR{sequence-b} for a subsequence matching
 129   \VAR{sequence-a}. Return \retval{index} in \VAR{sequence-b}, or
 130   \retval{\NIL}.
 131
 132   \IT{(\xorGOO{\FU*{REMOVE}\\\FU*{DELETE}}{\}} \VAR{foo} \VAR{sequence}
 133     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{0}\\
 134       \kwd{:test} \VAR{ function}\\
 135       \kwd{:test-not} \VAR{ function}\\
 136       \kwd{:start} \VAR{ start}\DF{0}\\
 137       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 138       \kwd{:key} \VAR{ function}\\
 139       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 140   Make \retval{copy of \VAR{sequence}} without elements matching
 141   \VAR{foo}. \VAR{sequence} is unmodified/possibly modified, resp.
 142
 143   \IT{(\xorGOO{\FU*{REMOVE-IF}\\\FU*{REMOVE-IF-NOT}\\
 144       \FU*{DELETE-IF}\\\FU*{DELETE-IF-NOT}}{\}}
 145     \VAR{test} \VAR{sequence}
 146     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 147       \kwd{:start} \VAR{ start}\DF{0}\\
 148       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 149       \kwd{:key} \VAR{ function}\\
 150       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 151   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count}) elements
 152   satisfying test or not satisfying test, resp., removed.
 153   \VAR{sequence} is unmodified/possibly modified, resp.
 154
 155   \IT{(\xorGOO{\FU*{REMOVE-DUPLICATES}\\\FU*{DELETE-DUPLICATES}}{\}} \VAR{sequence}
 156     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 157       \kwd{:test} \VAR{ function}\\
 158       \kwd{:test-not} \VAR{ function}\\
 159       \kwd{:start} \VAR{ start}\DF{0}\\
 160       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 161       \kwd{:key} \VAR{ function}\DF{\NIL}}{\}})}
 162   Make \retval{copy of
 163     \VAR{sequence}} without duplicates. \VAR{sequence} is unmodified/possibly
 164   modified, resp.
 165
 166   \IT{(\xorGOO{\FU*{SUBSTITUTE}\\\FU*{NSUBSTITUTE}}{\}} \VAR{new}
 167     \VAR{old} \VAR{foo} \VAR{sequence}
 168     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 169       \kwd{:test} \VAR{ function}\\
 170       \kwd{:test-not} \VAR{ function}\\
 171       \kwd{:start} \VAR{ start}\DF{0}\\
 172       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 173       \kwd{:key} \VAR{ function}\\
 174       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 175   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 176   \VAR{old}s replaced by \VAR{new}. \VAR{sequence} is
 177   unmodified/possibly modified, resp.
 178
 179   \IT{(\xorGOO{\FU*{SUBSTITUTE-IF}\\\FU*{SUBSTITUTE-IF-NOT}\\
 180       \FU*{NSUBSTITUTE-IF}\\\FU*{NSUBSTITUTE-IF-NOT}}{\}}
 181     \VAR{new} \VAR{test} \VAR{sequence}
 182     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 183       \kwd{:start} \VAR{ start}\DF{0}\\
 184       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 185       \kwd{:key} \VAR{ function}\\
 186       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 187   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 188   elements satisfying test or not satisfying test, resp., replaced by
 189   \VAR{new}. \VAR{sequence} is unmodified/possibly modified, resp.
 190
 191   \IT{(\FU*{REPLACE} \VAR{sequence-a} \VAR{sequence-b}
 192     \orGOO{\kwd{:start1} \VAR{ start-a}\DF{0}\\
 193       \kwd{:start2} \VAR{ start-b}\DF{0}\\
 194       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 195       \kwd{:end2} \VAR{ end-b}\DF{\NIL}}{\}})}
 196     Destructively replace elements of \retval{\VAR{sequence-a}} with elements of
 197     \VAR{sequence-b}.
 198
 199   \IT{(\FU*{MAP} \VAR{type} \VAR{function} \RP{\VAR{sequence}})}
 200   Apply \VAR{function} successively to corresponding elements of the
 201   \VAR{sequence}s. Return values as a \retval{sequence of
 202     \VAR{type}}. If \VAR{type} is \NIL, return \retval{\NIL}.
 203
 204   \IT{(\FU*{MAP-INTO} \VAR{result-sequence} \VAR{function} \RP{\VAR{sequence}})}
 205   Modify \retval{\VAR{result-sequence}} successively by applying
 206   \VAR{function} to corresponding elements of the \VAR{sequence}s.
 207
 208   \IT{(\FU*{REDUCE} \VAR{function} \VAR{sequence}
 209     \orGOO{\kwd{:initial-value} \VAR{ foo}\DF{\NIL}\\
 210       \kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 211       \kwd{:start} \VAR{ start}\DF{0}\\
 212       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 213       \kwd{:key} \VAR{ function}}{\}})}
 214   Starting with the first two elements of \VAR{sequence}, apply
 215   \VAR{function} successively to its last return value together with the next
 216   element of \VAR{sequence}. Return \retval{last value of {function}}.
 217
 218   \IT{(\FU*{COPY-SEQ} \VAR{sequence})}
 219   Return \retval{copy of \VAR{sequence}} with the same elements.
 220
 221
 222 \end{LIST}
 223
 224