مقدمه
شما روی پروژه‌ای کار می‌کنید که هدفش توسعه‌ی یک سامانه‌ی زمان‌بندی قطار برای شبکه‌ی راه‌آهنی پرتردد است.
از شما خواسته شده است که یک نمونه‌ی اولیه برای مسیرهای قطار در سامانه‌ی زمان‌بندی توسعه دهید.
هر مسیر از دنباله‌ای از ایستگاه‌های قطار تشکیل می‌شود که قطار موردنظر در آن‌ها توقف می‌کند.
دستورالعمل‌ها
تیم شما تصمیم گرفته است برای نمایش هر مسیر قطار در برنامه‌ی زمانی، از یک «لیست پیوندی دوطرفه» استفاده کند.
هر ایستگاه در مسیر قطار با یک گره در لیست پیوندی نمایش داده می‌شود.
لازم نیست نگران زمان رسیدن و حرکت در ایستگاه‌ها باشید.
هر ایستگاه به‌سادگی با یک عدد نمایش داده می‌شود.
می‌توان مسیرها را گسترش داد و به ابتدا یا انتهای یک مسیر ایستگاه افزود.
همچنین می‌توان با حذف ایستگاه‌ها از ابتدا یا انتهای یک مسیر، آن را کوتاه کرد.
گاهی یک ایستگاه تعطیل می‌شود و در آن صورت باید آن ایستگاه از مسیر حذف شود، حتی اگر در ابتدا یا انتهای مسیر نباشد.
اندازه‌ی یک مسیر نه با مسافتی که قطار می‌پیماید اندازه‌گیری می‌شود، بلکه با تعداد ایستگاه‌هایی که در آن‌ها توقف می‌کند.
لیست پیوندی یک ساختار داده‌ی بنیادی در علوم کامپیوتر است که اغلب در پیاده‌سازی ساختارهای داده‌ی دیگر به کار می‌رود.
همان‌طور که از اسمش پیداست، لیستی از گره‌هاست که به هم پیوند خورده‌اند.
لیستی از «گره‌ها» است که هر گره به همسایه یا همسایه‌هایش پیوند می‌خورد.
در یک لیست پیوندی یک‌طرفه هر گره فقط به گره بعدی خود پیوند می‌خورد.
در یک لیست پیوندی دوطرفه هر گره هم به گره قبلی و هم به گره بعدی خود پیوند می‌خورد.
اگر می‌خواهید درباره‌ی لیست‌های پیوندی بیشتر بدانید، نگاهی به این مقاله بیندازید که آن را با تصویرهای زیبا توضیح می‌دهد.
ساختارهای داده‌ی حالت‌دار
در زبان‌های تابعی، مانند Lean، بیشتر مقادیر طبق طراحی تغییرناپذیرند.
یعنی به‌روزرسانی‌ها معمولاً با ساختن یک مقدار جدید انجام می‌شوند.
مقدار قدیمی و مقدار جدید هر دو در کنار هم وجود دارند؛ می‌توان به آن‌ها ارجاع داد و از آن‌ها استفاده کرد.
با این حال، موقعیت‌های زیادی وجود دارد که در آن‌ها یک مقدار «حالت‌دار» مطلوب، یا حتی لازم است.
مقدار حالت‌دار با جهش به‌روزرسانی می‌شود: مقدار قدیمی جایگزین می‌شود، نه اینکه مقدار جدیدی ساخته شود.
پس از یک جهش، تنها مقدار به‌روزرسانی‌شده در دسترس باقی می‌ماند.
توجه داشته باشید که جهش‌ها می‌توانند برخی تضمین‌های زبان را نقض کنند.
یک تابع خالص باید همیشه برای مجموعه‌ی یکسانی از ورودی‌ها نتیجه‌ی یکسانی برگرداند، اما اگر یک ورودی در طول زمان تغییر کند، ممکن است تابع حتی وقتی با همان آرگومان‌ها فراخوانی می‌شود نتایج متفاوتی برگرداند.
به همین ترتیب، اگر یک تابع بتواند جدا از برگرداندن نتیجه تغییرات بیرونی ایجاد کند، یا بتواند از منابعی غیر از پارامترهایش بخواند، آن‌گاه دو فراخوانی از یک تابع ممکن است نتایج متفاوت و گاهی غیرقابل‌پیش‌بینی داشته باشند.
برای مدیریت چنین رفتار حالت‌داری، Lean هم مانند دیگر زبان‌های تابعی لازم می‌داند که توابع اثرگذار در نوع خاصی از ساختار بسته‌بندی شوند که آن‌ها را از توابع خالص متمایز می‌کند.
به این ساختارها «موناد» می‌گویند.
توجه به این نکته مهم است که هرچند هر مقدار حالت‌دار درون یک موناد اثرگذار قرار می‌گیرد، هر مونادی نماینده‌ی حالت جهش‌پذیر نیست.
نمونه‌های شاخص مونادهای «خالص» عبارت‌اند از Option، Except و Id.
در این تمرین، شما یک ساختار داده‌ی حالت‌دار به اسم LinkedList تعریف می‌کنید.
نمونه‌های این ساختار داده با جهش به‌روزرسانی می‌شوند.
برای پشتیبانی از این کار، همه‌ی توابع درون موناد ST بسته‌بندی می‌شوند.
در این موناد، حالت جهش‌پذیر تنها اثر جانبی است و ارجاع‌های جهش‌پذیر نمی‌توانند از آن خارج شوند.
برای اطلاعات بیشتر می‌توانید مرجع را ببینید.
منبع
موضوعی کلاسیک در علوم کامپیوتر
