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)) ?