Common Lisp the Language, 2nd Edition

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.

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.

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"

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

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

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.

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.

Next: Modifying Sequences Up: Sequences Previous: Simple Sequence Functions