Python中的正确列表和递归尾部

Question

在各种Lisps a 适当的清单 是要么 nil （空值）或 缺点 单元格，其中第一个（head，first，car）值指向一个值，第二个（tail，rest，cdr）指向另一个正确的列表。各种其他函数式编程语言实现了这种头和尾功能，包括Erlang和Scala。在Common Lisp和Emacs Lisp中，您可以无限递归地找到列表的尾部:

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

它会屈服的 nil.我想在Python中模拟这种行为。当然，为了性能，我最好坚持使用本机数据类型，这些数据类型经过了大量优化，所以这只是为了锻炼。我的代码是:

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([])

然而调用 tail 现在输入递归并导致最大递归深度错误。我怎样才能使下面这样的表达成为可能？换句话说，如何在Python中创建适当列表的功能？

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

相关的问题，但没有回答我的问题: Python中的LISP缺点

Answer 1

我已经尝试重写你的例子了一下-这似乎对我有用，而不会吹堆栈。

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

而不是试图创建你的类并将其绑定到一个列表，也许你应该编写你自己的链表（这基本上是lisps的工作原理，包含一个元素的节点链和下一个节点（代表列表的其余部分）。

我的蟒蛇有点生锈了,但我要刺一下.考虑这个伪代码:

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

然后，您应该能够使用以下内容:

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

如果你想无限地得到 tail 列表的属性，你需要使用 property.这样，直到你要求它，这就防止了无限递归尾不进行评估。

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