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

Answer 1

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

Answer 2

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

Answer 3

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
# []