Правильные списки и рекурсивный хвост в Python

В различных Лиспах правильный список имеет либо 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 в python


python cdr cons
person Mirzhan Irkegulov    schedule 02.10.2012    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Я попытался немного переписать ваш пример - кажется, это работает для меня, не взорвав стек.

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
person Peter Sobot    schedule 02.10.2012

arrow_upward
2
arrow_downward

Вместо того, чтобы пытаться создать свой класс и привязать его к списку, возможно, вам следует написать свой собственный связанный список (с которым в основном работают 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
person Wug    schedule 02.10.2012
comment
Обратите внимание, что это не изменяет и не сохраняет список, переданный ему в качестве аргумента, он считывает элементы из него по мере создания узлов, а затем забывает его. - person Wug; 02.10.2012

arrow_upward
0
arrow_downward

Если вы хотите бесконечно иметь возможность получать свойство 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
# []
person David Robinson    schedule 02.10.2012
comment
зачем вам if/else в tail? - person jfs; 02.10.2012
comment
Разве в этом примере нет большого пространства для выполнения? Пример Аскера также работает, поскольку он дублирует весь список для каждого узла (обрезая его по одному элементу за раз. Для списка из x узлов общий размер списков, созданных путем построения MyList, будет x * x/ 2. - person Wug; 02.10.2012
comment
@Wug: Нет, у меня нет большого пространства выполнения для построения MyList (хотя у спрашивающего есть), поскольку tail вычисляется только тогда, когда вы его запрашиваете. Выполнение a.tail.tail.tail.tail... действительно имеет пространство выполнения, пропорциональное количеству .tail, но это будет верно независимо от вашей реализации (поскольку это требует, чтобы каждый .tail был отдельным списком). - person David Robinson; 02.10.2012
comment
Верно, но я считаю, что это все еще идет с N ^ 2; когда вы вызываете tail, вы создаете новый MyList, который дублирует весь сохраненный список (кроме первого элемента). list1.extend(list2) добавляет все элементы из списка2 в список1, но не изменяет список2. - person Wug; 02.10.2012