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