كيف يمكنني إلحاق قائمة في المخطط؟

Question

تعد إضافة عنصر إلى رأس القائمة (القائمة الترابطية) أمرًا بسيطًا بما فيه الكفاية:

> (cons '(ding . 53) '((foo . 42) (bar . 27)))
((ding . 53) (foo . 42) (bar . 27))

يعد الإلحاق بذيل القائمة أمرًا أكثر صعوبة بعض الشيء.وبعد بعض التجارب، أنتجت هذا:

> (define (alist-append alist pair) `(,@alist ,pair))
> (alist-append '((foo . 42) (bar . 27)) '(ding . 53))
'((foo . 42) (bar . 27) (ding . 53))

ومع ذلك، يبدو لي أن هذا ليس هو الحل الاصطلاحي.فكيف يتم ذلك عادة في المخطط؟أم أن هذا هو الطريق في الواقع؟

Answer 1

أنت لا تلحق بقائمة.أنت سلبيات على قائمة.

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

Answer 2

تحدد Lisp الشائعة وظيفة تسمى أكونس لهذا الغرض بالضبط، حيث

(acons key value alist)

يعادل:

(cons (cons key value) alist)

يشير هذا بقوة إلى أن مجرد الاعتماد على القائمة هو أمر اصطلاحي.لاحظ أن هذا يعني شيئين:

1. نظرًا لأن عمليات البحث يتم إجراؤها عادةً من الأمام إلى الخلف، فإن الارتباطات المضافة حديثًا لها الأولوية على الارتباطات الأقدم.يمكن استخدام هذا للتنفيذ الساذج لكل من البيئات المعجمية والديناميكية.
2. على الرغم من أن استخدام القائمة هو O(1)، فإن الإلحاق بشكل عام هو O(n) حيث n هو طول القائمة، لذا فإن الاستخدام الاصطلاحي هو الأفضل للأداء بالإضافة إلى كونه مفضلًا من الناحية الأسلوبية.