Re: Python and Lisp : car and cdr

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 <nobody@nowhere.com>
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	<pan.2011.06.18.14.33.44.219000@nowhere.com>
Newsgroups	comp.lang.python
References	<franck-58760D.16453817062011@news.free.fr>
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

Show key headers only | View raw

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.

Thread

Python and Lisp : car and cdr Franck Ditter <franck@ditter.org> - 2011-06-17 16:45 +0200
  Re: Python and Lisp : car and cdr Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-17 09:29 -0600
  Re: Python and Lisp : car and cdr Nobody <nobody@nowhere.com> - 2011-06-18 15:34 +0100
  Re: Python and Lisp : car and cdr Lie Ryan <lie.1296@gmail.com> - 2011-06-19 16:00 +1000
    Re: Python and Lisp : car and cdr Ethan Furman <ethan@stoneleaf.us> - 2011-06-19 05:56 -0700
      Re: Python and Lisp : car and cdr Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-06-19 13:24 +0000
        Re: Python and Lisp : car and cdr Terry Reedy <tjreedy@udel.edu> - 2011-06-19 12:20 -0400
          Re: Python and Lisp : car and cdr Teemu Likonen <tlikonen@iki.fi> - 2011-06-19 19:38 +0300
      Re: Python and Lisp : car and cdr Hrvoje Niksic <hniksic@xemacs.org> - 2011-06-19 16:26 +0200
    Re: Python and Lisp : car and cdr Chris Angelico <rosuav@gmail.com> - 2011-06-19 23:23 +1000
    Re: Python and Lisp : car and cdr "Elias Fotinis" <efotinis@yahoo.com> - 2011-06-19 16:24 +0300
    Re: Python and Lisp : car and cdr Ethan Furman <ethan@stoneleaf.us> - 2011-06-19 08:07 -0700
    Re: Python and Lisp : car and cdr Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2011-06-19 11:36 -0700

csiph-web