Lisp idioms/functions for common tasks

So I've been mucking with Lisp for a few days, finding my way, getting the feel of it, and now I'm beginning to wonder what the canonical way to do certain tasks is. For example, to append a new element at the end of a list I would say

(setf (cdr (last list)) (cons 'new nil))

However, I suspect there's a function to do that and do it better. The HyperSpec is very useful but only if you know what you're looking for, which I don't. I'd also like to know how these functions perform: does last require O(n) time, does push create a new list or extend the old one, are these details implementation specific or part of the standard, things like that. Any reference will be much appreciated.

In Lisp you usually you don't append conses to the end of a list. Instead you prepend them with push and then apply nreverse. This isn't only more convienient but also about the same speed (compared to appending with and efficient algorithm).

If you really need to append to a list then use either append or it's destructive version nconc (which does what you were actually talking about).

PS: push extends the list. And last is (of course) O(n).

foregam wrote:does last require O(n) time

yes, but see below

foregam wrote:does push create a new list or extend the old one

It extends the old one, but you could think of it as creating a new list as well as long as you refrain from mutating your lists (using setf on them). The thing to realize is that it while it reuses the memory of the old list, that doesn't affect any other references to that old list. Take for instance:

(let ((lst1 '(1 2 3 4)))
  (let ((lst2 lst1))
    (push 0 lst2)
    lst2 ))
=> (0 1 2 3 4) ; As expected

(let ((lst1 '(1 2 3 4)))
  (let ((lst2 lst1))
    (push 0 lst2)
    lst1 ))
=> (1 2 3 4) ; Original list left unchanged

This is the defining characteristic of a persistent data structure or a functional data structure.

foregam wrote:are these details implementation specific or part of the standard

In these cases, they are usually thought of as part of the standard, although I am not sure, actually. The structure of a cons cell is a well defined thing, however I believe that as long as your implementation of cons, car, and cdr and friends all behave as specified your Lisp would be ANSI compliant.

Clearly, for any singly linked list, last must take O(n) time. You could design your own data structure that might, say, have a way to quickly access the last element of the list (like a skip list or even just a reference to the last cons cell), but it would almost certainly violate any assumption of a list being a persistent data structure and thus wouldn't be an ANSI compliant Lisp list (though perhaps still useful). You could design your own lists just like FSet does (they call them seqs) where accessing any element in the list is O(log n) which is nice if you are going to do random access but slower than when you only intend to access the first few elements or all of them. Since people only use lists for purposes where you don't need to access the end of a long list very often, switching a Lisp implementation of lists might not have a worthwhile result in terms of optimization.

Maybe the question about last was a bit silly, but then look here. Anyway, you get the idea what kind of details are of interest to me. Is there something like the CL Cookbook but a bit more detailed?