Listas adequadas e cauda recursiva em Python

Question

Em vários Lisps um lista adequada é também nil (um valor nulo) ou um contras célula, onde o primeiro valor (head, first, car) aponta para um valor e o segundo (tail, rest, cdr) aponta para outra lista adequada.Várias outras linguagens de programação funcional implementam essa funcionalidade inicial e final, incluindo Erlang e Scala.No Common Lisp e no Emacs Lisp você pode encontrar infinitamente recursivamente o final de uma lista:

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

Isso vai render nil.Quero emular esse comportamento em Python.Claro, para desempenho é melhor usar tipos de dados nativos, que são altamente otimizados, portanto, isso é apenas para exercícios.Meu código é:

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

No entanto, ligando tail agora insere uma recursão e resulta em erro de profundidade máxima de recursão.Como posso tornar possíveis expressões como abaixo?Em outras palavras, como posso criar a funcionalidade de uma lista adequada em Python?

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

Pergunta relacionada, mas não responde à minha pergunta: Contras do LISP em python

Answer 1

Tentei reescrever um pouco o seu exemplo - parece funcionar para mim sem estourar a pilha.

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

Em vez de tentar criar sua classe e vinculá-la a uma lista, talvez você deva escrever sua própria lista vinculada (que é basicamente com o que os lisps trabalham, cadeias de nós contendo um elemento e o próximo nó (que representa o resto da lista ).

Minha python está um pouco enferrujada, mas vou tentar.Considere este pseudocódigo:

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

Você deverá então ser capaz de usar o seguinte:

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

Se você quiser ser infinitamente capaz de obter o tail propriedade de uma lista, você precisará usar um property.Dessa forma, a cauda não é avaliada até que você a solicite, o que evita a recursão infinita.

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