A seq (pronounced “seek”) is an ordered collection of elements, accessed by index rather than by value. Their functionality overlaps with that of CL sequences, but they have a different performance profile. Seqs are implemented as WB-trees, so accessing an element, updating one, inserting one, removing one, extracting a subsequence, and concatenating two seqs all take O(log n) time; this is in contrast to a CL vector, for which access and update are very fast O(1) operations, but the rest all take linear time. This makes seqs much more general, and more suitable as a default choice for a sequence datatype.
The O(log n) access time, in particular, seems to contrast poorly with the O(1) time you would
get with a Lisp vector. However, it applies only when you’re doing true random access into the seq,
which is a relatively rare case in practice. More common is to iterate over the seq or a subrange
of it; using do-seq or the stateful or
functional iterators, there is a logarithmic-time setup phase, but
after that the iteration takes amortized constant time per element.
Seqs are performance-symmetrical: operations at the head (first, with-first,
less-first) take the same expected time as operations at the tail (last,
with-last, less-last). Furthermore, on seqs of more than a certain minimum size,
several elements at the head and several at the tail are stored separately from the tree, to make
these operations faster. So seqs are perfectly usable as queues, stacks, or deques — not as fast
as purpose-built mutable data structures, but fast enough for most use cases, even with millions of
elements.
Character strings are an important special case of CL vectors, and seqs have some special support
for them as well. FSet’s WB-trees are heterogeneous: instead of leaves holding single elements,
they hold short (i.e., bounded-length) vectors of elements. The seq implementation takes this
idea a step further: if all the elements of a vector are characters, the vector itself is a CL
string, which takes less space.. As a consequence, a seq containing only characters is reasonably
space-efficient; and adding a small number of non-characters to it doesn’t reduce this efficiency
much — the only leaf vectors that must become CL simple-vectors are those that actually
contain a non-character; the rest remain strings.
On implementations, including SBCL, that have two string types — base-string, which holds
only base-chars and allocates 8 bits per character, and string, which holds Unicode
and allocates 32 bits per character — FSet takes this one step further, using base-strings
wherever possible.
FSet also tracks whether a seq contains only characters, and prints it differently if so. The overall effect of these features is that using seqs is a very sound choice for tasks, such as HTML generation, that require a lot of string manipulation.
Seqs have default values that are returned by a lookup on an out-of-bounds index; see Map and Seq Defaults.
Currently, seqs have only one implementation: wb-seq, using WB-trees.
The abstract class for FSet functional seqs. Subclass of collection.
Returns true iff x is an FSet functional seq.
Functional seqs implemented using WB-trees. Subclass of seq. These print in two different
ways, depending on whether they are “char seqs”, i.e., they contain only characters. Non-char
seqs use the general form:
#[ e0 e1 ... ]/default
However, if there are subsequences of consecutive characters within a non-char seq, these are
printed as strings, preceded by #$. The default is printed only if it is not nil; if
the map has no default, /[no default] is printed.
Char seqs are printed as strings, prefixed by #, and possibly also suffixed by a slash and
default, or /[no default]. (Examples below.)
Returns true iff x is an FSet functional WB-tree seq.
Constructor function. Returns an empty wb-seq. If default is supplied, that will be
the seq’s default; if no-default? is true, the seq will have no
default.
Constructor macro. Constructs a wb-seq according to the supplied argument subforms. Each
argument subform can be an expression whose value is to appear in the sequence; or a list of the
form ($ expression), in which case the value of the expression is converted to a seq, which is spliced into the result seq. The order of the result
sequence reflects the order of the argument subforms. If one of the arguments is :default,
the seq’s default is the value of the subsequent form; if one is :no-default, the seq has no
default; if neither, the seq’s default is nil. To include :default or
:no-default as an ordinary element, quote it. Examples:
> (seq 3 17) #[ 3 17 ] > (seq 3 17 :default 0) #[ 3 17 ]/0 > (seq 3 17 :no-default) #[ 3 17 ]/[no default] > (seq 3 17 ':default) #[ 3 17 :DEFAULT ] > (defparameter *a-seq* (seq 3 17)) *A-SEQ* > (seq 4 ($ *a-seq*) 8) #[ 4 3 17 8 ] > (seq 'foo #\b #\a #\r 'baz) #[ FOO #$"bar" BAZ ] > (seq #\f #\o #\o) #"foo" > (seq #\f #\o #\o :no-default) #"foo"/[no default] > (seq #\x ($ "yz") #\z #\y) #"xyzzy"