Pick and remove

[White_Owl]

I want to pick an element from the list by position and remove that element from the list.
Something like:

Code: Select all

(defun pick (index list)
   (let ((e))
      (setf e (nth index list))
      (delete e list :start index :end (1+ index))
      e))

Code: Select all

(defvar *mylist* '(a b c d e)) => *MYLIST*
(pick 2 *mylist*) => C
*mylist* => (A B D E)

But I really do not like the code for pick. I think there should be a more elegant solution...

[pjstirling]

I don't think there's an elegant solution to this problem, but I had to write a version that doesn't walk the list twice for code that grabs a random selection from a list in the thousands.

Code: Select all

(defun pop-nth-helper (n previous)
  (unless (< 0 n)
    (error "pop-nth-helper only works for 0 < n"))
  (do ()
      ((= n 1))
    (setf previous (cdr previous)
          n (1- n)))
  (prog1
      (cadr previous)
    (setf (cdr previous) (cddr previous))))

(defmacro pop-nth (n place)
  (let ((counter (gensym)))
    `(let ((,counter ,n))
       (if (= ,counter 0)
	   (pop ,place)
           ;; else                                                                                                                                                                                                 
           (pop-nth-helper ,counter ,place)))))

[David Mullen]

DELETE is of course a generic sequence function. But you said "list" so here's one (destructive) solution with list-bashing specificity:

Code: Select all

(defun pick (index list)
  (check-type index fixnum)
  (loop for prev = nil then tail
        for count fixnum from 0
        for tail on list
        when (= count index)
        return (prog1 (car tail)
                 (if (null prev)
                     (cdr list)
                     (setf (cdr prev)
                           (cdr tail))))))

Except it doesn't work if you're deleting the first element of the list—so you need a macro to set the actual place.

[nuntius]

This is a spot where recursion shines.
You can treat the list as immutable, and creating a new list is fairly cheap since a traversal is required anyway.
So the caller gets the value and a new list, instead of destructively modifying the original list.
Unfortunately, this gets a little buried in the trappings to enable TCO and the syntax required for multiple values.

Code: Select all

(deftype non-negative-fixnum ()
  `(integer 0 ,most-positive-fixnum))

(defun pick (index list)
  (declare (non-negative-fixnum index) ; use a type check to guarantee that (>= index 0)
	   (optimize (speed 3))) ; enable TCO
  (if (= index 0)
      (values (car list) (cdr list))
    (multiple-value-bind (x tail) (pick (1- index) (cdr list))
			 (values x (cons (car list) tail)))))

Here's an example use. Note that SETF on VALUES can be used instead of MULTIPLE-VALUE-BIND.

Code: Select all

(let ((x nil)
      (l '(1 2 3 4 5)))
  (setf (values x l) (pick 3 l))
  (list x l))

Relevant links:
https://0branch.com/notes/tco-cl.html
https://common-lisp.net/project/cdr/doc ... types.html
http://wiki.c2.com/?PurelyFunctionalDataStructures


Edit:
The TCO isn't working for me. A simple "(pick 1000000 nil)" blows the stack. Probably because of the M-V-B.
I don't feel like fixing this. The solution would look like David's code, just in a recursive form, probably using an flet helper.

[pjstirling]

While it's true that you'll be walking the list either way, consing up a new list doesn't make a lot of sense

You care about the remainder list because you will be puilling more values out of it (otherwise you'd just use NTH)

If you try to pick a sub-list of 100 items from a list of 5000 items then you would create 247,475 new cons cells on average. Copying the list and destructively modifying the copy is much cheaper.

[nuntius]

There are cases where the consing is quite cheap. For example, a single pick, or if the pick index is always small.

Don't know enough about the OP's use case to say one way or the other.

Maybe he should copy the whole list into an array. Then pick becomes aref or svref.

Much better amortized time than repeated list traversals, cons or no cons.

[David Mullen]

Well, now I'm curious—what is this thing: a set-like or queue-like thing? Is there a heuristic for picking a particular element?