مقدمة
أنت تعمل على مشروع لتطوير نظام لجدولة القطارات في شبكة سكك حديدية مزدحمة.
طُلب منك تطوير نموذج أولي لمسارات القطارات في نظام الجدولة.
يتكوّن كل مسار من تسلسل من محطات القطار التي يتوقف عندها قطار معيّن.
التعليمات
قرّر فريقك استخدام قائمة مترابطة مزدوجة لتمثيل كل مسار قطار في الجدول الزمني.
كل محطة على طول مسار القطار ستُمثَّل بعقدة في القائمة المترابطة.
لا داعي للقلق بشأن أوقات الوصول والمغادرة في المحطات.
كل محطة ستُمثَّل ببساطة بعدد.
يمكن تمديد المسارات بإضافة محطات إلى بداية المسار أو نهايته.
ويمكن أيضًا تقصيرها بإزالة محطات من بداية المسار أو نهايته.
أحيانًا تُغلق إحدى المحطات، وفي هذه الحالة يجب إزالتها من المسار، حتى لو لم تكن في بداية المسار أو نهايته.
لا يُقاس حجم المسار بمدى سفر القطار، بل بعدد المحطات التي يتوقف عندها.
القائمة المترابطة بنية بيانات أساسية في علم الحاسوب، وكثيرًا ما تُستخدم في تنفيذ بنى بيانات أخرى.
وكما يوحي الاسم، فهي قائمة من العقد المترابطة معًا.
إنها قائمة من "العقد"، حيث ترتبط كل عقدة بجارتها أو بجيرانها.
في القائمة المترابطة الأحادية ترتبط كل عقدة بالعقدة التي تليها فقط.
وفي القائمة المترابطة المزدوجة ترتبط كل عقدة بالعقدة التي تسبقها، وكذلك بالعقدة التي تليها.
إذا أردت التعمق أكثر في القوائم المترابطة، فاطّلع على هذا المقال الذي يشرحها برسومات جميلة.
هياكل البيانات ذات الحالة
في اللغات الوظيفية، مثل Lean، معظم القيم غير قابلة للتغيير بحكم التصميم.
وهذا يعني أن التحديثات تُجرى عادةً بإنتاج قيمة جديدة.
فتتعايش القيمة القديمة والجديدة معًا، ويمكن الإشارة إلى كلٍّ منهما واستخدامه.
ومع ذلك، هناك مواقف كثيرة تكون فيها قيمة ذات حالة مطلوبة، أو حتى ضرورية.
تُحدَّث القيمة ذات الحالة عن طريق التعديل، أي استبدال القيمة القديمة بدلًا من إنشاء قيمة جديدة.
وبعد التعديل، لا تبقى متاحة سوى القيمة المُحدَّثة.
لاحظ أن التعديلات قد تُخلّ ببعض ضمانات اللغة.
فالدالة النقية يجب أن تُرجع دائمًا النتيجة نفسها لمجموعة المدخلات نفسها، لكن إذا كان أحد المدخلات قابلاً للتغير بمرور الوقت، فقد تُرجع الدالة نتائج مختلفة حتى عند استدعائها بالوسائط نفسها.
وبالمثل، إذا كان بإمكان دالة أن تُحدِث تغييرات خارجية غير إرجاع النتيجة، أو أن تقرأ من مصادر غير معاملاتها، فقد يكون لنداءين للدالة نفسها نتيجتان مختلفتان، وأحيانًا غير متوقعتين.
للتعامل مع هذا السلوك ذي الحالة، تتطلب Lean، مثل غيرها من اللغات الوظيفية، أن تُغلَّف الدوال ذات الأثر في نوع خاص من البنى يميّزها عن الدوال النقية.
وتسمى هذه البنى المونادات.
من المهم ملاحظة أنه، على الرغم من أن كل قيمة ذات حالة تعيش داخل مونادٍ ما ذي أثر، فليس كل موناد يمثّل حالة قابلة للتغيير.
ومن الأمثلة البارزة على المونادات «النقية» Option وExcept وId.
في هذا التمرين، ستقوم بتعريف هيكل بيانات ذي حالة يُسمى LinkedList.
وتُحدَّث نسخ هذا الهيكل عن طريق التعديل.
ولتوفير ذلك، تُغلَّف جميع الدوال داخل موناد ST.
وفي هذا الموناد، تكون الحالة القابلة للتغيير هي الأثر الجانبي الوحيد، ولا يمكن للمراجع القابلة للتغيير أن تتسرب إلى الخارج.
لمزيد من المعلومات، يمكنك الاطلاع على المرجع.
المصدر
موضوع كلاسيكي في علوم الحاسوب
