Listas adecuadas y cola recursiva en Python

Question

En varios Lisps un lista adecuada es cualquiera nil (un valor nulo) o un contras celda, donde el primer valor (cabeza, primero, automóvil) apunta a un valor y el segundo (cola, resto, cdr) apunta a otra lista adecuada.Varios otros lenguajes de programación funcional implementan esta funcionalidad principal y final, incluidos Erlang y Scala.En Common Lisp y Emacs Lisp puedes encontrar de forma infinitamente recursiva la cola de una lista:

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

rendirá nil.Quiero emular ese comportamiento en Python.Claro, para mejorar el rendimiento será mejor que me quede con los tipos de datos nativos, que están muy optimizados, así que esto es sólo para hacer ejercicio.Mi código es:

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

sin embargo llamando tail ahora entra en una recursividad y da como resultado un error de profundidad de recursividad máxima.¿Cómo puedo hacer posibles expresiones como las siguientes?En otras palabras, ¿cómo puedo crear la funcionalidad de una lista adecuada en Python?

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

Pregunta relacionada, pero no responde a mi pregunta: Contras de LISP en Python

Answer 1

Intenté reescribir un poco tu ejemplo; esto parece funcionar para mí sin arruinar la pila.

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

En lugar de intentar crear tu clase y vincularla a una lista, tal vez deberías escribir tu propia lista enlazada (que es básicamente con lo que funcionan los lisps, cadenas de nodos que contienen un elemento y el siguiente nodo (que representa el resto de la lista). ).

Mi pitón está un poco oxidada, pero lo intentaré.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

Entonces deberías poder utilizar lo siguiente:

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

Si quieres poder obtener infinitamente el tail propiedad de una lista, necesitarás usar un property.De esta forma, la cola no se evalúa hasta que la solicitas, lo que evita la recursividad 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
# []