What does INTERSECTION return when KEY is given?

[Chaitanya Gupta]

Hello,

If I pass a :KEY argument to (N)INTERSECTION (or UNION, for that
matter), does it return the elements from list-1 or list-2? Or is this
implementation-dependent? It hasn't been very clear to me from the
hyperspec.

The hyperspec gives this example:

(setq list1 (copy-list '((1 . 2) (2 . 3) (3 . 4) (4 . 5))))
=> ((1 . 2) (2 . 3) (3 . 4) (4 . 5))
(setq list2 (copy-list '((1 . 3) (2 . 4) (3 . 6) (4 . 8))))
=> ((1 . 3) (2 . 4) (3 . 6) (4 . 8))
(nintersection list1 list2 :key #'cdr) => ((2 . 3) (3 . 4))

Both the elements returned here belong to list-1. Could the result be
different, though?

Thanks,
Chaitanya

[Pascal Costanza]

Yes. The spec that it can be either from one or the other list.

Pascal

--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/

[Chaitanya Gupta]

Pascal Costanza wrote:
>> Both the elements returned here belong to list-1. Could the result be
>> different, though?
>
> Yes. The spec that it can be either from one or the other list.
>

Sad. I had thought of some innovative use for INTERSECTION if the
elements were only returned from list-1. :(

But I guess I can just roll my own INTERSECTION-FIRST or something.. :)

Chaitanya

[Marco Antoniotti]

Yes. As a matter of fact, short of using FSet, I would (and did) so.
There is no algorithmic requirement in the spec. So some
implementations happily use O(n^2) algorithms for the set functions.

Cheers
--
Marco

[Chaitanya Gupta]

Marco Antoniotti wrote:
>
> Yes. As a matter of fact, short of using FSet, I would (and did) so.
> There is no algorithmic requirement in the spec. So some
> implementations happily use O(n^2) algorithms for the set functions.
>

I didn't know about FSet, until now. :)

Chaitanya