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[Seq.~Predicates]{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{\LIT{0}}\\
  41       \kwd{:start2} \VAR{ start-b}\DF{\LIT{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[Seq.~Functions]{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}})} % default: implementation-dependent
  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} \DES{\VAR{sequence-a}} \DES{\VAR{sequence-b}}
  72     \VAR{test} \Op{\kwd{:key} \VAR{function}\DF{\NIL}})}
  73   {
  74   Return \retval{interleaved sequence} of \VAR{type}. Merged sequence
  75   will be sorted if both  \VAR{sequence-a} and \VAR{sequence-b} are
  76   sorted.
  77   }
  78
  79   \IT{(\FU*{FILL} \DES{\VAR{sequence}} \VAR{foo}
  80     \orGOO{\kwd{:start} \VAR{ start}\DF{\LIT{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{\LIT{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} which satisfy
 101   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{\LIT{0}}\\
 108       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 109       \kwd{:key} \VAR{ function}}{\}})}
 110   {
 111   Return \retval{number of elements} in \VAR{sequence} which satisfy
 112   \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
 118     \VAR{index}. \kwd{setf}able.
 119     }
 120
 121   \IT{(\FU*{SUBSEQ} \VAR{sequence} \VAR{start}
 122     \Op{\VAR{end}\DF{\NIL}})}
 123   {
 124   Return \retval{subsequence of \VAR{sequence}} between \VAR{start}
 125     and \VAR{end}. \kwd{setf}able.
 126     }
 127
 128   \IT{(\xorGOO{\FU*{SORT}\\
 129       \FU*{STABLE-SORT}}{\}} \DES{\VAR{sequence}} \VAR{test}
 130     \Op{\kwd{:key} \VAR{function}})}
 131   {
 132   Return \retval{\VAR{sequence} sorted}. Order
 133   of elements considered equal is not guaranteed/retained, respectively.
 134   }
 135
 136   \IT{\arrGOO{(\FU*{REVERSE} \VAR{ sequence})\\
 137       (\FU*{NREVERSE } \DES{\VAR{sequence}})}{.}}
 138   {
 139   Return \retval{\VAR{sequence} in reverse order}.
 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{\LIT{0}}\\
 148       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 149       \kwd{:key} \VAR{ function}}{\}})}
 150   {
 151   Return \retval{first element} in \VAR{sequence} which
 152   satisfies tests, or its \retval{position} relative to
 153   \VAR{sequence}'s start, respectively.
 154   }
 155
 156   \IT{(\xorGOO{\FU*{FIND-IF}\\
 157       \FU*{FIND-IF-NOT}\\\FU*{POSITION-IF}\\
 158       \FU*{POSITION-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
 159     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 160       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 161       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 162       \kwd{:key} \VAR{ function}}{\}})}
 163   {
 164   Return \retval{first element in \VAR{sequence}} which satisfies \VAR{test}, or
 165   \retval{its position} relative to \VAR{sequence}'s start, respectively.
 166   }
 167
 168   \IT{(\FU*{SEARCH} \VAR{sequence-a} \VAR{sequence-b}
 169     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 170       \kwd{:test} \VAR{ function}\\
 171       \kwd{:test-not} \VAR{ function}\\
 172       \kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
 173       \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
 174       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 175       \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
 176       \kwd{:key} \VAR{ function}}{\}})}
 177   {
 178   Search \VAR{sequence-b} for a subsequence matching
 179   \VAR{sequence-a}. Return \retval{position} in \VAR{sequence-b}, or
 180   \retval{\NIL}.
 181   }
 182
 183   \IT{(\xorGOO{\FU*{REMOVE} \VAR{ foo } \VAR{sequence}\\
 184       \FU*{DELETE} \VAR{ foo } \DES{\VAR{sequence}}}{\}}
 185     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 186       \kwd{:test} \VAR{ function}\\
 187       \kwd{:test-not} \VAR{ function}\\
 188       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 189       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 190       \kwd{:key} \VAR{ function}\\
 191       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 192   {
 193   Make \retval{copy of \VAR{sequence}} without elements matching
 194   \VAR{foo}.
 195   }
 196
 197   \IT{(\xorGOO{%
 198       \arrGOO{
 199         \FU*{REMOVE-IF}\\
 200         \FU*{REMOVE-IF-NOT}}{\}} \VAR{ test } \VAR{sequence}\\
 201       \arrGOO{
 202         \FU*{DELETE-IF}\\
 203         \FU*{DELETE-IF-NOT}}{\}} \VAR{ test }
 204       \DES{\VAR{sequence}}\text{ }}{\}}
 205       \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 206       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 207       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 208       \kwd{:key} \VAR{ function}\\
 209       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 210   {
 211   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count}) elements
 212   satisfying \VAR{test} removed.
 213   }
 214
 215   \IT{(\xorGOO{\FU*{REMOVE-DUPLICATES} \VAR{ sequence }\\
 216       \FU*{DELETE-DUPLICATES } \DES{\VAR{sequence}}}{\}}
 217     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 218       \kwd{:test} \VAR{ function}\\
 219       \kwd{:test-not} \VAR{ function}\\
 220       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 221       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 222       \kwd{:key} \VAR{ function}}{\}})}
 223   {
 224   Make \retval{copy of \VAR{sequence}} without duplicates.
 225   }
 226
 227   \IT{(\xorGOO{%
 228       \FU*{SUBSTITUTE} \VAR{ new} \VAR{ old } \VAR{sequence} \\
 229       \FU*{NSUBSTITUTE} \VAR{ new} \VAR{ old } \DES{\VAR{sequence}} }{\}}
 230     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 231       \kwd{:test} \VAR{ function}\\
 232       \kwd{:test-not} \VAR{ function}\\
 233       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 234       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 235       \kwd{:key} \VAR{ function}\\
 236       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 237   {
 238   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 239   \VAR{old}s replaced by \VAR{new}.
 240   }
 241
 242   \IT{(\xorGOO{%
 243       \arrGOO{%
 244         \FU*{SUBSTITUTE-IF}\\
 245         \FU*{SUBSTITUTE-IF-NOT}}{\}}
 246       \VAR{ new} \VAR{ test } \VAR{sequence}\\
 247       \arrGOO{%
 248         \FU*{NSUBSTITUTE-IF}\\
 249         \FU*{NSUBSTITUTE-IF-NOT}}{\}}
 250       \VAR{ new} \VAR{ test } \DES{\VAR{sequence}}\text{ }
 251     }{\}}
 252     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 253       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 254       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 255       \kwd{:key} \VAR{ function}\\
 256       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 257   {
 258     Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 259     elements satisfying \VAR{test} replaced by
 260     \VAR{new}.
 261   }
 262
 263   \IT{(\FU*{REPLACE} \DES{\VAR{sequence-a}} \VAR{sequence-b}
 264     \orGOO{\kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
 265       \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
 266       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 267       \kwd{:end2} \VAR{ end-b}\DF{\NIL}}{\}})}
 268   {
 269     Replace elements of \retval{\VAR{sequence-a}} with elements of
 270     \VAR{sequence-b}.
 271     }
 272
 273   \IT{(\FU*{MAP} \VAR{type} \VAR{function} \RP{\VAR{sequence}})}
 274   {
 275   Apply \VAR{function} successively to corresponding elements of the
 276   \VAR{sequence}s. Return values as a \retval{sequence} of
 277     \VAR{type}. If \VAR{type} is \NIL, return \retval{\NIL}.
 278   }
 279
 280   \IT{(\FU*{MAP-INTO} \DES{\VAR{result-sequence}} \VAR{function}
 281     \RP{\VAR{sequence}})}
 282   {
 283   Store into \retval{\VAR{result-sequence}} successively values of
 284   \VAR{function} applied to corresponding elements of the \VAR{sequence}s.
 285   }
 286
 287   \IT{(\FU*{REDUCE} \VAR{function} \VAR{sequence}
 288     \orGOO{\kwd{:initial-value} \VAR{ foo}\DF{\NIL}\\
 289       \kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 290       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 291       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 292       \kwd{:key} \VAR{ function}}{\}})}
 293   {
 294   Starting with the first two elements of \VAR{sequence}, apply
 295   \VAR{function} successively to its last return value together with the next
 296   element of \VAR{sequence}. Return \retval{last value} of {function}.
 297   }
 298
 299   \IT{(\FU*{COPY-SEQ} \VAR{sequence})}
 300   {
 301   Return \retval{copy of \VAR{sequence}} with the same elements.
 302   }
 303
 304
 305 \end{LIST}
 306
 307