From: Chaitanya Gupta
Subject: What does INTERSECTION return when KEY is given?
Date: 
Message-ID: <gog6f3$lfj$1@news.motzarella.org>
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
From: Pascal Costanza
Subject: Re: What does INTERSECTION return when KEY is given?
Date: 
Message-ID: <711m40Fir66kU1@mid.individual.net>
Chaitanya Gupta wrote:
> 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?

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/
From: Chaitanya Gupta
Subject: Re: What does INTERSECTION return when KEY is given?
Date: 
Message-ID: <gogjfg$uia$1@news.motzarella.org>
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
From: Marco Antoniotti
Subject: Re: What does INTERSECTION return when KEY is given?
Date: 
Message-ID: <b0820922-c08c-4614-8a72-f7de9d28f11e@j38g2000yqa.googlegroups.com>
On Mar 2, 1:29 pm, Chaitanya Gupta <····@chaitanyagupta.com> wrote:
> 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

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
From: Chaitanya Gupta
Subject: Re: What does INTERSECTION return when KEY is given?
Date: 
Message-ID: <goglft$8bb$1@news.motzarella.org>
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
comp.lang.lisp / 2009 / mar