Pick and remove

Discussion of Common Lisp
Post Reply
White_Owl
Posts: 15
Joined: Wed Sep 13, 2017 2:49 pm

Pick and remove

Post by White_Owl » Wed Oct 04, 2017 9:29 am

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
Posts: 166
Joined: Sun Nov 28, 2010 4:21 pm

Re: Pick and remove

Post by pjstirling » Wed Oct 04, 2017 10:26 am

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
Posts: 78
Joined: Mon Dec 01, 2014 12:29 pm
Contact:

Re: Pick and remove

Post by David Mullen » Wed Oct 04, 2017 10:54 am

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
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Pick and remove

Post by nuntius » Wed Oct 04, 2017 7:40 pm

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
Posts: 166
Joined: Sun Nov 28, 2010 4:21 pm

Re: Pick and remove

Post by pjstirling » Thu Oct 05, 2017 6:03 pm

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
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Pick and remove

Post by nuntius » Thu Oct 05, 2017 8:09 pm

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
Posts: 78
Joined: Mon Dec 01, 2014 12:29 pm
Contact:

Re: Pick and remove

Post by David Mullen » Fri Oct 06, 2017 11:28 am

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?

Post Reply