2

在各种 Lisps 中，正确的列表是nil（空值）或cons单元格，其中第一个（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

相关问题，但没有回答我的问题：LISP cons in python

4

3 回答 3

2

我已经尝试稍微重写您的示例-这似乎对我有用而不会破坏堆栈。

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
于 2012-10-02T17:44:25.653 回答
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
于 2012-10-02T17:50:23.000 回答
0

如果您想无限地获取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
# []
于 2012-10-02T17:44:39.027 回答