Common Lisp: is delete-if the same as setf + remove-if?

Question

The following code generates prime from 1 to n:

(defun prime-list(n)
  (let ((a)(b)(x (floor (sqrt n))))
    (loop for i from (floor n 6) downto 1 do
          (push (1+ (* 6 i)) a)
          (push (1- (* 6 i)) a))
    (loop while (<= (car a) x) do
          (push (car a) b)
          (setf a (remove-if #'(lambda(m)(or (= 0 (mod m (car a))) (> m n))) a)))
    (append '(2 3) (reverse b) a)))

It seems to me the part

(setf a (remove-if #'XXX a))

can be replaced by

(delete-if #'XXX a)

And I hoped this would make it faster. However when I made that change the function now get into an infinite loop and never returns. Why?

**ERROR1:** should be `while (<= (car a) x)` **ERROR2:** since any prime is of form `6i+-1`, any prime's square modulo 6 is 1. If `n == p^2-1` for some prime `p`, it follows `n == 6i` for some `i`. The code in Q will include `6i+1 == p^2` into the list; but will test by `x = sqrt(n) < p` so will include `p^2` in the output. Thus, when called with `n=p^2-1` for any prime, the above will produce `p^2` as last elt in its output. (I don't edit this in because the Q is not about the validity of code). — Will Ness, Mar 01 '13 at 12:24
also, this is a trial division sieve, which is much less efficient than the sieve of Eratosthenes (which *counts up in equal increments* to find the multiples, not tests them by division). — Will Ness, Mar 01 '13 at 12:39
@WillNess TURE. I was playing with that and didn't think about efficiency. Later I used bit-array and you can find the code here: http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Common_Lisp (the 2nd one. Comments are welcome.) — h__, Mar 01 '13 at 21:49
Understood. I just note this for the benefit of a casual reader. (error1 is now fixed; error2 still remains). — Will Ness, Mar 01 '13 at 22:15
@WillNess changed. But it is likely not the best way to fix it. ;) — h__, Mar 02 '13 at 02:05

score 7 · Accepted Answer · answered Jul 26 '12 at 04:27

As mentioned in the comments, you need to set the variable.

DELETE-IF is mostly a destructive version of REMOVE-IF. REMOVE-IF returns a freshly consed sequence, which does not contain the removed elements. DELETE-IF may return a sequence which is reused.

If you have a variable, which is bound to a list, you still need to set the result. Above functions return results, but they don't set variables to the result. In case of a list, the result of a DELETE-IF operation can be the empty list and there is no way the side effect can be, that a variable can be set to it - when it was pointing to a non-empty list.

Also, the returned value when the first element is in need of removal will always be different from the original sequence (there's no sensible way of surgically removing the first cons of a list while still having a poiter to that cons, so return the first non-removed cons instead). — Vatine, Jul 26 '12 at 10:51

cdk · Answer 2 · 2012-07-26T01:31:09.480

I don't have very much CL experience, but I've done a lot of work in Scheme.

In the second version (sans setf a) the remove-if expression is evaluated, but it does nothing to actually change a. loop is a macro in CL, it just evaluates expressions, but doesnt use the results of those expressions like a recursive function would.

So in the first version, the value of a is changed each time the loop runs due to the setf, but in the second, the value of a is constant throughout. Thus (car a) never changes and the loop never terminates.

we can compare the results of macroexpand on both the loop statements:

without setf:

(MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
 (BLOCK NIL
  (LET NIL
   (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
    (TAGBODY SYSTEM::BEGIN-LOOP
     (PROGN (UNLESS (< (CAR A) X) (LOOP-FINISH))
      (PROGN (PUSH (CAR A) B) (REMOVE-IF #'(LAMBDA (M) (= 0 (MOD M (CAR A)))) A)))
     (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
     (MACROLET
      ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP))))))))) ;

with setf:

(MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
 (BLOCK NIL
  (LET NIL
   (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
    (TAGBODY SYSTEM::BEGIN-LOOP
     (PROGN (UNLESS (< (CAR A) X) (LOOP-FINISH))
      (PROGN (PUSH (CAR A) B)
       (SETF A (REMOVE-IF #'(LAMBDA (M) (= 0 (MOD M (CAR A))))) A)))
     (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
     (MACROLET
      ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP))))))))) ;

you can see that in the first loop the remove-if expression is evaluated, but its result isn't used.

Oops, I guess I asked the wrong question, I mean "`(setf a (remove-if #'XXX a))` can be replaced by `(delete-if #'XXX a)`" — h__, Jul 26 '12 at 01:34

score -1 · Answer 3 · answered Jul 26 '12 at 01:33

-1

Chris is correct.

You may speed things up by using delete-if in place of remove-if

answered Jul 26 '12 at 01:33

Doug Currie

40,708
1
95
119

1

Sorry, I mean to ask about delete-if (I wrote delete-if in the title), I found delete-if doesn't work. I'm using Lispworks, and when I try delete-if, some very weird thing happened: delete if won't remove the first entry even if the first entry is supposed to be removed. See [link](https://dl.dropbox.com/u/9034084/Screen-shot%203.png) – h__ Jul 26 '12 at 01:39
1

You still need to use `setf`: `(setf foo (delete-if #'some-pred foo))`. – Hugh Jul 26 '12 at 03:51
You still need the `(setq a (delete-if ...)` – Doug Currie Jul 26 '12 at 03:51

Common Lisp: is delete-if the same as setf + remove-if?

3 Answers3

Linked