Introducción
Estás trabajando en un proyecto para desarrollar un sistema de programación de trenes para una red ferroviaria muy transitada.
Te han pedido que desarrolles un prototipo para las rutas de trenes del sistema de programación.
Cada ruta consiste en una secuencia de estaciones de tren en las que se detiene un tren en particular.
Instrucciones
Tu equipo ha decidido usar una lista doblemente enlazada para representar cada ruta de tren en el horario.
Cada estación a lo largo de la ruta del tren se representará con un nodo en la lista enlazada.
No necesitas preocuparte por los horarios de llegada y salida en las estaciones.
Cada estación simplemente se representará con un número.
Las rutas se pueden extender agregando estaciones al principio o al final de una ruta.
También se pueden acortar quitando estaciones del principio o del final de una ruta.
A veces se cierra una estación y, en ese caso, hay que quitarla de la ruta, aunque no esté ni al principio ni al final de esta.
El tamaño de una ruta no se mide por la distancia que recorre el tren, sino por la cantidad de estaciones en las que se detiene.
La lista enlazada es una estructura de datos fundamental en las ciencias de la computación, y a menudo se usa para implementar otras estructuras de datos.
Como su nombre lo indica, es una lista de nodos que están enlazados entre sí.
Es una lista de «nodos», donde cada nodo se enlaza con su vecino o sus vecinos.
En una lista simplemente enlazada, cada nodo se enlaza solo con el nodo que lo sigue.
En una lista doblemente enlazada, cada nodo se enlaza tanto con el nodo que está antes como con el que está después.
Si quieres profundizar en las listas enlazadas, echa un vistazo a este artículo, que las explica con dibujos muy claros.
Estructuras de datos con estado
En los lenguajes funcionales, como Lean, la mayoría de los valores son inmutables por diseño.
Esto significa que las actualizaciones normalmente se hacen produciendo un valor nuevo.
Tanto el valor viejo como el nuevo coexisten y se pueden referenciar y usar.
Sin embargo, hay muchas situaciones en las que se desea un valor con estado, o incluso es necesario.
Un valor con estado se actualiza mediante mutación, reemplazando el valor viejo en lugar de crear uno nuevo.
Después de una mutación, solo el valor actualizado sigue siendo accesible.
Fíjate que las mutaciones pueden romper algunas garantías del lenguaje.
Una función pura siempre debe devolver el mismo resultado para el mismo conjunto de argumentos, pero si un argumento puede cambiar con el tiempo, entonces la función puede devolver resultados diferentes incluso cuando se llama con los mismos argumentos.
De manera similar, si una función puede producir cambios externos además de devolver un resultado, o puede leer de fuentes distintas de sus parámetros, entonces dos llamadas a la misma función pueden tener resultados diferentes y a veces impredecibles.
Para manejar este comportamiento con estado, Lean, como otros lenguajes funcionales, requiere que las funciones con efectos se envuelvan en un tipo especial de estructura que las distinga de las funciones puras.
Estas estructuras se llaman mónadas.
Es importante notar que, aunque todo valor con estado vive dentro de alguna mónada con efectos, no toda mónada representa estado mutable.
Ejemplos notables de mónadas «puras» son Option, Except e Id.
En este ejercicio, vas a definir una estructura de datos con estado llamada LinkedList.
Las instancias de esta estructura de datos se actualizan por mutación.
Para lograr esto, todas las funciones se envuelven dentro de la mónada ST.
En esta mónada, el estado mutable es el único efecto secundario, y las referencias mutables no pueden escapar.
Para más información, puedes consultar la referencia.
Fuente
Tema clásico de las ciencias de la computación
