Asp Forum - question about set-difference

Jim Newton

11/30/2015 1:15:00 PM

Look at the documentation of SET-DIFFERENCE in the spec http://clhs.lisp.se/Body/f_...
can someone tell me where is the guarantee that set-difference returns a newly allocated list?
From my casual reading it appears to me that set-difference is allowed to return one of the
original lists, or a cons therein.

Am I reading this correctly that set-difference may not allocate a new list in some situations?

Jim

9 Answers

Pascal J. Bourguignon

11/30/2015 1:31:00 PM

Jim Newton <jimka.issy@gmail.com> writes:

> Look at the documentation of SET-DIFFERENCE in the spec http://clhs.lisp.se/Body/f_...
> can someone tell me where is the guarantee that set-difference returns a newly allocated list?
> From my casual reading it appears to me that set-difference is allowed to return one of the
> original lists, or a cons therein.
>
> Am I reading this correctly that set-difference may not allocate a new list in some situations?

Of course. For all pair of functions (f nf), f can be defined as:

(setf (fdefinition 'f) (fdefinition 'nf))

(including (setf (fdefinition 'delete) (fdefinition 'remove)))

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

Pascal J. Bourguignon

11/30/2015 1:33:00 PM

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

> Jim Newton <jimka.issy@gmail.com> writes:
>
>> Look at the documentation of SET-DIFFERENCE in the spec http://clhs.lisp.se/Body/f_...
>> can someone tell me where is the guarantee that set-difference returns a newly allocated list?
>> From my casual reading it appears to me that set-difference is allowed to return one of the
>> original lists, or a cons therein.
>>
>> Am I reading this correctly that set-difference may not allocate a new list in some situations?
>
> Of course. For all pair of functions (f nf), f can be defined as:
>
> (setf (fdefinition 'f) (fdefinition 'nf))

Sorry, I mean:

(setf (fdefinition 'nf) (fdefinition 'f))

> (including (setf (fdefinition 'delete) (fdefinition 'remove)))

So indeed, when there's no need to allocate a new list, there's no
reason to do so, so it would be silly to do so.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

Norbert_Paul

11/30/2015 4:18:00 PM

Jim Newton wrote:
> Am I reading this correctly that set-difference may not allocate a new list in some situations?
Yes, if by "may not" you mean "might not". Then this is what
"The result list may share cells with, or be eq to, either of list-1 or list-2, if appropriate."
means.

For exmple, the expressions
(let ((lst '(1 2 3)))
(eq (set-difference lst nil) lst))
and
(let ((lst '(1 2 3)))
(eq (set-difference lst '(1))))

may or may not return true.

Barry Margolin

11/30/2015 5:08:00 PM

In article <451d7230-038d-4760-aac8-d0ad1cdb9cd1@googlegroups.com>,
Jim Newton <jimka.issy@gmail.com> wrote:

> Look at the documentation of SET-DIFFERENCE in the spec
> http://clhs.lisp.se/Body/f_...
> can someone tell me where is the guarantee that set-difference returns a
> newly allocated list?
> From my casual reading it appears to me that set-difference is allowed to
> return one of the
> original lists, or a cons therein.
>
> Am I reading this correctly that set-difference may not allocate a new list
> in some situations?

That's correct. It can do so as long as it doesn't need to modify any of
the cons cells of the list it chooses to share with.

If you have the bindings:

(setq *l1* '(1 2 3) *l2* '(1) *l3* '(3 1 2))

then

(set-difference *l1* *l2*)

can return (cdr *l1))

(set-difference *l3* *l2*)

can return (cons 3 (cddr *l3*))

By comparison, nset-difference is allowed to modify its input, so in the
second example it can do

(setf (cdr *l3*) (cddr *l3*))

(ignore that I wrote them as literal lists for brevity).

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

Kaz Kylheku

11/30/2015 7:18:00 PM

On 2015-11-30, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>
>> Jim Newton <jimka.issy@gmail.com> writes:
>>
>>> Look at the documentation of SET-DIFFERENCE in the spec http://clhs.lisp.se/Body/f_...
>>> can someone tell me where is the guarantee that set-difference returns a newly allocated list?
>>> From my casual reading it appears to me that set-difference is allowed to return one of the
>>> original lists, or a cons therein.
>>>
>>> Am I reading this correctly that set-difference may not allocate a new list in some situations?
>>
>> Of course. For all pair of functions (f nf), f can be defined as:
>>
>> (setf (fdefinition 'f) (fdefinition 'nf))
>
> Sorry, I mean:
>
> (setf (fdefinition 'nf) (fdefinition 'f))
>
>> (including (setf (fdefinition 'delete) (fdefinition 'remove)))
>
> So indeed, when there's no need to allocate a new list, there's no
> reason to do so, so it would be silly to do so.

Your example of delete and remove cotains a distracting element, because those
two functions are connected by an issue which is important, but irrelevant
here: the choice whether to destroy the input sequence or not.

This is tangential to whether the output shares cons cells with the input(s).

Under remove, the output can share cons cells with the inputs
(andin fact *be* the input, if there is nothing to remove) so long
as the input structure is not mutated.

Under delete, the same holds, plus that sharing can be achieved to an
even greater degree by mutating the input.

I think you're trying to say that it's a general principle in Common Lisp
that unless otherwise specified, list-manipulating functions take advantage
of the assumption that applicative programming is being done, and share
structure between inputs and outputs.

Thus impure programs have to be carefully written in the face of most
library functions.

set-difference is no exception in this regard.

Pascal Costanza

11/30/2015 7:21:00 PM

On 30/11/2015 14:14, Jim Newton wrote:
> Look at the documentation of SET-DIFFERENCE in the spec http://clhs.lisp.se/Body/f_...
> can someone tell me where is the guarantee that set-difference returns a newly allocated list?
> From my casual reading it appears to me that set-difference is allowed to return one of the
> original lists, or a cons therein.
>
> Am I reading this correctly that set-difference may not allocate a new list in some situations?

If you need such a guarantee, you need to sprinkle some calls to
copy-list in the right places.

Pascal

--
My website: http:/...
Common Lisp Document Repository: http://cdr.eu...
Closer to MOP & ContextL: http://common-lisp.net/proje...
The views expressed are my own, and not those of my employer.

rpw3

12/1/2015 11:56:00 AM

Norbert_Paul <norbertpauls_spambin@yahoo.com> wrote:
+---------------
| and
| (let ((lst '(1 2 3)))
| (eq (set-difference lst '(1))))
| may or may not return true.
+---------------

Uh... That one can't *ever* return T.
Did you really mean this?

(let ((lst '(1 2 3)))
(eq (set-difference lst '(1)) (cdr lst)))

-Rob

p.s. FWIW, CMUCL returns T for your first example [not quoted]
and NIL for your second [as corrected above].

-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <http://rpw...
San Mateo, CA 94403

William James

12/1/2015 5:19:00 PM

Pascal Costanza wrote:

> > can someone tell me where is the guarantee that
> > set-difference returns a newly allocated list?
> > From my casual reading it appears to me that
> > set-difference is allowed to return one of the
> > original lists, or a cons therein.
> >
> > Am I reading this correctly that set-difference
> > may not allocate a new list in some situations?
>
> If you need such a guarantee, you need to sprinkle some
> calls to copy-list in the right places.

Ocaml:

module SS = Set.Make(String);;

let s1 = SS.of_list ["a";"b";"c";"d";"e";"f"];;
let s2 = SS.of_list ["a";"d"];;

SS.diff s1 s2 |> SS.iter print_endline ;;

b
c
e
f

--
If the Union was formed by the accession of States, then the
Union may be dissolved by the secession of States.
--- Daniel Webster, U.S. Senate, February 15, 1833

Norbert_Paul

12/2/2015 12:21:00 PM

Rob Warnock wrote:
> Norbert_Paul<norbertpauls_spambin@yahoo.com> wrote:
> +---------------
> | and
> | (let ((lst '(1 2 3)))
> | (eq (set-difference lst '(1))))
> | may or may not return true.
> +---------------
>
> Uh... That one can't *ever* return T.

OOPS!

> Did you really mean this?
>
> (let ((lst '(1 2 3)))
> (eq (set-difference lst '(1)) (cdr lst)))

Yes.

comp.lang.lisp

question about set-difference

Jim Newton

Pascal J. Bourguignon

Pascal J. Bourguignon

Norbert_Paul

Barry Margolin

Kaz Kylheku

Pascal Costanza

rpw3

William James

Norbert_Paul

x Login to ForumsZone