Page 1 of 1

Pick and remove

PostPosted: Wed Oct 04, 2017 9:29 am
by 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...

Re: Pick and remove

PostPosted: Wed Oct 04, 2017 10:26 am
by 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)))))

Re: Pick and remove

PostPosted: Wed Oct 04, 2017 10:54 am
by 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.

Re: Pick and remove

PostPosted: Wed Oct 04, 2017 7:40 pm
by 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.

Re: Pick and remove

PostPosted: Thu Oct 05, 2017 6:03 pm
by 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.

Re: Pick and remove

PostPosted: Thu Oct 05, 2017 8:09 pm
by 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.

Re: Pick and remove

PostPosted: Fri Oct 06, 2017 11:28 am
by 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?