Date: Sun, 19 Jun 2011 16:00:20 +1000
From: Lie Ryan <lie.1296@gmail.com>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110513 Lightning/1.0b3pre Thunderbird/3.1.10 ThunderBrowse/3.3.5
MIME-Version: 1.0
Newsgroups: comp.lang.python
Subject: Re: Python and Lisp : car and cdr
References: <franck-58760D.16453817062011@news.free.fr>
In-Reply-To: <franck-58760D.16453817062011@news.free.fr>
X-Enigmail-Version: 1.1.2
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
NNTP-Posting-Host: 110.175.240.90
X-Original-NNTP-Posting-Host: 110.175.240.90
Message-ID: <4dfd90de$1@dnews.tpgi.com.au>
X-Trace: dnews.tpgi.com.au!tpg.com.au 1308463326 110.175.240.90 (19 Jun 2011 16:02:06 +1000)
Lines: 32
Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.alt.net!news.kjsl.com!rahul.net!wasp.rahul.net!rahul.net!nntp1.phx1.gblx.net!nntp.gblx.net!nntp.gblx.net!nntp3.phx1!dnews.tpgi.com.au!tpg.com.au!not-for-mail
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7945

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)