python list handling and Lisp list handling

[Carl Banks]

On Apr 24, 8:19 am, Mark Tarver <dr.mtar... at ukonline.co.uk> wrote:
> This page says that Python lists are often flexible arrays
>
> http://www.brpreiss.com/books/opus7/html/page82.html
>
> but also says that their representation is implementation dependent.
> As far as I see this should mean that element access in Python should
> run in constant time.  Now if so this is a boon, because generally
>
> 'A list is a sequence of elements, but it is not a single primitive
> object; it is made of cons cells, one cell per element. Finding the
> nth element requires looking through n cons cells, so elements farther
> from the beginning of the list take longer to access. But it is
> possible to add elements to the list, or remove elements.'
>
> (fromhttp://www.chemie.fu-berlin.de/chemnet/use/info/elisp/elisp_7.html)
>
> But are Python lists also indistinguishable from conventional
> Lisplists for list processing.  For example, can I modify a Python
> list non-destructively?  Are they equivalent to Lisp lists. Can CAR
> and CDR in Lisp be thought of as
>
> def car (x):
>   return x[0]
>
> def cdr (x):
>   return x[1:]
>
> The idea of a list in which elements can be accessed in constant time
> is novel to me.

That's because Python lists aren't lists.

It might be an interesting exercise to compare Python lists and Lisp
lists, but you should do it under the understanding that they are not
analogous types.  (A Python list is analogous to a Lisp vector.)  The
two objects have almost no similarity in typical their manner of use;
even the way you iterate through them is different.

You could, as you've tried to do here, operate on Python lists the
same way you operate on Lisp lists, but you'd just be doing things the
hard way.  Whatever you're trying to do with cons, car, and cdr,
chances are Python has a high-level way to do it built in that
performs a lot better.

Then again, Lispers seem to like to reimplement high-level operations
from low-level primitives every time they need it.  So if you liked
doing that you might not mind doing a lot of extra work using your
homebrew cons, car, and cdr.


Carl Banks