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}})}
  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}})}
  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}} 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{\LIT{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}}{\}} \DES{\VAR{sequence}} \VAR{test}
 129     \Op{\kwd{:key} \VAR{function}})}
 130   {
 131   Return \retval{\VAR{sequence} sorted}. Order
 132   of elements considered equal is not guaranteed/retained, respectively.
 133   }
 134
 135   \IT{\arrGOO{(\FU*{REVERSE} \VAR{ sequence})\\
 136       (\FU*{NREVERSE } \DES{\VAR{sequence}})}{.}}
 137   {
 138   Return \retval{\VAR{sequence} in reverse order}.
 139   }
 140
 141   \IT{(\xorGOO{\FU*{FIND}\\
 142       \FU*{POSITION}}{\}} \VAR{foo} \VAR{sequence}
 143     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 144       \kwd{:test} \VAR{ function}\\
 145       \kwd{:test-not} \VAR{ function}\\
 146       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 147       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 148       \kwd{:key} \VAR{ function}}{\}})}
 149   {
 150   Return \retval{first element} found in \VAR{sequence}, or
 151   its \retval{position} relative to \VAR{sequence}'s start, respectively,
 152   between \VAR{start} and \VAR{end} satisfying tests.
 153   }
 154
 155   \IT{(\xorGOO{\FU*{FIND-IF}\\\FU*{FIND-IF-NOT}\\\FU*{POSITION-IF}\\\FU*{POSITION-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
 156     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 157       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 158       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 159       \kwd{:key} \VAR{ function}}{\}})}
 160   {
 161   Return \retval{first element in \VAR{sequence}}, or
 162   \retval{its position} relative to \VAR{sequence}'s start, respectively, between \VAR{start}
 163   and \VAR{end} satisfying \VAR{test}.
 164   }
 165
 166   \IT{(\FU*{SEARCH} \VAR{sequence-a} \VAR{sequence-b}
 167     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 168       \kwd{:test} \VAR{ function}\\
 169       \kwd{:test-not} \VAR{ function}\\
 170       \kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
 171       \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
 172       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 173       \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
 174       \kwd{:key} \VAR{ function}}{\}})}
 175   {
 176   Search \VAR{sequence-b} for a subsequence matching
 177   \VAR{sequence-a}. Return \retval{position} in \VAR{sequence-b}, or
 178   \retval{\NIL}.
 179   }
 180
 181   \IT{(\xorGOO{\FU*{REMOVE} \VAR{ foo } \VAR{sequence}\\
 182       \FU*{DELETE} \VAR{ foo } \DES{\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{\LIT{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}.
 193   }
 194
 195   \IT{(\xorGOO{%
 196       \arrGOO{
 197         \FU*{REMOVE-IF}\\
 198         \FU*{REMOVE-IF-NOT}}{\}} \VAR{ test } \VAR{sequence}\\
 199       \arrGOO{
 200         \FU*{DELETE-IF}\\
 201         \FU*{DELETE-IF-NOT}}{\}} \VAR{ test }
 202       \DES{\VAR{sequence}}\text{ }}{\}}
 203       \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 204       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 205       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 206       \kwd{:key} \VAR{ function}\\
 207       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 208   {
 209   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count}) elements
 210   satisfying \VAR{test} removed.
 211   }
 212
 213   \IT{(\xorGOO{\FU*{REMOVE-DUPLICATES} \VAR{ sequence }\\
 214       \FU*{DELETE-DUPLICATES } \DES{\VAR{sequence}}}{\}}
 215     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 216       \kwd{:test} \VAR{ function}\\
 217       \kwd{:test-not} \VAR{ function}\\
 218       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 219       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 220       \kwd{:key} \VAR{ function}}{\}})}
 221   {
 222   Make \retval{copy of \VAR{sequence}} without duplicates.
 223   }
 224
 225   \IT{(\xorGOO{%
 226       \FU*{SUBSTITUTE} \VAR{ new} \VAR{ old } \VAR{sequence} \\
 227       \FU*{NSUBSTITUTE} \VAR{ new} \VAR{ old } \DES{\VAR{sequence}} }{\}}
 228     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 229       \kwd{:test} \VAR{ function}\\
 230       \kwd{:test-not} \VAR{ function}\\
 231       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 232       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 233       \kwd{:key} \VAR{ function}\\
 234       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 235   {
 236   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 237   \VAR{old}s replaced by \VAR{new}.
 238   }
 239
 240   \IT{(\xorGOO{%
 241       \arrGOO{%
 242         \FU*{SUBSTITUTE-IF}\\
 243         \FU*{SUBSTITUTE-IF-NOT}}{\}}
 244       \VAR{ new} \VAR{ test } \VAR{sequence}\\
 245       \arrGOO{%
 246         \FU*{NSUBSTITUTE-IF}\\
 247         \FU*{NSUBSTITUTE-IF-NOT}}{\}}
 248       \VAR{ new} \VAR{ test } \DES{\VAR{sequence}}\text{ }
 249     }{\}}
 250     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 251       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 252       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 253       \kwd{:key} \VAR{ function}\\
 254       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 255   {
 256     Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 257     elements satisfying \VAR{test} replaced by
 258     \VAR{new}.
 259   }
 260
 261   \IT{(\FU*{REPLACE} \DES{\VAR{sequence-a}} \VAR{sequence-b}
 262     \orGOO{\kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
 263       \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
 264       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 265       \kwd{:end2} \VAR{ end-b}\DF{\NIL}}{\}})}
 266   {
 267     Replace elements of \retval{\VAR{sequence-a}} with elements of
 268     \VAR{sequence-b}.
 269     }
 270
 271   \IT{(\FU*{MAP} \VAR{type} \VAR{function} \RP{\VAR{sequence}})}
 272   {
 273   Apply \VAR{function} successively to corresponding elements of the
 274   \VAR{sequence}s. Return values as a \retval{sequence} of
 275     \VAR{type}. If \VAR{type} is \NIL, return \retval{\NIL}.
 276   }
 277
 278   \IT{(\FU*{MAP-INTO} \DES{\VAR{result-sequence}} \VAR{function}
 279     \RP{\VAR{sequence}})}
 280   {
 281   Store into \retval{\VAR{result-sequence}} successively values of
 282   \VAR{function} applied to corresponding elements of the \VAR{sequence}s.
 283   }
 284
 285   \IT{(\FU*{REDUCE} \VAR{function} \VAR{sequence}
 286     \orGOO{\kwd{:initial-value} \VAR{ foo}\DF{\NIL}\\
 287       \kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 288       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 289       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 290       \kwd{:key} \VAR{ function}}{\}})}
 291   {
 292   Starting with the first two elements of \VAR{sequence}, apply
 293   \VAR{function} successively to its last return value together with the next
 294   element of \VAR{sequence}. Return \retval{last value} of {function}.
 295   }
 296
 297   \IT{(\FU*{COPY-SEQ} \VAR{sequence})}
 298   {
 299   Return \retval{copy of \VAR{sequence}} with the same elements.
 300   }
 301
 302
 303 \end{LIST}
 304
 305