Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!xlned.com!feeder5.xlned.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.001 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'pointer': 0.05; 'subject:Python': 0.06; "shouldn't": 0.07; 'slice': 0.07; 'python': 0.08; 'from:addr:ethan': 0.09; 'from:addr:stoneleaf.us': 0.09; 'from:name:ethan furman': 0.09; 'message-id:@stoneleaf.us': 0.09; 'received:gator410.hostgator.com': 0.09; '~ethan~': 0.09; 'def': 0.12; 'wrote:': 0.14; 'lisp': 0.16; 'mean,': 0.16; 'cc:addr :python-list': 0.17; 'ryan': 0.19; 'thanks,': 0.19; 'header:In- Reply-To:1': 0.21; 'cc:2**0': 0.22; 'cc:no real name:2**0': 0.23; 'function': 0.25; 'subject: : ': 0.26; "i'm": 0.27; 'wondering': 0.28; 'cc:addr:python.org': 0.30; 'hi,': 0.31; 'does': 0.33; 'operations': 0.33; 'actually': 0.33; 'things': 0.33; 'regular': 0.34; 'header:User-Agent:1': 0.35; 'lie': 0.35; 'probably': 0.36; 'something': 0.37; 'think': 0.38; 'but': 0.38; 'subject:: ': 0.38; 'some': 0.38; 'should': 0.39; 'said': 0.39; 'your': 0.60; 'car': 0.63; 'received:websitewelcome.com': 0.67; 'received:gateway04.websitewelcome.com': 0.91; 'complexity': 0.93 Date: Sun, 19 Jun 2011 05:56:27 -0700 From: Ethan Furman User-Agent: Thunderbird 2.0.0.24 (Windows/20100228) MIME-Version: 1.0 To: Lie Ryan Subject: Re: Python and Lisp : car and cdr References: <4dfd90de$1@dnews.tpgi.com.au> In-Reply-To: <4dfd90de$1@dnews.tpgi.com.au> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - gator410.hostgator.com X-AntiAbuse: Original Domain - python.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - stoneleaf.us X-BWhitelist: no X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: c-67-170-168-84.hsd1.or.comcast.net ([192.168.74.5]) [67.170.168.84]:1575 X-Source-Auth: ethan+stoneleaf.us X-Email-Count: 1 X-Source-Cap: dG9idWs7dG9idWs7Z2F0b3I0MTAuaG9zdGdhdG9yLmNvbQ== Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 36 NNTP-Posting-Host: 82.94.164.166 X-Trace: 1308488252 news.xs4all.nl 49174 [::ffff:82.94.164.166]:36771 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7951 Lie Ryan wrote: > 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] IANAL (I am not a Lisper), but shouldn't that be 'return L[1:]' ? > def length(L): > if not L: return 0 > return 1 + length(cdr(L)) How is this different from regular ol' 'len' ? ~Ethan~