What does the delete function do to an array?

I am trying to delete an element from an array using the delete function in Common Lisp (SBCL) but noticed that all the indices of this array are still present (the return value of (length arr) on the array is unchanged) after a call to delete:

(defparameter *x* (make-array 3 :initial-contents (list 13 26 39)))
*x* ; #(13 26 39)
(delete 26 *x* :test #'equal) ; #(13 39)

*x* ; #(13 39 39)
(length *x*) ; 3

I assume that the second element of *X* is still accessible after calling delete because arrays are contiguous chunks of memory where indices cannot be 'removed' without creating a new array.

My confusion comes from using setf in conjunction with delete. This only allows the user access to elements that were not affected by delete:

(defparameter *y* (make-array 3 :initial-contents (list 13 26 39)))
*y* ; #(13 26 39)
(setf *y* (delete 26 *y* :test #'equal)) ; #(13 39)

*y* ; #(13 39)
(length *y*) ; 2

Does this mean that delete returns a new array when called on arrays? Or does the setf call create a new array so that (setf (delete ...)) effectively does the same thing as (setf (remove ...))? Or is the *Y* from above pointing at the same array the whole time, just the second element was somehow 'ignored' behind the scenes?

If you read the Common Lisp standard (usually the Common Lisp HyperSpec), then it says:

> delete item sequence &key from-end test test-not start end count key
> => result-sequence
>
> ...
>
> delete, delete-if, and delete-if-not are like remove, remove-if, and
> remove-if-not respectively, but they may modify sequence.

sequence is the supertype of vector and list. Thus the function delete works for vectors and lists.

delete item sequence denotes the required arguments.

but they may modify sequence then means that the function may modify the original sequence provided as an argument. may modify means that an implementations can differ in behavior.

But in any case you need to use the returned result sequence. That's also relatively easy to remember, since many (but not all) functions typically return results and it is preferred to think in terms of computed results and not as a procedure with side effects.

Note that vectors in Common Lisp are mutable objects. One can change their contents, without allocating a new object. Also note: Common Lisp provides destructive functions which may modify the argument objects. For some functions the behavior is intended and for some functions they are side effects not to be used. delete is such a latter function: the argument sequence can be changed and that object should no longer be used.

Example 1:

(defparameter *x* (make-array 3 :initial-contents (list 13 26 39)))

Above creates a vector object of length 3 with the provided contents. The variable *x* points to this object.

*x* ; #(13 26 39)

Above: The variable *x* still points to the originally created object.

(delete 26 *x* :test #'equal) ; #(13 39)

Above: #(13 39) is returned from the delete call. This value is not used, just returned. The variable *x* still points to the originally created vector object. That object might have been changed.

*x* ; #(13 39 39)

Above: The variable *x* still points to the originally created object. The object has been destructively changed by the delete call.

(length *x*) ; 3

Above: The variable *x* still points to the originally created object. It's length is still 3.

Example 2:

(defparameter *y* (make-array 3 :initial-contents (list 13 26 39)))

Above creates a vector object of length 3 with the provided contents. The variable *y* points to this object.

*y* ; #(13 26 39)

Above: The variable *y* still points to the originally created object.

(setf *y* (delete 26 *y* :test #'equal)) ; #(13 39)

Above: the variable *y* is set to the returned object from the delete call: #(13 39).

*y* ; #(13 39)

Above: The variable *y* points to the new, from delete returned, object.

(length *y*) ; 2

Above: The variable *y* still points to the new, from delete returned, object. The length of that object is 2.

delete is a destructive operation which may (but is not required to) modify the original sequence upon which it operates. The resulting sequence is returned. It is a mistake to use delete (or similar destructive operations) and then to treat the original sequence as if it is the correct result (as in your first example). You must always use the sequence which has been returned by delete (as in your second example).

"Does this mean that delete returns a new array when called on arrays?"

You should probably think of the return value as a new array. delete does construct its result, but it is allowed to modify or destroy the input sequence as part of that process. The returned sequence may or may not be identical to the input sequence in the eq sense.

setf does not create a new sequence, and in the case of using remove instead of delete, remove is not allowed to modify or destroy its input sequence. The result returned from remove also may or may not be identical to the input sequence.

Whether you use the non-destructive remove or the destructive delete, you must work with the returned sequence to use the result of the operation. In the case of remove you may still work with the original input sequence since it is reliably known to be intact, but in the case of delete you should not use the input sequence after the operation since it may have been altered.

DELETE is a destructive operation. That means that the function can modify the input sequence to produce its output, and so, you should only use the output of the function and you must consider the input as lost and you must not use it anymore.

It's important to understand why such "destructive" behavior is available in destructive operators : it is for efficiency purpose; When you call a destructive operator, you're allowing the implementation to do what it wants with the input to produce the output in a more efficient way than by using a non-destructive operator.

The corollary is that : you must not use destructive operators for their side-effects, you must consider your input as definitively lost.

That said, that doesn't mean implementations can't reuse your input to produce the output. See this little experiment with SBCL :

CL-USER> (defparameter *x* (make-array 3 :initial-contents (list 13 26 39)))
*X*
CL-USER> (defparameter *y* (delete 26 *x* :test #'=))
*Y*
CL-USER> *x*
#(13 39 39)
CL-USER> *y*
#(13 39)
CL-USER> (eq *x* *y*)
NIL

But now see:

CL-USER> (defparameter *x* (make-array 3 :element-type 'number
                                :fill-pointer 3
                                :initial-contents (list 13 26 39)))
*X*
CL-USER> *x*
#(13 26 39)
CL-USER> (defparameter *y* (delete 26 *x* :test #'=))
*Y*
CL-USER> *y*
#(13 39)
CL-USER> *x*
#(13 39)
CL-USER> (eq *x* *y*)
T