Python의 적절한 목록 및 재귀 꼬리

Question

다양한 lisps a 올바른 목록 는 nil입니다 (a null value) 또는 첫 번째 (머리, 첫 번째, 자동차) 가치가 점점 셀 값과 두 번째 (Tail, REST, CDR)가 다른 적절한 목록을 가리 킵니다. 다양한 다른 기능 프로그래밍 언어는 Erlang 및 Scala를 포함 하여이 머리와 꼬리 기능을 구현합니다. 일반적인 Lisp 및 Emacs Lisp에서는 무한히 재귀 적으로 목록의 꼬리를 찾을 수 있습니다.

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

.

nil를 생성합니다. 나는 그 행동을 파이썬에서 에뮬레이트하고 싶습니다. 물론, 성능을 위해서는 네이티브 데이터 유형으로 더 잘 붙어 있습니다. 이것은 무겁게 최적화되어 있습니다. 그래서 이것은 운동을위한 것입니다. 내 코드는 다음과 같습니다.

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를 호출하면 재귀를 입력하고 최대 재귀 깊이 오류가 발생합니다. 가능한 것과 같은 표현을 어떻게 만들 수 있습니까? 즉, 파이썬에서 적절한 목록의 기능을 어떻게 만들 수 있습니까?

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

.

관련 질문,하지만 내 질문에 대답하지 않습니다 : 파이썬에서 Lisp 단점

Answer 1

예제를 조금 다시 작성하려고 시도했습니다. 이것은 스택을 불고없이 나를 위해 일하는 것 같습니다.

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

클래스를 만들고 목록에 바인딩하는 것이 아니라 자신의 링크 된 목록 (기본적으로 Lisps가 작동하는 것과 요소가 포함 된 노드의 체인과 다음 노드가 포함 된 노드가있는 것)을 작성해야합니다.목록의).

My Python은 조금 녹슬지 않지만 찌르기를 할 것입니다.이 의사를 고려하십시오 :

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

.

Answer 3

무한히 목록의 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
# []

.