Python and Lisp : car and cdr

[Nobody]

On Fri, 17 Jun 2011 16:45:38 +0200, Franck Ditter wrote:

> Hi, I'm just wondering about the complexity of some Python operations 
> to mimic Lisp car and cdr in Python...
> 
> def length(L) :
>   if not L : return 0
>   return 1 + length(L[1:])

Python's lists are arrays/vectors, not linked lists.

> Should I think of the slice L[1:] as (cdr L) ?

No.

> I mean, is the slice a copy of a segment of L,

Yes.

> or do I actually get a pointer to something inside L ?

No.

> Is the above function length O(n) or probably O(n^2) ? 

O(n^2).

And Python doesn't do tail-call optimisation, so you're likely to run out
of stack for a large list.