Bon les listes et les récursive queue en Python

Question

Dans divers Lisps un bonne liste est soit nil (une valeur nulle) ou un cons cellule, où le premier (tête, d'abord, voiture) de la valeur des points d'une valeur et le second (la queue, le reste, du rdc) points à une autre liste.Divers autres langages de programmation fonctionnelle mettre en œuvre cette tête et la queue de fonctionnalités, y compris Erlang et Scala.En Common Lisp et Emacs Lisp, vous pouvez infiniment de manière récursive trouver une queue d'une liste:

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

Il donnera nil.Je veux émuler ce comportement en Python.Bien sûr, pour les performances, je ferais mieux de coller avec native types de données, qui sont optimisés, donc c'est uniquement pour faire de l'exercice.Mon code est:

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

Cependant l'appel tail entre maintenant dans une récursivité et les résultats dans un maximum de profondeur de récursion d'erreur.Comment puis-je faire des expressions comme ci-dessous possible?En d'autres termes, comment puis-je créer une fonctionnalité d'une liste en Python?

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

Liés à la question, mais ne répond pas à ma question: LISP cons en python

Answer 1

J'ai essayé de réécrire votre exemple un peu - cela semble fonctionner pour moi sans faire exploser la pile.

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

Plutôt que d'essayer de créer votre classe et de le lier à une liste, peut-être que vous devriez écrire votre propre liste chaînée (qui est essentiellement ce que le lisps travailler avec, de chaînes de nœuds contenant un élément et le nœud suivant (qui représente le reste de la liste).

Mon python est un peu rouillé mais je vais faire un coup de couteau à elle.Considérer cette pseudo-code:

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

Vous devriez alors être en mesure d'utiliser les éléments suivants:

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 vous voulez infiniment d'être en mesure d'obtenir le tail propriété de une liste, vous aurez besoin d'utiliser un property.De cette façon, la queue n'est pas évalué jusqu'à ce que vous demandez, ce qui empêche la récursivité infinie.

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