python list handling and Lisp list handling

[Carl Banks]

On Apr 25, 12:07 am, Mark Tarver <dr.mtar... at ukonline.co.uk> wrote:
> 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
>
> > >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- 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?

In Python

cdr([]) == []

And I'd think that'd be an exception in Lisp depending on variants and
such.  That's the only difference I can think of.


Carl Banks