Python and Lisp : car and cdr

Discussion in 'Python' started by Franck Ditter, Jun 17, 2011.

  1. 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
     
    Franck Ditter, Jun 17, 2011
    #1
    1. Advertisements

  2. Franck Ditter

    Ian Kelly Guest

    The slice is a copy of a segment of L.
    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.
    http://docs.python.org/tutorial/introduction.html#lists
     
    Ian Kelly, Jun 17, 2011
    #2
    1. Advertisements

  3. Franck Ditter

    Nobody Guest

    Python's lists are arrays/vectors, not linked lists.
    O(n^2).

    And Python doesn't do tail-call optimisation, so you're likely to run out
    of stack for a large list.
     
    Nobody, Jun 18, 2011
    #3
  4. Franck Ditter

    Lie Ryan Guest

    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)
     
    Lie Ryan, Jun 19, 2011
    #4
  5. Franck Ditter

    Ethan Furman Guest

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

    How is this different from regular ol' 'len' ?

    ~Ethan~
     
    Ethan Furman, Jun 19, 2011
    #5
  6. In LISP, a list is a series of two-item units (conses).

    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
     
    Chris Angelico, Jun 19, 2011
    #6
  7. It's better, because len() can't overflow the stack. ;)
     
    Elias Fotinis, Jun 19, 2011
    #7
  8. 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.

    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 D'Aprano, Jun 19, 2011
    #8
  9. Not for the linked list implementation he presented.
    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))
    (1, 2, 3)
     
    Hrvoje Niksic, Jun 19, 2011
    #9
  10. Franck Ditter

    Ethan Furman Guest


    Ah, thanks all for the clarification.

    ~Ethan~
     
    Ethan Furman, Jun 19, 2011
    #10
  11. Franck Ditter

    Terry Reedy Guest

    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 Reedy, Jun 19, 2011
    #11
  12. 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.
     
    Teemu Likonen, Jun 19, 2011
    #12
  13. 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)
     
    Dennis Lee Bieber, Jun 19, 2011
    #13
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.