**Common Lisp the Language, 2nd Edition**

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.

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.

**[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`.

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.

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"

**[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.

**[Function]**

`some 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.

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

**[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.

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.

AI.Repository@cs.cmu.edu