Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #7828

Re: Python and Lisp : car and cdr

Show all headers | View raw

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) :
>  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 ?

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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