«

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.'

(from http://www.chemie.fu-berlin.de/chemn...p/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.

Mark

Mark Tarver 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.'
>
> (from http://www.chemie.fu-berlin.de/chemn...p/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.
>
They are usually implemented as resizable arrays. In CPython great care
has been taken to make appending average to constant time; however,
inserting requires the later elements to be shifted up.

In the way they are normally used they are fast.

There are also queues and deques for when you want efficient queue or
deque behaviour.

Mark Tarver <> writes:
> 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

Python lists are vectors that automatically resize. You can append to
the end in amortized constant time in the obvious way (i.e. the
implementation allocates some extra space for expansion, and copies to
an even bigger area if you run out of expansion room). You can insert
and delete in the middle in linear time. This isn't as bad as it
sounds because the Python interpreter is pretty slow, but the list
insertion/deletion primitives are in C and are fast.

Mark Tarver <> writes:
> But are Python lists also indistinguishable from conventional
> Lisplists for list processing.

Forgot to add: you might look at http://norvig.com/python-lisp.html

Mark Tarver <> writes:

> But are Python lists also indistinguishable from conventional
> Lisplists for list processing.

They are very different. There is nothing like cons or nconc.
You can't convert two lists to a single longer list with nconc,
etc.

On 24 Apr, 17:19, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> Mark Tarver <dr.mtar...@ukonline.co.uk> writes:
> > But are Python lists also indistinguishable from conventional
> > Lisplists for list processing. *
>
> Forgot to add: you might look athttp://norvig.com/python-lisp.html
>
> Mark Tarver <dr.mtar...@ukonline.co.uk> writes:
> > But are Python lists also indistinguishable from conventional
> > Lisplists for list processing.
>
> They are very different. *There is nothing like cons or nconc.
> You can't convert two lists to a single longer list with nconc,
> etc.

Ah; so this

def cons (x,y):
return [x] + y

is not accurate?

Mark

Mark Tarver <> writes:
> Ah; so this
>
> def cons (x,y):
> return [x] + y
>
> is not accurate?

Depends what you mean by accurate!

in lisp, if you do:

(setq a '(1 2))
(setq b (cons 0 a))
(rplaca a 3)

Then
a is now (3 2)
b is now (0 3 2)

In Python, if you do:

a = [1, 2]
b = cons(0, a) # with your definition of cons
a[0] = 3

Then
a is now [3, 2]
b is now [0, 1, 2]

So in this respect, it is not accurate. But that's because Python lists
are vectors not conses.

--
Arnaud

On 24 Apr, 19:54, Arnaud Delobelle <arno...@googlemail.com> wrote:
> Mark Tarver <dr.mtar...@ukonline.co.uk> writes:
> > Ah; *so this
>
> > def cons (x,y):
> > * return [x] + y
>
> > is not accurate?
>
> Depends what you mean by accurate!
>
> in lisp, if you do:
>
> * * (setq a '(1 2))
> * * (setq b (cons 0 a))
> * * (rplaca a 3)
>
> Then
> * * a is now (3 2)
> * * b is now (0 3 2)
>
> In Python, if you do:
>
> * * a = [1, 2]
> * * b = cons(0, a) # with your definition of cons
> * * a[0] = 3
>
> Then
> * * a is now [3, 2]
> * * b is now [0, 1, 2]
>
> So in this respect, it is not accurate. *But that's because Python lists
> are vectors not conses.
>
> --
> Arnaud

Thanks for that.

OK; I think I get it. RPLACA and RPLACD are part of the id of Common
Lisp which I rarely contemplate. However what it seems to be is that
the difference is this. Lisp operates a destructive operation like
RPLACA in such a way that RPLACA on a global G not only changes G, but
all globals that reference G. Python on the other hand has a
destructive operation a[0] = .... which acts a bit like RPLACA but
whose change is local to the global changed. I take it that this is
because Python essentially copies the list, creating a brand new
vector rather than playing with pointers. Is that more or less it?

Which brings me to my next question. Assuming that we ban the use of
destructive operations like a[0] = ... Lisp's RPLACA and all the
rest. 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?

def car (x):
return x[0]

def cdr (x):
return x[1:]

def cons (x,y):
return [x] + y

Mark

On Apr 24, 8:19*am, Mark Tarver <dr.mtar...@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

On 25 Apr, 05:01, Carl Banks <pavlovevide...@gmail.com> wrote:
> On Apr 24, 8:19*am, Mark Tarver <dr.mtar...@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?

Mark

What is different is the concept of "all globals that
> reference G". *For example:
>
> >>> a = [1, 2, 3]
> >>> b = a
> >>> a[0] = 0
> >>> print b
>
> [0, 2, 3]

I see that Python had an id too .

Mark