Common Lisp the Language, 2nd Edition


next up previous contents index
Next: Modifying Sequences Up: Sequences Previous: Simple Sequence Functions

14.2. Concatenating, Mapping, and Reducing Sequences

The functions in this section each operate on an arbitrary number of sequences except for reduce, which is included here because of its conceptual relationship to the mapping functions.


[Function]
concatenate result-type &rest sequences

The result is a new sequence that contains all the elements of all the sequences in order. All of the sequences are copied from; the result does not share any structure with any of the argument sequences (in this concatenate differs from append). The type of the result is specified by result-type, which must be a subtype of sequence, as for the function coerce. It must be possible for every element of the argument sequences to be an element of a sequence of type result-type.

If only one sequence argument is provided and it has the type specified by result-type, concatenate is required to copy the argument rather than simply returning it. If a copy is not required, but only possibly type conversion, then the coerce function may be appropriate.

change_begin
X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH)   to specify that concatenate should signal an error if the sequence type specifies the number of elements and the sum of the argument lengths is different.
change_end


[Function]
map result-type function sequence &rest more-sequences

The function must take as many arguments as there are sequences provided; at least one sequence must be provided. The result of map is a sequence such that element j is the result of applying function to element j of each of the argument sequences. The result sequence is as long as the shortest of the input sequences.

If the function has side effects, it can count on being called first on all the elements numbered 0, then on all those numbered 1, and so on.

The type of the result sequence is specified by the argument result-type (which must be a subtype of the type sequence), as for the function coerce. In addition, one may specify nil for the result type, meaning that no result sequence is to be produced; in this case the function is invoked only for effect, and map returns nil. This gives an effect similar to that of mapc.

change_begin
X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH)   to specify that map should signal an error if the sequence type specifies the number of elements and the minimum of the argument lengths is different.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict user side effects; see section 7.9.
change_end


Compatibility note: In MacLisp, Lisp Machine Lisp, Interlisp, and indeed even Lisp 1.5, the function map has always meant a non-value-returning version. However, standard computer science literature, including in particular the recent wave of papers on ``functional programming,'' have come to use map to mean what in the past Lisp implementations have called mapcar. To simplify things henceforth, Common Lisp follows current usage, and what was formerly called map is named mapl in Common Lisp.

For example:

(map 'list #'- '(1 2 3 4)) => (-1 -2 -3 -4) 
(map 'string 
     #'(lambda (x) (if (oddp x) #\1 #\0)) 
     '(1 2 3 4)) 
   => "1010"

change_begin

[Function]
map-into result-sequence function &rest sequences

X3J13 voted in June 1989 (MAP-INTO)   to add the function map-into. It destructively modifies the result-sequence to contain the results of applying function to corresponding elements of the argument sequences in turn; it then returns result-sequence.

The arguments result-sequence and each element of sequences can each be either a list or a vector (one-dimensional array). The function must accept at least as many arguments as the number of argument sequences supplied to map-into. If result-sequence and the other argument sequences are not all the same length, the iteration terminates when the shortest sequence is exhausted. If result-sequence is a vector with a fill pointer, the fill pointer is ignored when deciding how many iterations to perform, and afterwards the fill pointer is set to the number of times the function was applied.

If the function has side effects, it can count on being called first on all the elements numbered 0, then on all those numbered 1, and so on.

If result-sequence is longer than the shortest element of sequences, extra elements at the end of result-sequence are unchanged.

The function map-into differs from map in that it modifies an existing sequence rather than creating a new one. In addition, map-into can be called with only two arguments (result-sequence and function), while map requires at least three arguments.

If result-sequence is nil, map-into immediately returns nil, because nil is a sequence of length zero.
change_end


[Function]
some predicate sequence &rest more-sequences
every predicate sequence &rest more-sequences
notany predicate sequence &rest more-sequences
notevery predicate sequence &rest more-sequences

These are all predicates. The predicate must take as many arguments as there are sequences provided. The predicate is first applied to the elements with index 0 in each of the sequences, and possibly then to the elements with index 1, and so on, until a termination criterion is met or the end of the shortest of the sequences is reached.

If the predicate has side effects, it can count on being called first on all the elements numbered 0, then on all those numbered 1, and so on.

some returns as soon as any invocation of predicate returns a non-nil value; some returns that value. If the end of a sequence is reached, some returns nil. Thus, considered as a predicate, it is true if some invocation of predicate is true.

every returns nil as soon as any invocation of predicate returns nil. If the end of a sequence is reached, every returns a non-nil value. Thus, considered as a predicate, it is true if every invocation of predicate is true.

notany returns nil as soon as any invocation of predicate returns a non-nil value. If the end of a sequence is reached, notany returns a non-nil value. Thus, considered as a predicate, it is true if no invocation of predicate is true.

notevery returns a non-nil value as soon as any invocation of predicate returns nil. If the end of a sequence is reached, notevery returns nil. Thus, considered as a predicate, it is true if not every invocation of predicate is true.

change_begin
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict user side effects; see section 7.9.
change_end


Compatibility note: The order of the arguments here is not compatible with Interlisp and Lisp Machine Lisp. This is to stress the similarity of these functions to map. The functions are therefore extended here to functions of more than one argument, and to multiple sequences.


[Function]
reduce function sequence &key :from-end :start :end :initial-value

The reduce function combines all the elements of a sequence using a binary operation; for example, using + one can add up all the elements.

The specified subsequence of the sequence is combined or ``reduced'' using the function, which must accept two arguments. The reduction is left-associative, unless the :from-end argument is true (it defaults to nil), in which case it is right-associative. If an :initial-value argument is given, it is logically placed before the subsequence (after it if :from-end is true) and included in the reduction operation.

If the specified subsequence contains exactly one element and the keyword argument :initial-value is not given, then that element is returned and the function is not called. If the specified subsequence is empty and an :initial-value is given, then the :initial-value is returned and the function is not called.

If the specified subsequence is empty and no :initial-value is given, then the function is called with zero arguments, and reduce returns whatever the function does. (This is the only case where the function is called with other than two arguments.)

(reduce #'+ '(1 2 3 4)) => 10 
(reduce #'- '(1 2 3 4)) == (- (- (- 1 2) 3) 4) => -8 
(reduce #'- '(1 2 3 4) :from-end t)     ;Alternating sum 
   == (- 1 (- 2 (- 3 4))) => -2 
(reduce #'+ '()) => 0 
(reduce #'+ '(3)) => 3 
(reduce #'+ '(foo)) => foo 
(reduce #'list '(1 2 3 4)) => (((1 2) 3) 4) 
(reduce #'list '(1 2 3 4) :from-end t) => (1 (2 (3 4))) 
(reduce #'list '(1 2 3 4) :initial-value 'foo) 
   => ((((foo 1) 2) 3) 4) 
(reduce #'list '(1 2 3 4) 
        :from-end t :initial-value 'foo) 
   => (1 (2 (3 (4 foo))))

If the function produces side effects, the order of the calls to the function can be correctly predicted from the reduction ordering demonstrated above.

change_begin
The name ``reduce'' for this function is borrowed from APL.

X3J13 voted in March 1988 (REDUCE-ARGUMENT-EXTRACTION)   to extend the reduce function to take an additional keyword argument named :key. As usual, this argument defaults to the identity function. The value of this argument must be a function that accepts at least one argument. This function is applied once to each element of the sequence that is to participate in the reduction operation, in the order implied by the :from-end argument; the values returned by this function are combined by the reduction function. However, the :key function is not applied to the :initial-value argument (if any).

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict user side effects; see section 7.9.
change_end



next up previous contents index
Next: Modifying Sequences Up: Sequences Previous: Simple Sequence Functions


AI.Repository@cs.cmu.edu