Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!feeds.phibee-telecom.net!dedekind.zen.co.uk!zen.net.uk!hamilton.zen.co.uk!prichard.zen.co.uk.POSTED!not-for-mail From: Nobody Subject: Re: Python and Lisp : car and cdr Date: Sat, 18 Jun 2011 15:34:33 +0100 User-Agent: Pan/0.14.2 (This is not a psychotic episode. It's a cleansing moment of clarity.) Message-Id: Newsgroups: comp.lang.python References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Lines: 30 Organization: Zen Internet NNTP-Posting-Host: b662d4bb.news.zen.co.uk X-Trace: DXC=9S;L<;`J0iKYW7lQM;eP^A0g@SS;SF6nGR9OH0:RnENDHaSI0<_V23LMinDf@i<0AH\8b6n5ji;7L X-Complaints-To: abuse@zen.co.uk Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7910 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.