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:
Code: Select all
(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.