Issue ADJOIN

[Pascal J. Bourguignon]

It seems to me that the specification of ADJOIN is "wrong".

Tests whether item is the same as an existing element of list. If
the item is not an existing element, adjoin adds it to list (as if
by cons) and returns the resulting list; otherwise, nothing is added
and the original list is returned.

The test, test-not, and key affect how it is determined whether item
is the same as an element of list. For details, see Section 17.2.1
(Satisfying a Two-Argument Test).

Abd sectuib 17.2.1 says:

The function designated by the :key argument is never called on O
itself. However, if the function operates on multiple sequences
(e.g., as happens in set-difference), O will be the result of
calling the :key function on an element of the other sequence.

So, CLHS says that ADJOIN should not call key on the object to be
adjoined:

(defun adjoin* (item list &key (key (function identity))
(test (function eql))
(test-not nil test-not-p))
(if (apply (function member) item list
:key key
:test test
(when test-not-p
(list :test-not test-not)))
list
(cons item list)))

and therefore clhs specifies:

(adjoin* '(a 1) '((a 2) (b 3)) :key (function car))
--> ((a 1) (a 2) (b 3))

Of course, that's not what's implemented, in all implementations we
have:

(adjoin '(a 1) '((a 2) (b 3)) :key (function car))
--> ((a 2) (b 3))


Therefore, it seems to me there should be a clarifying issue for ADJOIN.
The specification for PUSHNEW is correct, and refers to the
expected behavior from ADJOIN. The clarifying issue for ADJOIN could
just substitute the paragraph:

The test, test-not, and key affect how it is determined whether item
is the same as an element of list. For details, see Section 17.2.1
(Satisfying a Two-Argument Test).

replacing it by:

Whether or not item is already a member of the list that is in place
is determined by comparisons using :test or :test-not. The first
argument to the :test or :test-not function is item as returned by
the :key function (if supplied); the second argument is an element
of the list in place as returned by the :key function (if supplied).

If :key is supplied, it is used to extract the part to be tested
from both item and the list element.

The argument to the :key function is an element of the list stored
in place. The :key function typically returns part part of the
element of the list. If :key is not supplied or nil, the list
element is used.

from the PUSHNEW specification. Since the specifications already makes
reference to the specification of ADJOIN, those paragraphs could just be
removed from PUSHNEW.


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[Kaz Kylheku]

On 2012-06-02, Pascal J. Bourguignon <p...@informatimago.com> wrote:
> The function designated by the :key argument is never called on O
> itself. However, if the function operates on multiple sequences
> (e.g., as happens in set-difference), O will be the result of
> calling the :key function on an element of the other sequence.

I think you perhaps simply have to regard the action of ADJOIN as being rather
more related to SET-DIFFERENCE, INTERSECTION and UNION than, to REMOVE or FIND.

Perhaps adjoin can be regarded to be somewhat like:

(adjoin x y ...) -> (union (list x) y ...)

where the item x is not regarded as a search key, but the element
of a one-element sequence.

The wording of the ADJOIN description is clearly defective, though, since it
doesn't capture this nuance.

[Barry Margolin]

In article <87mx4l3...@kuiper.lan.informatimago.com>,

"Pascal J. Bourguignon" <p...@informatimago.com> wrote:

> It seems to me that the specification of ADJOIN is "wrong".
>
> Tests whether item is the same as an existing element of list. If
> the item is not an existing element, adjoin adds it to list (as if
> by cons) and returns the resulting list; otherwise, nothing is added
> and the original list is returned.
>
> The test, test-not, and key affect how it is determined whether item
> is the same as an element of list. For details, see Section 17.2.1
> (Satisfying a Two-Argument Test).
>
> Abd sectuib 17.2.1 says:
>
> The function designated by the :key argument is never called on O
> itself. However, if the function operates on multiple sequences
> (e.g., as happens in set-difference), O will be the result of
> calling the :key function on an element of the other sequence.
>
> So, CLHS says that ADJOIN should not call key on the object to be
> adjoined:

No, it only says that when you're using a function that takes a single
item and a sequence.

In the case of functions that work on two sequences, the key is called
on elements of both sequences. First, 17.2.1 says:

If a :key argument is provided, it is a designator for a function
of one argument to be called with each Ei as an argument, and
yielding an object Zi to be used for comparison. (If there is no
:key argument, Zi is Ei.)

In this sentence, Ei refers to the elements of the first sequence. The
paragraph you quoted above says that :key is called on elements of "the
other sequence". Together, these two paragraphs indicate that :key is
called on elements of both sequence.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[Pascal J. Bourguignon]

In the case of ADJOIN there's a single sequence.

Syntax:

adjoin item list &key key test test-not => new-list

Arguments and Values:

item---an object.

list---a proper list.

That's why it's not correct to make reference to 17.2.1 in the
specification of ADJOIN.

[Barry Margolin]

In article <87ipf92...@kuiper.lan.informatimago.com>,

Of course, silly me.

Yes, this is clearly an error -- there's an example in the ADJOIN
writeup that applies the :key function to item. And for the obvious
purpose of ADJOIN, it needs to -- otherwise, you'll add elements to the
list that aren't in the same form as rest.

The way to fix this is to word the description like PUSHNEW, rather than
reference 17.2.1.

[Pascal J. Bourguignon]

Barry Margolin <bar...@alum.mit.edu> writes:

> The way to fix this is to word the description like PUSHNEW, rather than
> reference 17.2.1.

I created an issue on cliki for reference:

http://www.cliki.net/Issue%20ADJOIN-SPECIFICATION