Introduzione
Stai lavorando a un progetto per sviluppare un sistema di pianificazione dei treni per una rete ferroviaria molto trafficata.
Ti è stato chiesto di sviluppare un prototipo per le tratte dei treni del sistema di pianificazione.
Ogni tratta è composta da una sequenza di stazioni ferroviarie in cui un determinato treno fa fermata.
Istruzioni
Il tuo team ha deciso di usare una lista doppiamente concatenata per rappresentare ogni percorso ferroviario dell'orario.
Ogni stazione lungo il percorso del treno sarà rappresentata da un nodo della lista concatenata.
Non devi preoccuparti degli orari di arrivo e di partenza alle stazioni.
Ogni stazione sarà semplicemente rappresentata da un numero.
I percorsi possono essere estesi, aggiungendo stazioni all'inizio o alla fine di un percorso.
Si possono anche accorciare rimuovendo stazioni dall'inizio o dalla fine di un percorso.
A volte una stazione viene chiusa, e in quel caso va rimossa dal percorso, anche se non si trova all'inizio o alla fine.
La dimensione di un percorso non si misura in base a quanto lontano viaggia il treno, ma in base a quante stazioni tocca.
La lista concatenata è una struttura dati fondamentale dell'informatica, spesso usata per implementare altre strutture dati.
Come suggerisce il nome, è una lista di nodi collegati tra loro.
È una lista di «nodi», in cui ogni nodo è collegato al suo vicino o ai suoi vicini.
In una lista semplicemente concatenata ogni nodo è collegato solo al nodo che lo segue.
In una lista doppiamente concatenata ogni nodo è collegato sia al nodo che viene prima sia a quello che viene dopo.
Se vuoi approfondire le liste concatenate, dai un'occhiata a questo articolo, che le spiega con dei bei disegni.
Strutture dati con stato
Nei linguaggi funzionali, come Lean, la maggior parte dei valori è immutabile per scelta progettuale.
Questo significa che di solito gli aggiornamenti avvengono producendo un nuovo valore.
Il vecchio e il nuovo valore coesistono e possono essere referenziati e usati.
Esistono però molte situazioni in cui un valore con stato è desiderabile, o addirittura necessario.
Un valore con stato viene aggiornato tramite mutazione, sostituendo il vecchio valore invece di crearne uno nuovo.
Dopo una mutazione, solo il valore aggiornato resta accessibile.
Tieni presente che le mutazioni possono infrangere alcune garanzie del linguaggio.
Una funzione pura deve restituire sempre lo stesso risultato per lo stesso insieme di input, ma se un input può cambiare nel tempo, allora la funzione può restituire risultati diversi anche quando viene chiamata con gli stessi argomenti.
Allo stesso modo, se una funzione può produrre cambiamenti esterni diversi dalla restituzione di un risultato, o può leggere da fonti diverse dai suoi parametri, due chiamate alla stessa funzione possono avere esiti diversi e a volte imprevedibili.
Per gestire questo comportamento con stato, Lean, come altri linguaggi funzionali, richiede che le funzioni con effetti siano racchiuse in un tipo speciale di struttura che le distingue dalle funzioni pure.
Queste strutture si chiamano monadi.
È importante notare che, anche se ogni valore con stato vive dentro una qualche monade con effetti, non tutte le monadi rappresentano uno stato mutabile.
Esempi noti di monadi «pure» sono Option, Except e Id.
In questo esercizio definirai una struttura dati con stato chiamata LinkedList.
Le istanze di questa struttura dati vengono aggiornate tramite mutazione.
Per supportare tutto questo, tutte le funzioni sono racchiuse nella monade ST.
In questa monade, lo stato mutabile è l'unico effetto collaterale, e i riferimenti mutabili non possono fuoriuscirne.
Per maggiori informazioni, puoi consultare il riferimento.
Fonte
Argomento classico dell'informatica
