2

さまざまなLispでは、適切なリストはnil（null値）またはconsセルのいずれかであり、最初の（head、first、car）値は値を指し、2番目の（tail、rest、cdr）は別の適切なリストを指します。ErlangやScalaなど、他のさまざまな関数型プログラミング言語がこのヘッドアンドテール機能を実装しています。CommonLispとEmacsLispでは、リストの末尾を無限に再帰的に見つけることができます。

(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

関連する質問ですが、私の質問には答えません：PythonのLISPの短所

4

3 に答える 3

2

クラスを作成してリストにバインドするのではなく、独自のリンクリスト（基本的にはLispが機能するものであり、要素を含むノードのチェーンと次のノード（リストの残りの部分を表す）を作成する必要があります）。

私の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
于 2012-10-02T17:50:23.000 に答える
2

私はあなたの例を少し書き直そうとしました - これはスタックを吹き飛ばすことなく私にとってはうまくいくようです.

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
于 2012-10-02T17:44:25.653 に答える
0

If you want to infinitely be able to get the tail property of a list, you'll need to use a property. This way, the tail is not evaluated until you ask for it, which prevents the infinite recursion.

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
# []
于 2012-10-02T17:44:39.027 に答える