4 ms·
`append` on lists is equivalent to concatenation, not Python's append which is equivalent to `vector-push` or `vector-push-extend` in Lisp (and which, as the na
by Jtsummers 4y ago
`append` on lists is equivalent to concatenation, not Python's append which is equivalent to `vector-push` or `vector-push-extend` in Lisp (and which, as the name suggests, takes a vector for the place and not a list). For performance reasons, the more conventional behavior in Lisp to collect values would be:
(let ((some-place nil))
(push an-item some-place)
...
(nreverse some-place)) ;; if the order really matters, you see the same pattern in Erlang and others
Pushing (and popping) work on the front of lists. Counterintuitively, vector-push and vector-pop work on the end of the vector (though the rationale around performance is the same,). By pushing/popping on the front of the list the action can be done in constant time. `push item place` is equivalent to this whether it's precisely this under the hood for an implementation or not:
(setf place (cons item place))
Pop is this:
(prog1
(car place)
(setf place (cdr place)))
(Maybe I've been spending too much time in the hyper spec, my equivalence examples could have been copy/pasted from it and I wrote them before double checking.)
Pop: http://clhs.lisp.se/Body/m_pop.htm#pop http://clhs.lisp.se/Body/m_pop.htm#pop
Push: http://clhs.lisp.se/Body/m_push.htm#push http://clhs.lisp.se/Body/m_push.htm#push
- lispm 4y ago> For performance reasons, the more conventional behavior in Lisp to collect values would be What you describe is what a human typical would write. For tools this is optimized. For example in (loop for e in list collect (oddp e)) this usually would be optimized. It would not add to the end and then reverse. Instead, it would keep a pointer to the end and add to the end via that pointer.
- kagevf 4y agoWould the code to maintain a pointer on the last element look something like this? (let* ((list (list 1 2 3 4)) (last (last list))) (rplacd last (list 5 6)) (setf last (last last)) (format t "list: ~a~%last: ~a~%" list last)) => list: (1 2 3 4 5 6) last: (6)
- lispm 4y agoin an iteration: (let* ((rlist (list '())) (last list)) (flet ((collect (item) (setf (cdr last) (list item) last (cdr last)) item) (finish () (cdr rlist))) (dotimes (i 10) (collect i)) (finish)))
- kagevf 4y agoThank you for the reply! And I see that even in my original attempt, I could have used (setf (cdr)) instead of (rplacd)...
- lispm 4y ago(let* ((rlist (list '())) (last rlist)) (flet ((collect (item &aux (cons-cell (list item))) (setf (cdr last) cons-cell last cons-cell) item) (finish () (cdr rlist))) (dotimes (i 10) (collect i)) (finish)))
- deleted 4y ago[deleted]