Proper lists and recursive tail in Python

Question

In various Lisps a proper list is either nil (a null value) or a cons cell, where the first (head, first, car) value points to a value and the second (tail, rest, cdr) points to another proper list. Various other functional programming languages implement this head and tail functionality, including Erlang and Scala. In Common Lisp and Emacs Lisp you can infinitely recursively find a tail of a list:

(rest (rest (rest (rest (rest (rest ()))))))

It will yield nil. I want to emulate that behavior in Python. Sure, for performance i'd better stick with native datatypes, which are heavily optimized, so this is only for exercise. My code is:

class MyList:
    def __init__(self, *xs):
        self._x = []
        self._x.extend(xs)
        self.is_empty = not xs
        self.head = xs[0] if xs else None
        self.tail = MyList(*xs[1:]) if xs[1:] else MyList([])

However calling tail now enters a recursion and results in maximum recursion depth error. How can i make expressions like below possible? In other words, how can i create functionality of a proper list in Python?

a = MyList(1,2)
my_list.tail.tail.tail.tail.tail.tail

Related question, but does not answer my question: LISP cons in python

score 2 · Accepted Answer · answered Oct 02 '12 at 17:44

I've tried rewriting your example a bit - this seems to work for me without blowing the stack.

class MyList(object):
    def __init__(self, *xs):
        self._x = xs if all(xs) else tuple()
        self.head = xs[0] if xs else None

    @property
    def is_empty(self):
        return not self._x

    @property
    def tail(self):
        return MyList(self._x[1:]) if self._x[1:] else MyList([])

s = MyList(1, 2)
print s.tail.tail.tail.tail.tail.tail

score 2 · Answer 2 · answered Oct 02 '12 at 17:50

Rather than trying to create your class and bind it to a list, maybe you should write your own linked list (which is basically what the lisps work with, chains of nodes containing an element and the next node (which represents the rest of the list).

My python is a bit rusty but I'll make a stab at it. Consider this pseudocode:

class WugList:
    def __init__(self, *xs):
        self.head = xs[0] if (len(xs) > 0) else None
        self.tail = WugList(xs[1:]) if (len(xs) > 0) else self
        self.is_empty = (len(xs) > 0)

    def car(self):
        return self.head

    def cdr(self):
        return self.tail

You should then be able to use the following:

derp = WugList([1,2,3,42,69,9001])
a = derp.car()                   # 1
b = derp.cdr().car()             # 2
c = derp.cdr().cdr().cdr().car() # 42

# chaining cdr infinitely is possible because the last node's head is None
# and its tail is itself
d = derp.cdr().cdr().cdr().cdr().cdr().cdr().cdr().cdr().cdr().cdr()
              .cdr().cdr().cdr().cdr().cdr().cdr().cdr().cdr().cdr()
              .cdr().cdr().cdr().cdr().cdr().cdr().cdr().cdr().car() # None

Note that this doesn't modify or save the list passed to it as an argument, it reads the elements out of it as it's creating nodes and then forgets it. — Wug, Oct 02 '12 at 17:53

David Robinson · Answer 3 · 2012-10-02T18:21:31.793

0

If you want to infinitely be able to get the tail property of a list, you'll need to use a property. This way, the tail is not evaluated until you ask for it, which prevents the infinite recursion.

class MyList:
    def __init__(self, *xs):
        self._x = []
        self._x.extend(xs)
        self.is_empty = not xs
        self.head = xs[0] if xs else None

    @property
    def tail(self):
        return MyList(*self._x[1:])

a = MyList(1,2)
print a._x
# [1, 2]
print a.tail._x
# [2]
print a.tail.tail._x
# []
print a.tail.tail.tail._x
# []
print a.tail.tail.tail.tail._x
# []

edited Oct 02 '12 at 18:21

answered Oct 02 '12 at 17:44

David Robinson

77,383
16
167
187

why do you need if/else in `tail`? – jfs Oct 02 '12 at 17:49
Doesn't this example have large runspace? Asker's example does as well, since it duplicates the entire list for every node (trimming one element at a time off of it. For a list of x nodes, the total size of the lists created by constructing a MyList would be x*x/2. – Wug Oct 02 '12 at 17:55
@Wug: No, mine does not have a large runspace for constructing a `MyList` (though the asker's does), since the `tail` is computed only when you ask for it. Doing `a.tail.tail.tail.tail...` does have a runspace proportional to the number of `.tail`s, but that will be true no matter what your implementation is (since that is asking for each `.tail` to be its own list). – David Robinson Oct 02 '12 at 18:12
1

True, but I believe it still goes with N^2; when you call tail, you make a new MyList, which duplicates the entire stored list (except for the first element). `list1.extend(list2)` adds all of the elements in list2 to list1 but does not modify list2. – Wug Oct 02 '12 at 18:48

Proper lists and recursive tail in Python

3 Answers3