Introduction
Tu travailles sur un projet de développement d'un système de planification des trains pour un réseau ferroviaire très fréquenté.
On t'a demandé de développer un prototype pour les itinéraires de train du système de planification.
Chaque itinéraire est constitué d'une suite de gares où s'arrête un train donné.
Instructions
Ton équipe a décidé d'utiliser une liste doublement chaînée pour représenter chaque ligne de train de l'horaire.
Chaque gare le long de la ligne de train sera représentée par un nœud dans la liste chaînée.
Pas besoin de te soucier des heures d'arrivée et de départ dans les gares.
Chaque gare sera simplement représentée par un nombre.
Les lignes peuvent être prolongées, en ajoutant des gares au début ou à la fin d'une ligne.
Elles peuvent aussi être raccourcies en supprimant des gares au début ou à la fin d'une ligne.
Il arrive qu'une gare ferme, et dans ce cas elle doit être retirée de la ligne, même si elle ne se trouve ni au début ni à la fin de celle-ci.
La taille d'une ligne ne se mesure pas à la distance parcourue par le train, mais au nombre de gares où il s'arrête.
La liste chaînée est une structure de données fondamentale en informatique, souvent utilisée pour implémenter d'autres structures de données.
Comme son nom l'indique, c'est une liste de nœuds reliés entre eux.
C'est une liste de « nœuds », où chaque nœud est relié à son ou ses voisins.
Dans une liste simplement chaînée, chaque nœud n'est relié qu'au nœud qui le suit.
Dans une liste doublement chaînée, chaque nœud est relié à la fois au nœud qui le précède et à celui qui le suit.
Si tu veux approfondir les listes chaînées, jette un œil à cet article qui les explique avec de jolis dessins.
Structures de données à état
Dans les langages fonctionnels, comme Lean, la plupart des valeurs sont immuables par conception.
Cela signifie que les mises à jour se font généralement en produisant une nouvelle valeur.
L'ancienne et la nouvelle valeur coexistent et peuvent toutes deux être référencées et utilisées.
Cependant, il existe de nombreuses situations où une valeur à état est souhaitable, voire nécessaire.
Une valeur à état est mise à jour par mutation, en remplaçant l'ancienne valeur au lieu d'en créer une nouvelle.
Après une mutation, seule la valeur mise à jour reste accessible.
Note que les mutations peuvent briser certaines garanties du langage.
Une fonction pure doit toujours renvoyer le même résultat pour le même ensemble d'entrées, mais si une entrée peut changer au fil du temps, la fonction peut renvoyer des résultats différents même lorsqu'on l'appelle avec les mêmes arguments.
De même, si une fonction peut produire des changements externes autres que le renvoi d'un résultat, ou peut lire depuis des sources autres que ses paramètres, alors deux appels à la même fonction peuvent avoir des résultats différents, et parfois imprévisibles.
Pour gérer ce comportement à état, Lean, comme les autres langages fonctionnels, exige que les fonctions à effets soient enveloppées dans un type particulier de structure qui les distingue des fonctions pures.
Ces structures sont appelées des monades.
Il est important de noter que, bien que toute valeur à état vive à l'intérieur d'une monade à effets, toute monade ne représente pas un état mutable.
Des exemples notables de monades « pures » sont Option, Except et Id.
Dans cet exercice, tu vas définir une structure de données à état appelée LinkedList.
Les instances de cette structure de données sont mises à jour par mutation.
Pour permettre cela, toutes les fonctions sont enveloppées dans la monade ST.
Dans cette monade, l'état mutable est le seul effet de bord, et les références mutables ne peuvent pas s'échapper.
Pour plus d'informations, tu peux consulter la référence.
Source
Un classique de l'informatique.
