Common Lisp the Language, 2nd Edition

Next: Mapping Up: Series Functions Previous: Series Functions

A.2.1. Scanners

Scanners create series outputs based on non-series inputs. Either they operate based on some formula (for example, scanning a range of integers) or they enumerate the elements in an aggregate data structure (for example, scanning the elements in a list or array).

[Function]
scan-range &key (:start 0) (:by 1) (:type 'number)``:upto :below :downto :above :length

The function scan-range returns a series of numbers starting with the :start argument (default integer 0) and counting up by the :by argument (default integer 1). The :type argument (default number) is a type specifier indicating the type of numbers in the series produced. The :type argument must be a (not necessarily proper) subtype of number. The :start and :by arguments must be of that type.

One of the last five arguments may be used to specify the kind of end test to be used; these are called termination arguments. If :upto is specified, counting continues only so long as the numbers generated are less than or equal to :upto. If :below is specified, counting continues only so long as the numbers generated are less than :below. If :downto is specified, counting continues only so long as the numbers generated are greater than or equal to :downto. If :above is specified, counting continues only so long as the numbers generated are greater than :above. If :length is specified, it must be a non-negative integer and the output series has this length.

If none of the termination arguments are specified, the output has unbounded length. If more than one termination argument is specified, it is an error.

(scan-range :upto 4) => #Z(0 1 2 3 4) 
(scan-range :from 1 :by -1 :above -4) => #Z(1 0 -1 -2 -3) 
(scan-range :from .5 :by .1 :type 'float) => #Z(.5 .6 .7 ...) 
(scan-range) => #Z(0 1 2 3 4 5 6 ...)

[Function]
scansequence
scan typesequence

scan returns a series containing the elements of sequence in order. The type argument is a type specifier indicating the type of sequence to be scanned; it must be a (not necessarily proper) subtype of sequence. If type is omitted, it defaults to list. (This function exhibits an argument pattern that is unusual for Common Lisp: an ``optional’’ argument preceding a required argument. This pattern cannot be expressed in the usual manner with &optional. It is indicated above by two definition lines, showing the two possible argument patterns.)

If the sequence is a list, it must be a proper list ending in nil. Scanning is significantly more efficient if it can be determined at compile time whether type is a subtype of list or vector and for vectors what the length of the vector is.

(scan '(a b c)) => #Z(a b c) 
(scan 'string "BAR") => #Z(#\B #\A #\R)

[Function]
scan-sublistslist

scan-sublists returns a series containing the successive sublists of list. The list must be a proper list ending in nil.

(scan-sublists '(a b c)) => #Z((a b c) (b c) (c))

[Function]
scan-multipletypefirst-sequence&restmore-sequences

Several sequences can be scanned at once by using several calls on scan. Each call on scan will test to see when its sequence runs out of elements and execution will stop as soon as any of the sequences are exhausted. Although very robust, this approach to scanning can be inefficient. In situations where it is known in advance which sequence is the shortest, scan-multiple can be used to obtain the same results more rapidly.

scan-multiple is similar to scan except that several sequences can be scanned at once. If there are n sequence inputs, scan-multiple returns n series containing the elements of these sequences. It must be the case that none of the sequence inputs is shorter than the first sequence. All of the output series are the same length as the first input sequence. Extra elements in the other input sequences are ignored. Using scan-multiple is more efficient than using multiple instances of scan, because scan-multiple only has to check for the first input running out of elements.

If type is of the form (values...), then there must be m sequence inputs and the ith sequence must have type . Otherwise there can be any number of sequence inputs, each of which must have type type.

(multiple-value-bind (data weights) 
    (scan-multiple 'list '(1 6 3 2 8) '(2 3 3 3 2)) 
  (collect (map-fn t #'* data weights))) 
  => (2 18 9 6 16)

[Function]
scan-lists-of-listslists-of-lists&optionalleaf-test
scan-lists-of-lists-fringelists-of-lists&optionalleaf-test

The argument lists-of-lists is viewed as a tree where each internal node is a non-empty list and the elements of the list are the children of the node. scan-lists-of-lists and scan-lists-of-lists-fringe each scan lists-of-lists in preorder and return a series of its nodes. scan-lists-of-lists returns every node in the tree. scan-lists-of-lists-fringe returns only the leaf nodes.

The scan proceeds as follows. The argument lists-of-lists can be any Lisp object. If lists-of-lists is an atom or satisfies the predicate leaf-test (if present), it is a leaf node. (The predicate can count on being applied only to conses.) Otherwise, lists-of-lists is a (not necessarily proper) list. The first element of lists-of-lists is recursively scanned in full, followed by the second and so on until a non-cons cdr is encountered. Whether or not this final cdr is nil, it is ignored.

(scan-lists-of-lists '((2) (nil))) 
  => #Z(((2) (nil)) (2) 2 (nil) nil) 
(scan-lists-of-lists-fringe '((2) (nil))) => #Z(2 nil) 
(scan-lists-of-lists-fringe '((2) (nil)) 
                            #'(lambda (e) (numberp (car e)))) 
  => #Z((2) nil)

[Function]
scan-alista-list&optional (test#'eql)
scan-plistplist
scan-hashtable

When given an association list, a property list, or a hash table (respectively), each of these functions produces two outputs: a series of keys K and a series of the corresponding values V. Each key in the input appears exactly once in the output, even if it appears more than once in the input. (The test argument of scan-alist specifies the equality test between keys; it defaults to eql.) The two outputs have the same length. Each V is the value returned by the appropriate accessing function (cdr of assoc, getf, or gethash, respectively) when given K. scan-alist and scan-plist scan keys in the order they appear in the underlying structure. scan-hash scans keys in no particular order.

(scan-plist '(a 1 b 3)) => #Z(a b) and #Z(1 3) 
(scan-alist '((a . 1) nil (a . 3) (b . 2))) 
  => #Z(a b) and #Z(1 2)

[Function]
scan-symbols &optional (package*package*)

scan-symbols returns a series, in no particular order, and possibly containing duplicates, of the symbols accessible in package (which defaults to the current package).

[Function]
scan-filefile-name&optional (reader#'read)

scan-file opens the file named by the string file-name and applies the function reader to it repeatedly until the end of the file is reached. Reader must accept the standard input function arguments input-stream, eof-error-p, and eof-value as its arguments. (For instance, reader can be read, read-preserving-white-space, read-line, or read-char.) If omitted, reader defaults to read. scan-file returns a series of the values returned by reader, up to but not including the value returned when the end of the file is reached. The file is correctly closed, even if an abort occurs.

[Function]
scan-fntypeinitstep&optionaltest

The higher-order function scan-fn supports the general concept of scanning. The type argument is a type specifier indicating the type of values returned by init and step. The values type specifier can be used for this argument to indicate multiple types; however, type cannot indicate zero values. If type indicates m types , then scan-fn returns m series T1, …, Tm, where Ti has the type (series). The arguments init, step, and test are functions.

The init must be of type (function () (values...)).

The step must be of type (function (...) (values...)).

The test (if present) must be of type (function (...) t).

The elements of the Ti are computed as follows:

(values T1 ... Tm) = (funcall init) 
(values T1 ... Tm) = (funcall step T1 ... Tm)

The outputs all have the same length. If there is no test, the outputs have unbounded length. If there is a test, the outputs consist of the elements up to, but not including, the first elements (with index j, say) for which the following termination test is not nil.

(funcall test T1 ... Tm)

It is guaranteed that step will not be applied to the elements that pass this termination test.

If init, step, or test has side effects when invoked, it can count on being called in the order indicated by the equations above, with test called just before step on each cycle. However, given the lazy evaluation nature of series, these functions will not be called until their outputs are actually used (if ever). In addition, no assumptions can be made about the relative order of evaluation of these calls with regard to execution in other parts of a given series expression. The first example below scans down a list stepping two elements at a time. The second example generates two unbounded series: the integers counting up from 1 and the sequence of partial sums of the first i integers.

(scan-fn t #'(lambda () '(a b c d)) #'cddr #'null) 
  => #Z((a b c d) (c d)) 

(scan-fn '(values integer integer) 
         #'(lambda () (values 1 0)) 
         #'(lambda (i sum) (values (+ i 1) (+ sum i)))) 
  => #Z(1 2 3 4 ...) and #Z(0 1 3 6 ...)

[Function]
scan-fn-inclusivetypeinitsteptest

The higher-order function scan-fn-inclusive is the same as scan-fn except that the first set of elements for which test returns a non-null value is included in the output. As with scan-fn, it is guaranteed that step will not be applied to the elements for which test is non-null.

Next: Mapping Up: Series Functions Previous: Series Functions

AI.Repository@cs.cmu.edu