Python and Lisp : car and cdr

[Lie Ryan]

On 06/18/11 00:45, 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:])
> 
> 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 ? Is the above function length O(n) or probably O(n^2) ? 
> Where are such implementation things (well) said ?
> 
> Thanks,
> 
>      franck

Your function does not mimic Lisp's car/cdr. This one does:


def car(L):
    return L[0]
def cdr(L):
    return L[1]
def length(L):
    if not L: return 0
    return 1 + length(cdr(L))

L = (a, (b, (c, (d, None))))
length(L)

is O(n)