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