Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!newsfeed.CARNet.hr!gregory.BNet.hr!busola.homelinux.net!not-for-mail
From: Hrvoje Niksic <hniksic@xemacs.org>
Newsgroups: comp.lang.python
Subject: Re: Python and Lisp : car and cdr
Date: Sun, 19 Jun 2011 16:26:56 +0200
Organization: B.net Hrvatska d.o.o.
Lines: 63
Message-ID: <87aaddrj67.fsf@xemacs.org>
References: <franck-58760D.16453817062011@news.free.fr> <4dfd90de$1@dnews.tpgi.com.au> <mailman.144.1308488252.1164.python-list@python.org>
NNTP-Posting-Host: cpe-94-253-188-152.zg.cable.xnet.hr
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: gregory.bnet.hr 1308493801 22012 94.253.188.152 (19 Jun 2011 14:30:01 GMT)
X-Complaints-To: abuse@globalnet.hr
NNTP-Posting-Date: Sun, 19 Jun 2011 14:30:01 +0000 (UTC)
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1.50 (gnu/linux)
Cancel-Lock: sha1:eid7PgD8TuIZiAGT8Gb3ji3vDwg=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python: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)