Elenchi corretti e coda ricorsiva in Python

Question

in vari lisps A Elenco corretto è nil (a valore null) o un contro cella, dove il primo (testa, primo, auto) punti valore A un valore e il secondo (coda, riposo, cdr) punta a un altro elenco appropriato. Varie altre lingue di programmazione funzionali implementano questa funzionalità di testa e coda, tra cui Erlang e Scala. In comune Lisp e Emacs Lisp è possibile trovare infinitamente in modo ricorsivo una coda di una lista:

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

.

cederà nil. Voglio emulare quel comportamento in Python. Certo, per le prestazioni, farei meglio ad attaccare con i tipi di tipi nativi, che sono fortemente ottimizzati, quindi questo è solo per l'esercizio. Il mio codice è:

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

.

Comunale a chiamare tail ora entra in una ricorsione e risultati in massimo errore di profondità di ricorsione. Come posso rendere le espressioni come di seguito possibile? In altre parole, come posso creare funzionalità di un elenco appropriato in Python?

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

.

Domanda correlata, ma non risponde alla mia domanda: lisp contro in python

Answer 1

Ho provato a riscrivere il tuo esempio un po '- questo sembra funzionare per me senza soffiare lo stack.

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

Piuttosto che cercare di creare la tua classe e legarlo in un elenco, forse dovresti scrivere il tuo elenco collegato (che è fondamentalmente ciò che i lisps funzionano con, catene di nodi contenenti un elemento e il nodo successivo (che rappresenta il restodella lista).

Il mio Python è un po 'arrugginito ma farò una pugnalata.Considera questo pseudocodice:

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

.

Dovresti quindi essere in grado di utilizzare quanto segue:

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 si desidera infinitamente essere in grado di ottenere la proprietà tail di un elenco, è necessario utilizzare un property.In questo modo, la coda non viene valutata fino a quando non lo chiedi, il che impedisce l'infinita ricorsione.

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

.