Вступ
Ми працюємо над проєктом з розробки системи розкладу потягів для завантаженої залізничної мережі.
Нас попросили розробити прототип маршрутів потягів для цієї системи розкладу. Кожен маршрут складається з послідовності станцій, на яких зупиняється відповідний потяг.
Вказівки
Наша команда вирішила використовувати двонаправлений звʼязаний список, щоб представити кожен маршрут потяга в розкладі.
Кожну станцію на маршруті потяга представлятиме вузол у звʼязаному списку.
Нам не потрібно перейматися часом прибуття та відправлення на станціях.
Кожну станцію просто представлятиме число.
Маршрути можна подовжувати, додаючи станції на початок або в кінець маршруту.
Їх також можна скорочувати, прибираючи станції з початку або з кінця маршруту.
Іноді станцію закривають, і тоді її потрібно прибрати з маршруту, навіть якщо вона не на початку і не в кінці маршруту.
Розмір маршруту вимірюють не тим, яку відстань долає потяг, а тим, на скількох станціях він зупиняється.
Звʼязаний список - фундаментальна структура даних у компʼютерних науках, яку часто використовують для реалізації інших структур даних.
Як випливає з назви, це список вузлів, зʼєднаних між собою.
Це список «вузлів», де кожен вузол посилається на свого сусіда або сусідів.
У однонаправленому звʼязаному списку кожен вузол посилається лише на вузол, що йде за ним.
У двонаправленому звʼязаному списку кожен вузол посилається і на вузол, що йде перед ним, і на вузол, що йде після нього.
Якщо хочеться глибше зануритися у звʼязані списки, погляньте на цю статтю, де все пояснено за допомогою гарних малюнків.
Структури даних зі станом
У функціональних мовах, як-от Lean, більшість значень є незмінними за задумом.
Це означає, що оновлення зазвичай відбуваються через створення нового значення.
Старе й нове значення співіснують, до них можна звертатися й використовувати їх.
Однак у багатьох ситуаціях значення зі станом є бажаним або навіть необхідним.
Значення зі станом оновлюється мутацією, яка замінює старе значення, а не створює нове.
Після мутації доступним залишається лише оновлене значення.
Зауважмо, що мутації можуть порушувати деякі гарантії мови.
Чиста функція завжди повинна повертати той самий результат для того самого набору вхідних даних, але якщо вхідні дані можуть змінюватися з часом, тоді функція може повертати різні результати, навіть коли її викликають з тими самими аргументами.
Так само, якщо функція може спричиняти зовнішні зміни, окрім повернення результату, або читати з джерел, відмінних від її параметрів, тоді два виклики тієї самої функції можуть мати різні, а часом і непередбачувані наслідки.
Щоб працювати з такою поведінкою зі станом, Lean, як і інші функціональні мови, вимагає, щоб функції з побічними ефектами були загорнуті в особливий різновид структури, яка відрізняє їх від чистих функцій.
Ці структури називаються монадами.
Важливо зауважити, що хоча кожне значення зі станом живе всередині якоїсь монади з побічними ефектами, не кожна монада представляє змінний стан.
До помітних прикладів «чистих» монад належать Option, Except й Id.
У цій вправі ми визначимо структуру даних зі станом під назвою LinkedList.
Примірники цієї структури даних оновлюються мутацією.
Щоб це працювало, усі функції загорнуті в монаду ST.
У цій монаді змінний стан є єдиним побічним ефектом, а змінні посилання не можуть вийти за її межі.
Докладніше можна переглянути в довідці.
Джерело
Класична тема з інформатики
