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

Groups > comp.lang.python > #7820 > unrolled thread

Python and Lisp : car and cdr

Back to article view | Back to comp.lang.python

Contents

  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

#7820 — Python and Lisp : car and cdr

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

[toc] | [next] | [standalone]

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

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

#7945

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]
def length(L):
    if not L: return 0
    return 1 + length(cdr(L))

L = (a, (b, (c, (d, None))))
length(L)

is O(n)

[toc] | [prev] | [next] | [standalone]

#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~

[toc] | [prev] | [next] | [standalone]

#7954

On Sun, 19 Jun 2011 05:56:27 -0700, Ethan Furman wrote:

> 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:]' ?

No. Each cell in a Lisp-style linked list has exactly two elements, and 
in Python are usually implemented as nested tuples:

(head, tail)  # Annoyingly, this is also known as (car, cdr).

where head is the data value and tail is either another Lisp-style list 
or a marker for empty (such as the empty tuple () or None). 

So a one-element linked list might be given as:

(42, None)

A two element list:  (42, (43, None))
Three element list:  (42, (43, (44, None)))

and so forth. So while you could harmlessly use a slice L[1:], there is 
no point, since L[1:] will have at most a single element.


>> def length(L):
>>     if not L: return 0
>>     return 1 + length(cdr(L))
> 
> How is this different from regular ol' 'len' ?

The point is to duplicate Lisp's implementation, not to be useful :)

Regular len will return 2, no matter how many elements you have in the 
linked list, because it doesn't look at the tail recursively.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#7979

On 6/19/2011 9:24 AM, Steven D'Aprano wrote:

> No. Each cell in a Lisp-style linked list has exactly two elements, and
> in Python are usually implemented as nested tuples:
>
> (head, tail)  # Annoyingly, this is also known as (car, cdr).
>
> where head is the data value and tail is either another Lisp-style list
> or a marker for empty (such as the empty tuple () or None).
>
> So a one-element linked list might be given as:
>
> (42, None)
>
> A two element list:  (42, (43, None))
> Three element list:  (42, (43, (44, None)))
>
> and so forth. So while you could harmlessly use a slice L[1:], there is
> no point, since L[1:] will have at most a single element.

It should be noted that the head element of any 'list' can also be a 
'list' (as with Python lists),

t = { { (1,None), (2,(3,None)) ), ( (4,(5,None)), (6,None) ) )

so that the structure is actually a tree, which is a much more general 
data structure than a true sequence of atoms. But TREP (for 
tree-processing) is not as catchy as LISP (for list processing).

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#7980

* 2011-06-19T12:20:32-04:00 * Terry Reedy wrote:

> On 6/19/2011 9:24 AM, Steven D'Aprano wrote:
>> No. Each cell in a Lisp-style linked list has exactly two elements,
>> and in Python are usually implemented as nested tuples:
>>
>> (head, tail)  # Annoyingly, this is also known as (car, cdr).
>>
>> where head is the data value and tail is either another Lisp-style
>> list or a marker for empty (such as the empty tuple () or None).

> It should be noted that the head element of any 'list' can also be a
> list' (as with Python lists),

Both the head and tail elements of a cons cell can refer to any Lisp
objects. Cons cell is a general-purpose primitive data type but it is
_often_ used to build lists and trees so the tail element often refers
to another cons cell (or nil that terminates the list).

Let's not forget that Lisp's program code itself is built on such trees
of cons cells. Lisp code itself is represented in this primitive Lisp
data type. That's why Lisp is so powerful in meta programming. It's
trivial to use Lisp functions to create Lisp code.

[toc] | [prev] | [next] | [standalone]

#7960

Ethan Furman <ethan@stoneleaf.us> writes:

>> 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:]' ?

Not for the linked list implementation he presented.

>> def length(L):
>>     if not L: return 0
>>     return 1 + length(cdr(L))
>
> How is this different from regular ol' 'len' ?

len would just return 2 for every linked list, and would raise an
exception for empty list (represented by None in Lie's implementation).

A more Pythonic implementation would represent the linked list as a
first-class objects with car and cdr being attributes, allowing for
fairly natural expression of __len__, __iter__, etc.  For example:

class List(object):
    __slots__ = 'car', 'cdr'

    def __init__(self, it=()):
        it = iter(it)
        try:
            self.car = it.next()
        except StopIteration:
            pass
        else:
            self.cdr = List(it)

    def __len__(self):
        if not hasattr(self, 'cdr'):
            return 0
        return 1 + len(self.cdr)

    def __iter__(self):
        head = self
        while hasattr(head, 'cdr'):
            yield head.car
            head = head.cdr

    def __repr__(self):
        return "%s(%r)" % (type(self).__name__, list(self))

>>> l = List([1, 2, 3])
>>> l
List([1, 2, 3])
>>> l.car
1
>>> l.cdr
List([2, 3])
>>> l.cdr.cdr.car
3
>>> l.cdr.cdr.cdr
List([])
>>> tuple(l)
(1, 2, 3)

[toc] | [prev] | [next] | [standalone]

#7953

On Sun, Jun 19, 2011 at 10:56 PM, Ethan Furman <ethan@stoneleaf.us> wrote:
> Lie Ryan wrote:
>> def cdr(L):
>>    return L[1]
>
> IANAL (I am not a Lisper), but shouldn't that be 'return L[1:]' ?

In LISP, a list is a series of two-item units (conses).

>> L = (a, (b, (c, (d, None))))

This represents the LISP equivalent of [a, b, c, d] in Python. A list
is a linked list, not an array (as in Python).

IANAL either though, someone else may wish to clarify the advantages
of this system.

ChrisA

[toc] | [prev] | [next] | [standalone]

#7955

On Sun, 19 Jun 2011 15:56:27 +0300, Ethan Furman <ethan@stoneleaf.us> wrote:

> Lie Ryan wrote:
>
>> def length(L):
>>     if not L: return 0
>>     return 1 + length(cdr(L))
>
> How is this different from regular ol' 'len' ?

It's better, because len() can't overflow the stack. ;)

[toc] | [prev] | [next] | [standalone]

#7968

Ethan Furman wrote:
> IANAL (I am not a Lisper), but shouldn't that be 'return L[1:]' ?


Ah, thanks all for the clarification.

~Ethan~

[toc] | [prev] | [next] | [standalone]

#7988

On Sun, 19 Jun 2011 23:23:10 +1000, Chris Angelico <rosuav@gmail.com>
declaimed the following in gmane.comp.python.general:

> 
> IANAL either though, someone else may wish to clarify the advantages
> of this system.
>
	My "Anatomy of LISP" book is in storage, but as I recall, it came
about just as an optimization for the original hardware... One long
register holding both CAR and CDR pointers (my mind also insists the TLA
are Content Address Register, Content Data Register, though the names
seem backwards since the CAR tended to refer to the current node's data,
and CDR referred to the next node)
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
        wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web