Pick and remove

Discussion of Common Lisp

Pick and remove

Postby 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...
White_Owl
 
Posts: 15
Joined: Wed Sep 13, 2017 2:49 pm

Re: Pick and remove

Postby 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)))))
pjstirling
 
Posts: 140
Joined: Sun Nov 28, 2010 4:21 pm

Re: Pick and remove

Postby 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.
David Mullen
 
Posts: 65
Joined: Mon Dec 01, 2014 12:29 pm

Re: Pick and remove

Postby 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.
User avatar
nuntius
 
Posts: 530
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Pick and remove

Postby 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.
pjstirling
 
Posts: 140
Joined: Sun Nov 28, 2010 4:21 pm

Re: Pick and remove

Postby 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.
User avatar
nuntius
 
Posts: 530
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Pick and remove

Postby 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?
David Mullen
 
Posts: 65
Joined: Mon Dec 01, 2014 12:29 pm


Return to Common Lisp

Who is online

Users browsing this forum: Bing [Bot] and 2 guests

cron