Adding rassq-delete-all to lisp/subr.el.

Adding rassq-delete-all to lisp/subr.el.

[Lute Kamstra]

lisp/subr.el currently defines assq-delete-all.  What about providing
rassq-delete-all as well?

Lute.


(defun rassq-delete-all (value alist)
  "Delete from ALIST all elements whose cdr is `eq' to VALUE.
Return the modified alist.
Elements of ALIST that are not conses are ignored."
  (let ((tail alist))
    (while tail
      (when (and (consp (car tail)) (eq (cadr tail) value))
	(setq alist (delq (car tail) alist)))
      (setq tail (cdr tail)))
    alist))

Re: Adding rassq-delete-all to lisp/subr.el.

[Lute Kamstra]

Lute Kamstra <Lute.Kamstra.lists@xs4all.nl> writes:

> (defun rassq-delete-all (value alist)
>   "Delete from ALIST all elements whose cdr is `eq' to VALUE.
> Return the modified alist.
> Elements of ALIST that are not conses are ignored."
>   (let ((tail alist))
>     (while tail
>       (when (and (consp (car tail)) (eq (cadr tail) value))
                                           ^^^^
Whoops:                                    cdar
> 	(setq alist (delq (car tail) alist)))
>       (setq tail (cdr tail)))
>     alist))

Re: Adding rassq-delete-all to lisp/subr.el.

[David Kastrup]

Lute Kamstra <Lute.Kamstra.lists@xs4all.nl> writes:

> lisp/subr.el currently defines assq-delete-all.  What about providing
> rassq-delete-all as well?
>
> Lute.
>
>
> (defun rassq-delete-all (value alist)
>   "Delete from ALIST all elements whose cdr is `eq' to VALUE.
> Return the modified alist.
> Elements of ALIST that are not conses are ignored."
>   (let ((tail alist))
>     (while tail
>       (when (and (consp (car tail)) (eq (cadr tail) value))
> 	(setq alist (delq (car tail) alist)))
>       (setq tail (cdr tail)))
>     alist))

That is not what the function does.  You are confusing cadr and cdar.

And I am not too fond of quadratic complexity algorithms.  It would
seem much better to write

(defun rassq-delete-all (value alist)
  "Delete from ALIST all elements whose cdr is `eq' to VALUE.
Return the modified alist.
Elements of ALIST that are not conses are ignored."
  (while (and (consp (car alist)) (eq (cdr (car alist)) value))
    (setq alist (cdr alist)))
  (prog1 alist
    (let ((tail alist))
      (while (setq tail (cdr tail))
        (if (and (consp (car tail))
		 (eq (cdr (car tail)) value))
	    (setcdr alist (cdr tail))
	  (setq alist tail))))))

If one takes
(defun checkit ()
  (setq x nil)
  (dotimes (i 100001) (push (cons (- i) i) x))
  (float-time
   (time-since (prog1 (current-time)
		 (dotimes (i 101)
		   (setq x (rassq-delete-all (* 100 i) x)))))))

The discrepancy seems pretty small after byte compilation, which seems
strange.

What makes a _significant_ difference is using (car (cdr...)) instead
of (cadr...): for some unfathomable reason, cadr introduces a
temporary binding to "x", and that is really expensive in the inner
loop.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Adding rassq-delete-all to lisp/subr.el.

[Lute Kamstra]

David Kastrup <dak@gnu.org> writes:

> Lute Kamstra <Lute.Kamstra.lists@xs4all.nl> writes:
>
>> lisp/subr.el currently defines assq-delete-all.  What about providing
>> rassq-delete-all as well?
>>
>> Lute.
>>
>>
>> (defun rassq-delete-all (value alist)
>>   "Delete from ALIST all elements whose cdr is `eq' to VALUE.
>> Return the modified alist.
>> Elements of ALIST that are not conses are ignored."
>>   (let ((tail alist))
>>     (while tail
>>       (when (and (consp (car tail)) (eq (cadr tail) value))
>> 	(setq alist (delq (car tail) alist)))
>>       (setq tail (cdr tail)))
>>     alist))
>
> That is not what the function does.  You are confusing cadr and cdar.

Yup, I noticed.

> And I am not too fond of quadratic complexity algorithms.

Me neither, but I was lazy and adapted assq-delete-all.

> It would seem much better to write
>
> (defun rassq-delete-all (value alist)
>   "Delete from ALIST all elements whose cdr is `eq' to VALUE.
> Return the modified alist.
> Elements of ALIST that are not conses are ignored."
>   (while (and (consp (car alist)) (eq (cdr (car alist)) value))
>     (setq alist (cdr alist)))
>   (prog1 alist
>     (let ((tail alist))
>       (while (setq tail (cdr tail))
>         (if (and (consp (car tail))
> 		 (eq (cdr (car tail)) value))
> 	    (setcdr alist (cdr tail))
> 	  (setq alist tail))))))

Nice.  I find this rewrite a bit easier to understand, though:

(defun rassq-delete-all (value alist)
  "Delete from ALIST all elements whose cdr is `eq' to VALUE.
Return the modified alist.
Elements of ALIST that are not conses are ignored."
  (while (and (consp (car alist)) (eq (cdr (car alist)) value))
    (setq alist (cdr alist)))
  (let ((tail alist) tail-cdr)
    (while (setq tail-cdr (cdr tail))
      (if (and (consp (car tail-cdr))
	       (eq (cdr (car tail-cdr)) value))
	  (setcdr tail (cdr tail-cdr))
	(setq tail tail-cdr))))
  alist)

> If one takes
> (defun checkit ()
>   (setq x nil)
>   (dotimes (i 100001) (push (cons (- i) i) x))
>   (float-time
>    (time-since (prog1 (current-time)
> 		 (dotimes (i 101)
> 		   (setq x (rassq-delete-all (* 100 i) x)))))))
>
> The discrepancy seems pretty small after byte compilation, which seems
> strange.

delq in defined in C and it's only called 101 times.

> What makes a _significant_ difference is using (car (cdr...)) instead
> of (cadr...): for some unfathomable reason, cadr introduces a
> temporary binding to "x", and that is really expensive in the inner
> loop.

Strange, (cadr ...) is just a defsubst for (car (cdr ...)).  So
compiled it should make no difference.

Lute.

Re: Adding rassq-delete-all to lisp/subr.el.

[David Kastrup]

Lute Kamstra <Lute.Kamstra.lists@xs4all.nl> writes:

> David Kastrup <dak@gnu.org> writes:
>
>> And I am not too fond of quadratic complexity algorithms.
>
> Me neither, but I was lazy and adapted assq-delete-all.
>
>> If one takes
>> (defun checkit ()
>>   (setq x nil)
>>   (dotimes (i 100001) (push (cons (- i) i) x))
>>   (float-time
>>    (time-since (prog1 (current-time)
>> 		 (dotimes (i 101)
>> 		   (setq x (rassq-delete-all (* 100 i) x)))))))
>>
>> The discrepancy seems pretty small after byte compilation, which seems
>> strange.
>
> delq in defined in C and it's only called 101 times.

Ah, right.  If we removed all elements piecemeal, this would be
different.

>> What makes a _significant_ difference is using (car (cdr...)) instead
>> of (cadr...): for some unfathomable reason, cadr introduces a
>> temporary binding to "x", and that is really expensive in the inner
>> loop.
>
> Strange, (cadr ...) is just a defsubst for (car (cdr ...)).  So
> compiled it should make no difference.

The defsubst binds and unbinds x.  I consider that a byte compiler
deficiency.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Adding rassq-delete-all to lisp/subr.el.

[Richard Stallman]

    lisp/subr.el currently defines assq-delete-all.  What about providing
    rassq-delete-all as well?

Why?

I don't want to add functions to Emacs merely for completeness' sake.

Re: Adding rassq-delete-all to lisp/subr.el.

[Lute Kamstra]

Richard Stallman <rms@gnu.org> writes:

>     lisp/subr.el currently defines assq-delete-all.  What about providing
>     rassq-delete-all as well?
>
> Why?
>
> I don't want to add functions to Emacs merely for completeness' sake.

I could use it for removing things from auto-mode-alist:

Index: lisp/loadhist.el
===================================================================
RCS file: /cvsroot/emacs/emacs/lisp/loadhist.el,v
retrieving revision 1.32
diff -C2 -r1.32 loadhist.el
*** lisp/loadhist.el	19 Apr 2005 15:08:05 -0000	1.32
--- lisp/loadhist.el	19 Apr 2005 20:27:30 -0000
***************
*** 189,194 ****
  			(memq x unload-feature-special-hooks)))	; Known abnormal hooks etc.
  	   (dolist (y unload-hook-features-list)
! 	     (when (eq (car-safe y) 'defun)
! 	       (remove-hook x (cdr y))))))))
      (when (fboundp 'elp-restore-function) ; remove ELP stuff first
        (dolist (elt unload-hook-features-list)
--- 189,201 ----
  			(memq x unload-feature-special-hooks)))	; Known abnormal hooks etc.
  	   (dolist (y unload-hook-features-list)
! 	     (when (and (eq (car-safe y) 'defun)
! 			(not (get (cdr y) 'autoload)))
! 	       (remove-hook x (cdr y)))))))
!       ;; Remove any feature-symbols from auto-mode-alist as well.
!       (dolist (y unload-hook-features-list)
! 	(when (and (eq (car-safe y) 'defun)
! 		   (not (get (cdr y) 'autoload)))
! 	  (setq auto-mode-alist
! 		(rassq-delete-all (cdr y) auto-mode-alist)))))
      (when (fboundp 'elp-restore-function) ; remove ELP stuff first
        (dolist (elt unload-hook-features-list)

Re: Adding rassq-delete-all to lisp/subr.el.

[Richard Stallman]

    I could use it for removing things from auto-mode-alist:

That is one plausible use.  Are there others?

Re: Adding rassq-delete-all to lisp/subr.el.

[Lute Kamstra]

Richard Stallman <rms@gnu.org> writes:

>     I could use it for removing things from auto-mode-alist:
>
> That is one plausible use.  Are there others?

I did a quick grep on Emacs' sources and found a couple of places
where rassq-delete-all could be used:

,----[ files.el ]
| 	     (delq (rassq 'ange-ftp-completion-hook-function tem) tem)))))
`----

,----[ image-file.el ]
|   ;; Remove existing handler
|   (let ((existing-entry
| 	 (rassq 'image-file-handler file-name-handler-alist)))
|     (when existing-entry
|       (setq file-name-handler-alist
| 	    (delq existing-entry file-name-handler-alist))))
`----

,----[ net/tramp-ftp.el ]
|   (let ((a1 (rassq 'ange-ftp-hook-function file-name-handler-alist))
| 	(a2 (rassq 'ange-ftp-completion-hook-function file-name-handler-alist)))
|     (setq file-name-handler-alist
| 	  (delete a1 (delete a2 file-name-handler-alist)))))
`----

,----[ url/url-handlers.el ]
|     ;; Remove old entry, if any.
|     (setq file-name-handler-alist
| 	  (delq (rassq 'url-file-handler file-name-handler-alist)
| 		file-name-handler-alist))
`----

Lute.

Re: Adding rassq-delete-all to lisp/subr.el.

[Richard Stallman]

    > Strange, (cadr ...) is just a defsubst for (car (cdr ...)).  So
    > compiled it should make no difference.

    The defsubst binds and unbinds x.  I consider that a byte compiler
    deficiency.

In general, the byte compiler cannot omit that binding.
It does not know that the binding won't be  referred to
from one of the functions that is called.

However, in this specific case, cadr calls only primitives, so that
can't happen.  It would not be too hard to change the compiler to
recognize that and eliminate the binding.  That could be a useful
thing to work on, but shouldn't be installed now.

Re: Adding rassq-delete-all to lisp/subr.el.

[Richard Stallman]

I guess this is enough potential uses to justify a harmless
small function.

Re: Adding rassq-delete-all to lisp/subr.el.

[Lute Kamstra]

David Kastrup <dak@gnu.org> writes:

> Lute Kamstra <Lute.Kamstra.lists@xs4all.nl> writes:
>
>> David Kastrup <dak@gnu.org> writes:
>>
>>> And I am not too fond of quadratic complexity algorithms.
>>
>> Me neither, but I was lazy and adapted assq-delete-all.
>>
>>> If one takes
>>> (defun checkit ()
>>>   (setq x nil)
>>>   (dotimes (i 100001) (push (cons (- i) i) x))
>>>   (float-time
>>>    (time-since (prog1 (current-time)
>>> 		 (dotimes (i 101)
>>> 		   (setq x (rassq-delete-all (* 100 i) x)))))))
>>>
>>> The discrepancy seems pretty small after byte compilation, which seems
>>> strange.
>>
>> delq in defined in C and it's only called 101 times.
>
> Ah, right.  If we removed all elements piecemeal, this would be
> different.

No, that would still run in linear time.  To get quadratic behavior,
you can do this:

(defun checkit ()
  (setq x nil)
  (dotimes (i 100000)
    (push '(a . a) x)
    (push '(b . b) x))
  (float-time
   (time-since
    (prog1 (current-time)
      (rassq-delete-all 'a x)))))

Lute.