clqr-sequences.tex

   1 % Copyright (C) 2008, 2009, 2010, 2014, 2018 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; with no Invariant Sections, no Front-Cover Texts and
   6 % no Back-Cover Texts. For details see file COPYING.
   7 %
   8
   9 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  10 \section{Sequences}
  11 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  12 \label{section:Sequences}
  13
  14 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  15 \subsection{Sequence Predicates}
  16 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  17 \begin{LIST}{1cm}
  18
  19   \IT{(\xorGOO{\FU*{EVERY}\\
  20       \FU*{NOTEVERY}}{\}} \VAR{test}
  21     \RP{\VAR{sequence}})}
  22   {
  23   Return \retval{\NIL} or \retval{\T}, respectively, as soon as \VAR{test} on
  24   any set of corresponding elements of \VAR{sequence}s returns \NIL.
  25   }
  26
  27   \IT{(\xorGOO{\FU*{SOME}\\
  28       \FU*{NOTANY}}{\}} \VAR{test}
  29     \RP{\VAR{sequence}})}
  30   {
  31   Return \retval{value of \VAR{test}} or \retval{\NIL}, respectively, as soon
  32   as \VAR{test} on any set of corresponding elements of
  33   \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       \xorGOO{%
  39         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
  40         \kwd{:test-not} \VAR{ function}}{.}\\
  41       \kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
  42       \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
  43       \kwd{:end1}  \VAR{ end-a}\DF{\NIL}\\
  44       \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
  45       \kwd{:key} \VAR{ function}}{\}})}
  46   {
  47   Return \retval{position in \VAR{sequence-a}} where
  48   \VAR{sequence-a} and \VAR{sequence-b} begin to
  49   mismatch. Return \retval{\NIL} if
  50   they match entirely.
  51   }
  52
  53 \end{LIST}
  54
  55 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  56 \subsection{Sequence Functions}
  57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  58
  59 \begin{LIST}{1cm}
  60
  61   \IT{(\FU*{MAKE-SEQUENCE} \VAR{sequence-type} \VAR{size}
  62     \Op{\kwd{:initial-element} \VAR{foo}})} % default: implementation-dependent
  63   {
  64   Make \retval{sequence} of \VAR{sequence-type} with \VAR{size} elements.
  65   }
  66
  67   \IT{(\FU*{CONCATENATE} \VAR{type} \OPn{\VAR{sequence}})}
  68   {
  69   Return \retval{concatenated sequence} of \VAR{type}.
  70   }
  71
  72   \IT{(\FU*{MERGE} \VAR{type} \DES{\VAR{sequence-a}} \DES{\VAR{sequence-b}}
  73     \VAR{test} \Op{\kwd{:key} \VAR{function}\DF{\NIL}})}
  74   {
  75   Return \retval{interleaved sequence} of \VAR{type}. Merged sequence
  76   will be sorted if both  \VAR{sequence-a} and \VAR{sequence-b} are
  77   sorted.
  78   }
  79
  80   \IT{(\FU*{FILL} \DES{\VAR{sequence}} \VAR{foo}
  81     \orGOO{\kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
  82       \kwd{:end} \VAR{ end}\DF{\NIL}}{\}})}
  83   {
  84   Return \retval{\VAR{sequence}} after setting elements between \VAR{start}
  85   and \VAR{end} to \VAR{foo}.
  86   }
  87
  88   \IT{(\FU*{LENGTH} \VAR{sequence})}
  89   {Return \retval{length of
  90     \VAR{sequence}} (being value of fill pointer if applicable).
  91     }
  92
  93   \IT{(\FU*{COUNT} \VAR{foo} \VAR{sequence}
  94     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
  95       \xorGOO{%
  96         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
  97         \kwd{:test-not} \VAR{ function}}{.}\\
  98       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
  99       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 100       \kwd{:key} \VAR{ function}}{\}})}
 101   {
 102   Return \retval{number of elements} in \VAR{sequence} which match
 103   \VAR{foo}.
 104   }
 105
 106   \IT{(\xorGOO{\FU*{COUNT-IF}\\
 107       \FU*{COUNT-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
 108     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 109       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 110       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 111       \kwd{:key} \VAR{ function}}{\}})}
 112   {
 113   Return \retval{number of elements} in \VAR{sequence} which satisfy
 114   \VAR{test}.
 115   }
 116
 117   \IT{(\FU*{ELT} \VAR{sequence} \VAR{index})}
 118   {Return \retval{element of
 119     \VAR{sequence}} pointed to by zero-indexed
 120     \VAR{index}. \kwd{setf}able.
 121     }
 122
 123   \IT{(\FU*{SUBSEQ} \VAR{sequence} \VAR{start}
 124     \Op{\VAR{end}\DF{\NIL}})}
 125   {
 126   Return \retval{subsequence of \VAR{sequence}} between \VAR{start}
 127     and \VAR{end}. \kwd{setf}able.
 128     }
 129
 130   \IT{(\xorGOO{\FU*{SORT}\\
 131       \FU*{STABLE-SORT}}{\}} \DES{\VAR{sequence}} \VAR{test}
 132     \Op{\kwd{:key} \VAR{function}})}
 133   {
 134   Return \retval{\VAR{sequence} sorted}. Order
 135   of elements considered equal is not guaranteed/retained, respectively.
 136   }
 137
 138   \IT{\arrGOO{(\FU*{REVERSE} \VAR{ sequence})\\
 139       (\FU*{NREVERSE } \DES{\VAR{sequence}})}{.}}
 140   {
 141   Return \retval{\VAR{sequence} in reverse order}.
 142   }
 143
 144   \IT{(\xorGOO{\FU*{FIND}\\
 145       \FU*{POSITION}}{\}} \VAR{foo} \VAR{sequence}
 146     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 147       \xorGOO{%
 148         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 149         \kwd{:test-not} \VAR{ test}}{.}\\
 150       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 151       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 152       \kwd{:key} \VAR{ function}}{\}})}
 153   {
 154   Return \retval{first element} in \VAR{sequence} which
 155   matches \VAR{foo}, or its \retval{position} relative to the begin
 156   of \VAR{sequence}, respectively.
 157   }
 158
 159   \IT{(\xorGOO{\FU*{FIND-IF}\\
 160       \FU*{FIND-IF-NOT}\\\FU*{POSITION-IF}\\
 161       \FU*{POSITION-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
 162     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 163       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 164       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 165       \kwd{:key} \VAR{ function}}{\}})}
 166   {
 167   Return \retval{first element} in \VAR{sequence} which satisfies \VAR{test}, or
 168   its \retval{position} relative to the begin of \VAR{sequence}, respectively.
 169   }
 170
 171   \IT{(\FU*{SEARCH} \VAR{sequence-a} \VAR{sequence-b}
 172     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 173       \xorGOO{%
 174         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 175         \kwd{:test-not} \VAR{ function}}{.}\\
 176       \kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
 177       \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
 178       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 179       \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
 180       \kwd{:key} \VAR{ function}}{\}})}
 181   {
 182   Search \VAR{sequence-b} for a subsequence matching
 183   \VAR{sequence-a}. Return \retval{position} in \VAR{sequence-b}, or
 184   \retval{\NIL}.
 185   }
 186
 187   \IT{(\xorGOO{\FU*{REMOVE} \VAR{ foo } \VAR{sequence}\\
 188       \FU*{DELETE} \VAR{ foo } \DES{\VAR{sequence}}}{\}}
 189     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 190       \xorGOO{%
 191         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 192         \kwd{:test-not} \VAR{ function}}{.}\\
 193       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 194       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 195       \kwd{:key} \VAR{ function}\\
 196       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 197   {
 198   Make \retval{copy of \VAR{sequence}} without elements matching
 199   \VAR{foo}.
 200   }
 201
 202   \IT{(\xorGOO{%
 203       \arrGOO{
 204         \FU*{REMOVE-IF}\\
 205         \FU*{REMOVE-IF-NOT}}{\}} \VAR{ test } \VAR{sequence}\\
 206       \arrGOO{
 207         \FU*{DELETE-IF}\\
 208         \FU*{DELETE-IF-NOT}}{\}} \VAR{ test }
 209       \DES{\VAR{sequence}}\text{ }}{\}}
 210       \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 211       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 212       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 213       \kwd{:key} \VAR{ function}\\
 214       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 215   {
 216   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count}) elements
 217   satisfying \VAR{test} removed.
 218   }
 219
 220   \IT{(\xorGOO{\FU*{REMOVE-DUPLICATES} \VAR{ sequence }\\
 221       \FU*{DELETE-DUPLICATES } \DES{\VAR{sequence}}}{\}}
 222     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 223       \xorGOO{%
 224         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 225         \kwd{:test-not} \VAR{ function}}{.}\\
 226       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 227       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 228       \kwd{:key} \VAR{ function}}{\}})}
 229   {
 230   Make \retval{copy of \VAR{sequence}} without duplicates.
 231   }
 232
 233   \IT{(\xorGOO{%
 234       \FU*{SUBSTITUTE} \VAR{ new} \VAR{ old } \VAR{sequence} \\
 235       \FU*{NSUBSTITUTE} \VAR{ new} \VAR{ old } \DES{\VAR{sequence}} }{\}}
 236     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 237       \xorGOO{%
 238         \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
 239         \kwd{:test-not} \VAR{ function}}{.}\\
 240       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 241       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 242       \kwd{:key} \VAR{ function}\\
 243       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 244   {
 245   Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 246   \VAR{old}s replaced by \VAR{new}.
 247   }
 248
 249   \IT{(\xorGOO{%
 250       \arrGOO{%
 251         \FU*{SUBSTITUTE-IF}\\
 252         \FU*{SUBSTITUTE-IF-NOT}}{\}}
 253       \VAR{ new} \VAR{ test } \VAR{sequence}\\
 254       \arrGOO{%
 255         \FU*{NSUBSTITUTE-IF}\\
 256         \FU*{NSUBSTITUTE-IF-NOT}}{\}}
 257       \VAR{ new} \VAR{ test } \DES{\VAR{sequence}}\text{ }
 258     }{\}}
 259     \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 260       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 261       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 262       \kwd{:key} \VAR{ function}\\
 263       \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
 264   {
 265     Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
 266     elements satisfying \VAR{test} replaced by
 267     \VAR{new}.
 268   }
 269
 270   \IT{(\FU*{REPLACE} \DES{\VAR{sequence-a}} \VAR{sequence-b}
 271     \orGOO{\kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
 272       \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
 273       \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
 274       \kwd{:end2} \VAR{ end-b}\DF{\NIL}}{\}})}
 275   {
 276     Replace elements of \retval{\VAR{sequence-a}} with elements of
 277     \VAR{sequence-b}.
 278     }
 279
 280   \IT{(\FU*{MAP} \VAR{type} \VAR{function} \RP{\VAR{sequence}})}
 281   {
 282   Apply \VAR{function} successively to corresponding elements of the
 283   \VAR{sequence}s. Return values as a \retval{sequence} of
 284     \VAR{type}. If \VAR{type} is \NIL, return \retval{\NIL}.
 285   }
 286
 287   \IT{(\FU*{MAP-INTO} \DES{\VAR{result-sequence}} \VAR{function}
 288     \OPn{\VAR{sequence}})}
 289   {
 290   Store into \retval{\VAR{result-sequence}} successively values of
 291   \VAR{function} applied to corresponding elements of the \VAR{sequence}s.
 292   }
 293
 294   \IT{(\FU*{REDUCE} \VAR{function} \VAR{sequence}
 295     \orGOO{\kwd{:initial-value} \VAR{ foo}\DF{\NIL}\\
 296       \kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
 297       \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
 298       \kwd{:end} \VAR{ end}\DF{\NIL}\\
 299       \kwd{:key} \VAR{ function}}{\}})}
 300   {
 301   Starting with the first two elements of \VAR{sequence}, apply
 302   \VAR{function} successively to its last return value together with the next
 303   element of \VAR{sequence}. Return \retval{last value} of {function}.
 304   }
 305
 306   \IT{(\FU*{COPY-SEQ} \VAR{sequence})}
 307   {
 308     \retval{Copy of \VAR{sequence}} with shared elements.
 309   }
 310
 311
 312 \end{LIST}
 313
 314
 315
 316 %%% Local Variables:
 317 %%% mode: latex
 318 %%% TeX-master: "clqr"
 319 %%% End: