Bevezetés
Egy forgalmas vasúti hálózat menetrendtervező rendszerének fejlesztésén dolgozol.
Arra kértek, hogy prototípust készíts a menetrendtervező rendszer vonatútvonalaihoz.
Minden útvonal azoknak a vasútállomásoknak a sorából áll, ahol az adott vonat megáll.
Utasítások
A csapatod úgy döntött, hogy a menetrendben szereplő minden vonatútvonalat kétszeresen láncolt listával ábrázol.
A vonat útvonalán minden állomást egy-egy csomópont képvisel a láncolt listában.
Nem kell az állomások érkezési és indulási idejével foglalkoznod.
Minden állomást egyszerűen egy szám ábrázol.
Az útvonalak bővíthetők: új állomásokat adhatsz az útvonal elejére vagy végére.
Rövidíthetők is, ha eltávolítod az állomásokat az útvonal elejéről vagy végéről.
Néha bezárnak egy állomást, és ilyenkor el kell távolítani az útvonalról, akkor is, ha nem az útvonal elején vagy végén van.
Az útvonal hosszát nem az méri, hogy milyen messzire utazik a vonat, hanem az, hogy hány állomáson áll meg.
A láncolt lista alapvető adatszerkezet a számítástechnikában, és gyakran más adatszerkezetek megvalósításához használják.
Ahogy a neve is sugallja, olyan csomópontok listája, amelyek össze vannak kapcsolva egymással.
Olyan „csomópontok” listája, ahol minden csomópont a szomszédjához vagy a szomszédaihoz kapcsolódik.
Egy egyszeresen láncolt listában minden csomópont csak az őt követő csomópontra mutat.
Egy kétszeresen láncolt listában minden csomópont kapcsolódik az előtte lévő és az utána következő csomóponthoz is.
Ha mélyebbre szeretnél ásni a láncolt listák világában, nézd meg ezt a cikket, amely szép ábrák segítségével magyarázza el őket.
Állapottal rendelkező adatszerkezetek
A funkcionális nyelvekben, például a Leanben, a legtöbb érték eleve megváltoztathatatlan.
Ez azt jelenti, hogy a frissítés általában egy új érték létrehozásával történik.
A régi és az új érték is együtt létezik, mindkettőre lehet hivatkozni, és mindkettő használható.
Vannak azonban olyan helyzetek, amikor állapottal rendelkező értékre vágyunk, vagy éppenséggel szükség van rá.
Az állapottal rendelkező értéket mutációval frissítjük: a régi értéket kicseréljük ahelyett, hogy újat hoznánk létre.
Egy mutáció után már csak a frissített érték érhető el.
Ne feledd, hogy a mutációk a nyelv néhány garanciáját is megtörhetik.
Egy tiszta függvénynek ugyanarra a bemenetre mindig ugyanazt az eredményt kell visszaadnia, de ha egy bemenet idővel megváltozhat, akkor a függvény ugyanazokkal az argumentumokkal hívva is más eredményt adhat.
Hasonlóképpen, ha egy függvény az eredmény visszaadásán kívül külső változásokat is előidézhet, vagy a paraméterein kívül más forrásokból is olvashat, akkor ugyanannak a függvénynek két meghívása is eltérő, sőt néha kiszámíthatatlan eredménnyel járhat.
Az ilyen állapottal járó viselkedés kezeléséhez a Leannek, akárcsak a többi funkcionális nyelvnek, megköveteli, hogy a mellékhatással járó függvényeket egy speciális szerkezetbe csomagoljuk, amely megkülönbözteti őket a tiszta függvényektől.
Ezeket a szerkezeteket monádoknak nevezzük.
Fontos megjegyezni, hogy bár minden állapottal rendelkező érték valamilyen mellékhatással járó monádon belül él, nem minden monád képvisel módosítható állapotot.
A „tiszta” monádok nevezetes példái az Option, az Except és az Id.
Ebben a feladatban egy LinkedList nevű, állapottal rendelkező adatszerkezetet fogsz definiálni.
Az adatszerkezet példányait mutációval frissítjük.
Ennek támogatásához minden függvényt az ST monádba csomagolunk.
Ebben a monádban a módosítható állapot az egyetlen mellékhatás, és a módosítható hivatkozások nem szökhetnek ki.
További információért nézd meg a referenciát.
Forrás
Klasszikus számítástudományi téma
