moving an element of a list to another list

Let's say i need to remove the nth element of the list "l" and push it at the beginning of list "out".
The best i could figure out is :

(progn
  (push (nth n l) out)
  (setf l (delete (nth n l) l))

But it looks pretty inefficient to me. "(nth n l)" is evaluated twice and "(delete (nth n l) l)" doesn't sound good.
Is there a better way to do that ?

Is there a better way? Yes, but you have to write it at a lower level (doing your own loop over the list, your own cdr manipulations, etc.).

If this isn't a performance issue, I would focus on getting the rest of your code working before worrying about this. At that time, the answer may be to optimize this code, or it may be to use a different data structure.

Destructive:

(if (zerop n)
    (progn (push (car l) out)
           (setf l (cdr l)))
    (let ((prevcdr (nthcdr (- n 1) l)))
      (push (cadr prevcdr) out)
      (setf (cdr prevcdr) (cddr prevcdr))))

Non-destructive:

(progn
  (push (nth n l) out)
  (setf l (nconc (subseq l 0 n) (nthcdr (1+ n) l))))

I'd say that the biggest problem with that code is not preformance, but it will delete multiple copies of the same element if it is found. If that is what you want, use let to store the nth value instead of computing it twice.

Thanks Gugamilare, the first one look like what i was looking for.
I was hoping there was a standard function that could help in this kind of case. Something like "pop" but which can work in the middle of a list. But now i realize that the "one way" nature of the lists makes this difficult to do.

gugamilare wrote:
I'd say that the biggest problem with that code is not preformance, but it will delete multiple copies of the same element if it is found. If that is what you want, use let to store the nth value instead of computing it twice.

Good point ! In my case this was not an issue, i forgot to mention that all the elements of l are different. But it is sure something to be aware of.

vernonsolo wrote:Thanks Gugamilare, the first one look like what i was looking for.
I was hoping there was a standard function that could help in this kind of case. Something like "pop" but which can work in the middle of a list. But now i realize that the "one way" nature of the lists makes this difficult to do.

Haven't you learned Lisp yet?

Non-destructive:

(defmacro pop-nth (n l)
  (with-gensyms (nvar lvar ncdr)
    `(let* ((,nvar ,n)
            (,lvar ,l)
            (,nthcdr (nthcdr ,nvar ,lvar)))
       (prog1 (car ,nthcdr)
         (setf ,l (nconc (subseq ,lvar 0 ,nvar)
                         (cdr ,nthcdr)))))))

Destructive:

(defmacro npop-nth (n l)
  (with-gensyms (nvar lvar prevcdr)
    `(let ((,nvar ,n)
           (,lvar ,l))
       (if (zerop ,nvar)
           (prog1 (car ,lvar)
             (setf ,l (cdr ,lvar)))
           (let ((,prevcdr (nthcdr (- ,nvar 1) ,varl)))
             (prog1 (cadr ,prevcdr)
               (setf (cdr ,prevcdr) (cddr ,prevcdr))))))))

Note that I just wrote that, I didn't test anything, but that might be enough to get the idea

gugamilare wrote: Haven't you learned Lisp yet?

I just started few days ago

I tried the non-destructive one in my program, but i had problem with 'with-gensyms' so i modified it to :

(defmacro pop-nth (n l)
  (let ((nvar (gensym)) (lvar (gensym)) (ncdr (gensym)))
    `(let* ((,nvar ,n)
            (,lvar ,l)
            (,ncdr (nthcdr ,nvar ,lvar)))
       (prog1 (car ,ncdr)
         (setf ,l (nconc (subseq ,lvar 0 ,nvar)
                         (cdr ,ncdr)))))))

then my ugly code is replaced by :

(push (pop-nth n l) out)

and it works ! it's even like 5 or 10% faster

It is my first macro

Thanks for your help

PS: then i tried the destructive one and gained 20% speed from the original

vernonsolo wrote:PS: then i tried the destructive one and gained 20% speed from the original

If you try it with bigger lists, the performance gain will be even greater

I probably wouldn't write a macro for this problem, I would isolate the problem of 'stealing' an item from a list:

(defmacro awhen (test &rest code)
  `(let ((it ,test))
     (when it ,@code)))

(defun steal (n list)
  (awhen (nthcdr (1- n) list)
    (prog1 (cadr it) (rplacd it (cddr it)))))

And it is used like this:

(defvar *test-input* '(a b c d e f g))
(steal 1 *test-input*)   ;; Returns 'b, *test-output* is now (a c d e f g)

There is one problem --- what happens if you steal item 0 from a list? It won't work, and it cannot be made to work because steal is a utility function, and it would be unwise to hardcode it so it would setf *test-input* to (cdr *test-input*) for the zero case. However, we can write a function using steal that has this knowledge.

(defvar *input* '(a b c d e))
(defvar *output* nil)

(defun steal/pop (n)
  (if (and *test-input* (zerop n))
      (setf *output* (cons (car *input*) *output*) 
	    *input* (cdr *input*))
      (and (< n (length *input*)) (push (steal n *input*) *output*))))

This method does exactly what you describe. It steals the Nth element from *input*, and pushes it onto *output*, I also made it do bounds checking so it won't do anything if N is larger than *input*. The routine is hardcoded to reference those external variables, which is ideal because its simple.

If you have a number of lists that you need to modify, and you don't want to have a customized steal routine for each one, you can use a sentinal value like so:

(defvar *new-input* '(sentinal a b c d e))

By putting a sentinal value in as item 0, we have no reason to ever require a (steal 0 *new-input*). This works fine so long as we remember to perform all other operations (like length, find, position, etc) upon (cdr *new-input*) and not the full *new-input*.

Thanks Warren for the suggestions, it was very interesting. I think it is always good to know more than one way to do something
This "awhen" macro... I cannot count how many time i had to use this mechanism and yet i never thought of doing a macro out of it, thanks for that too

The 'a' stands for anamorphic. Paul Graham's 'On Lisp' has it (and anamorphic if, cond, etc), but I think the technique is older than that still. PG also has the definition of 'with-gensyms'. I won't go into details since PG explains it in that book, which is freely available as a downloadable pdf at http://www.paulgraham.com/onlisp.html.

See also Anaphora.

Warren Wilkinson wrote:There is one problem --- what happens if you steal item 0 from a list? It won't work, and it cannot be made to work because steal is a utility function, and it would be unwise to hardcode it so it would setf *test-input* to (cdr *test-input*) for the zero case.

That is the reason I chose to write a macro, not a function. And, since pop-nth (or steal) is a generalization of pop, which is a macro, it feels more natural to me that it is also pop-nth is coded as a macro. Writing a macro also allows a non-destructive version, which is important if your lists share tails.

Your right in that a non-destructive version of steal can't be made because it would have to save the functionally updated list somewhere, which would be outside knowledge.

I used a function out of personal habit. I'll try to change problems slightly (i.e. using sentinals) to allow a function based solution before I try macros. Macros have a way of growing; a little here.. another macro there... a extra conditional to its output here... etc. You can have some pretty flimsy towers built on macros.

Mostly I just want to keep things simple and macros can sometimes be a crutch that makes a bad design work. This is not one of those times, but I've got my macro-rare style internalized now =).

Warren Wilkinson wrote:The 'a' stands for anamorphic. Paul Graham's 'On Lisp' has it (and anamorphic if, cond, etc), but I think the technique is older than that still. PG also has the definition of 'with-gensyms'. I won't go into details since PG explains it in that book, which is freely available as a downloadable pdf at http://www.paulgraham.com/onlisp.html.

Just a quibble... That should be "anaphoric," not "anamorphic."