From: Kent M Pitman
Subject: Re: intersection: noncommutative: can be relied upon?
Date: 
Message-ID: <sfwiuuxiiom.fsf@world.std.com>
SDS <···········@cctrading.com> writes:

> Neither CLtL2 nor CLHS specify this:
> (intersection '(a b) '((a . 1) (b . 2) (c . 3)) :test #'eq
>               :key (lambda (x) (if (consp x) (car x) x)))
> ==> (a b)
> (intersection '((a . 1) (b . 2) (c . 3)) '(a b) :test #'eq
>               :key (lambda (x) (if (consp x) (car x) x)))
> ==> ((a . 1) (b . 2))
> Can I assume that intersection takes the elements from the first list?

It's not specified because it's not defined.  If we had specified it,
I'm fairly confident we'd have made it "explicitly vague".

I'm hampered here by not having ever studied set theory so I don't
know the proper formal terms to use in explaining your problem, but
if you'll forgive the informal threatment, your problem is that
you're using sets in which the key creates an equivalence relation
between certain objects by saying that other aspects of those objects
do not matter in determining the set membership.  In doing this,
you effectively define that a and (a . 1) ARE the same element since
either's presence in the set is acceptable.  My feeling is that
if you do not believe that a and (a . 1) are absolutely equivalent
(since they have EQ keys), then you have improperly chosen to use
either INTERSECTION or this key.  I think that secretly you are not
really doing a set operation but only doing something that is like
sets, and that you are admitting that it is not enough like sets
for INTERSECTION to do what you want.  What you apparently wish is
that the definition of INTERSECTION were made concrete enough that
you could still fortuitously rely on the operator even though you're
not really using sets.  But no such luck.

> (It is specified for nintersection, but what about intersection?)

This is probably not because we were trying to make it easier for you
to abuse the set model, but rather because in a side-effecting situation
you want a bound on the side-effect.  I really think that philosophically
you are on thin ice even with NINTERSECTION.

> Is intersection the proper tool to extract subsets matching on a key?
> (Like in the second call above, a subset of the alist is extracted).

Yes, but I think you are not really using mathematical sets (even though
I also admit I'm not an expert on sets, so I might be wrong).

>  Of course, there are many ways to extract subsets, e.g.,
>    (mapcon (lambda (x) (if (member (caar x) '(a b)) (list (car x)) nil))
>     '((a . 1) (b . 2) (c . 3)))
>   ==> ((a . 1) (b . 2))
>  What would the gurus think to be "the best way"?

Oops.  That's what I get for replying linearly without reading ahead.
I don't know if I'm a "guru".  I just have a lot of opinions.
In any case, this isn't a set operation, this is a sequence operation.
I'm much more comfortable describing this as a "table lookup" or a 
"sequence filtering" than a "set manipulation".  I know it seems a 
subtle distinction, but the fact is that MAPCON  -is- defined to be
concrete enough to meet your needs where INTERSECTION really is not.
From: Duncan Smith
Subject: Re: intersection: noncommutative: can be relied upon?
Date: 
Message-ID: <344CD833.4E76@flavors.com>
? (remove '(a b) '((a . 1) (b . 2) (c . 3))
          :test #'(lambda (x y) (not (member (car y) x))))
((A . 1) (B . 2))
?