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