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

Peter Sobot · Accepted Answer · 2012-10-02 17:44:25Z

2

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

answered Oct 2, 2012 at 17:44

Peter Sobot

2,55721 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Wug · Accepted Answer · 2012-10-02 17:50:23Z

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

answered Oct 2, 2012 at 17:50

Wug

13.3k5 gold badges36 silver badges57 bronze badges

1 Comment

Wug Over a year ago

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.

David Robinson · Accepted Answer · 2012-10-02 18:21:31Z

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 2, 2012 at 18:21

answered Oct 2, 2012 at 17:44

David Robinson

78.8k16 gold badges172 silver badges189 bronze badges

4 Comments

jfs Over a year ago

why do you need if/else in tail?

Wug Over a year ago

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.

David Robinson Over a year ago

@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 .tails, but that will be true no matter what your implementation is (since that is asking for each .tail to be its own list).

Wug Over a year ago

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.

Collectives™ on Stack Overflow

Proper lists and recursive tail in Python

3 Answers 3

Comments

1 Comment

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related