Page 1 of 1
Pick and remove
Posted: 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
Posted: 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
Posted: 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
Posted: 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
Posted: 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
Posted: 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
Posted: 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?