القوائم المناسبة والذيل العودي في بيثون

Question

في اللثغات المختلفة أ القائمة المناسبة اما nil (قيمة فارغة) أو أ سلبيات الخلية، حيث تشير القيمة الأولى (الرأس، الأول، السيارة) إلى قيمة وتشير القيمة الثانية (الذيل، الراحة، مجلس الإنماء والإعمار) إلى قائمة مناسبة أخرى.تقوم العديد من لغات البرمجة الوظيفية الأخرى بتنفيذ وظيفة الرأس والذيل هذه، بما في ذلك Erlang وScala.في Common 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

بدلاً من محاولة إنشاء صفك وربطه بقائمة، ربما يجب عليك كتابة القائمة المرتبطة الخاصة بك (والتي هي في الأساس ما تعمل عليه اللفات، وسلاسل العقد التي تحتوي على عنصر والعقدة التالية (التي تمثل بقية القائمة ).

الثعبان الخاص بي صدئ بعض الشيء ولكني سأقوم بطعنه.خذ بعين الاعتبار هذا الكود الزائف:

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