python list handling and Lisp list handling
dr.mtarver at ukonline.co.uk
Sat Apr 25 09:07:19 CEST 2009
On 25 Apr, 05:01, Carl Banks <pavlovevide... at gmail.com> wrote:
> 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
> > 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
> > 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- Hide quoted text -
> - Show quoted text -
OK; I guess the answer to the question
"Assuming the following Python encodings, and ignoring questions
of performance, would Python and Lisp lists then be observationally
indistinguishable? i.e. would these then be fair encodings?"
is a 'yes'. Any disagreement?
More information about the Python-list