Python and Lisp : car and cdr

[Ian Kelly]

On Fri, Jun 17, 2011 at 8:45 AM, Franck Ditter <franck at ditter.org> 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:])
>
> Should I think of the slice L[1:] as (cdr L) ? I mean, is the slice
> a copy of a segment of L, or do I actually get a pointer to something
> inside L ?

The slice is a copy of a segment of L.

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

O(n^2).  If you want to implement Lisp-style list processing in
Python, Python lists are not the most efficient data type to do it
with.  I would suggest using 2-element tuples to represent cons cells
and building up from there.

Also note that Python does not do tail recursion optimization, so
recursion in general is inefficient and prone to stack overflow if the
data structure is large enough.

> Where are such implementation things (well) said ?

http://docs.python.org/tutorial/introduction.html#lists