Path: csiph.com!x330-a1.tempe.blueboxinc.net!feeder3.hal-mli.net!nx01.iad01.newshosting.com!newshosting.com!news2.euro.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
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; 'python,': 0.01; 'pointer': 0.05; 'subject:Python': 0.06; 'slice': 0.07; 'python': 0.08; 'recursion': 0.09; 'tail': 0.09; 'def': 0.12; 'am,': 0.14; 'wrote:': 0.14; 'lisp': 0.16; 'mean,': 0.16; 'overflow': 0.16; 'stack': 0.16; 'cc:addr:python-list': 0.17; 'suggest': 0.19; 'header:In-Reply-To:1': 0.21; 'cc:2**0': 0.22; 'cc:no real name:2**0': 0.23; 'sfxlen:0': 0.23; '\xa0if': 0.23; 'fri,': 0.23; 'received:209.85.161.46': 0.23; 'received:mail- fx0-f46.google.com': 0.23; 'structure': 0.23; 'there.': 0.25; 'function': 0.25; 'subject: : ': 0.26; 'received:209.85.161': 0.26; "i'm": 0.27; 'wondering': 0.28; 'message- id:@mail.gmail.com': 0.28; 'lists': 0.29; 'implement': 0.30; 'cc:addr:python.org': 0.30; 'tuples': 0.30; 'hi,': 0.31; 'does': 0.33; 'operations': 0.33; 'with.': 0.33; 'list': 0.33; 'actually': 0.33; 'things': 0.33; '17,': 0.35; 'using': 0.35; 'probably': 0.36; 'received:google.com': 0.37; 'something': 0.37; 'received:209.85': 0.37; 'url:docs': 0.37; 'think': 0.38; 'url:python': 0.38; 'processing': 0.38; 'url:org': 0.38; 'data': 0.38; 'subject:: ': 0.38; 'some': 0.38; 'should': 0.39; 'said': 0.39; 'received:209': 0.39; 'car': 0.63; 'prone': 0.84; 'inefficient': 0.91; 'complexity': 0.93
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type:content-transfer-encoding; bh=Jt1gyWrOrYDViTYHgdKwZiPKXbA2tfucQteTXdgVayY=; b=m7+JaCyQfyZsB2+LJk4gIYALRRDyjbNe9CCQOeOOFyH7yyXEof/XIipGW+U9omKLn0 sJH/YZLuAlJ7OiJ18VNboWbDY8kdTvUu3QpL1P3Gh/7rj77pb7ZGkezT2Pdt8Sl6k7+B 5K18dIg4T3BaapqPAObpTS/Z6XMm9M6JiWWZk=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; b=o7Xj1mXLmojP6JflMEEOTkhA1hzsU2Lj6Co0t1QPj7tMkxCkV0mlP3O81ny6LMdNU1 2R5D5QO3Ialatep6aXjia/NvXMFw89okARPSrSeDJ5CSDIBiNXZ3UOmCslkujL/ZU6vo a1RD6FlJ3ifefI9S7bDRT5LLsoWNkPKmWBfX8=
MIME-Version: 1.0
In-Reply-To: <franck-58760D.16453817062011@news.free.fr>
References: <franck-58760D.16453817062011@news.free.fr>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Fri, 17 Jun 2011 09:29:57 -0600
Subject: Re: Python and Lisp : car and cdr
To: Franck Ditter <franck@ditter.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
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 <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.76.1308324628.1164.python-list@python.org>
Lines: 28
NNTP-Posting-Host: 82.94.164.166
X-Trace: 1308324628 news.xs4all.nl 49178 [::ffff:82.94.164.166]:43006
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7828

On Fri, Jun 17, 2011 at 8:45 AM, Franck Ditter <franck@ditter.org> wrote:
> Hi, I'm just wondering about the complexity of some Python operations
> to mimic Lisp car and cdr in Python...
>
> def length(L) :
> =A0if not L : return 0
> =A0return 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 ?

The slice is a copy of a segment of L.

> Is the above function length O(n) or probably O(n^2) ?

O(n^2).  If you want to implement Lisp-style list processing in
Python, Python lists are not the most efficient data type to do it
with.  I would suggest using 2-element tuples to represent cons cells
and building up from there.

Also note that Python does not do tail recursion optimization, so
recursion in general is inefficient and prone to stack overflow if the
data structure is large enough.

> Where are such implementation things (well) said ?

http://docs.python.org/tutorial/introduction.html#lists