Introdução
Você está trabalhando em um projeto para desenvolver um sistema de agendamento de trens para uma rede ferroviária movimentada.
Você ficou responsável por desenvolver um protótipo para as rotas de trem do sistema de agendamento.
Cada rota é uma sequência de estações de trem em que um determinado trem para.
Instruções
Sua equipe decidiu usar uma lista duplamente encadeada para representar cada rota de trem no cronograma.
Cada estação ao longo da rota do trem será representada por um nó na lista encadeada.
Você não precisa se preocupar com os horários de chegada e de partida nas estações.
Cada estação será representada simplesmente por um número.
As rotas podem ser estendidas, adicionando estações ao início ou ao fim de uma rota.
Também podem ser encurtadas, removendo estações do início ou do fim de uma rota.
Às vezes uma estação é fechada e, nesse caso, ela precisa ser removida da rota, mesmo que não esteja no início nem no fim dela.
O tamanho de uma rota não é medido pela distância que o trem percorre, mas por quantas estações ele para.
A lista encadeada é uma estrutura de dados fundamental na ciência da computação, frequentemente usada na implementação de outras estruturas de dados.
Como o nome sugere, é uma lista de nós que estão ligados entre si.
É uma lista de "nós", em que cada nó se liga ao seu vizinho ou aos seus vizinhos.
Em uma lista simplesmente encadeada, cada nó se liga apenas ao nó que vem depois dele.
Em uma lista duplamente encadeada, cada nó se liga tanto ao nó que vem antes quanto ao nó que vem depois.
Se você quiser se aprofundar em listas encadeadas, confira este artigo, que explica o assunto com desenhos bem explicativos.
Em linguagens funcionais, como Lean, a maioria dos valores é imutável por design.
Isso significa que atualizações geralmente são feitas produzindo um novo valor.
Tanto o valor antigo quanto o novo coexistem e podem ser referenciados e usados.
No entanto, há muitas situações em que um valor com estado é desejado, ou até mesmo necessário.
Um valor com estado é atualizado por mutação, substituindo o valor antigo em vez de criar um novo.
Após uma mutação, apenas o valor atualizado permanece acessível.
Observe que mutações podem quebrar algumas garantias da linguagem.
Uma função pura deve sempre retornar o mesmo resultado para o mesmo conjunto de entradas, mas se uma entrada pode mudar com o tempo, então a função pode retornar resultados diferentes mesmo quando chamada com os mesmos argumentos.
Da mesma forma, se uma função pode produzir mudanças externas além de retornar um resultado, ou pode ler de fontes que não sejam seus parâmetros, então duas chamadas à mesma função podem ter resultados diferentes e às vezes imprevisíveis.
Para lidar com esse comportamento com estado, Lean, como outras linguagens funcionais, exige que funções com efeitos sejam envolvidas em um tipo especial de estrutura que as distingue de funções puras.
Essas estruturas são chamadas de mônadas.
É importante notar que, embora todo valor com estado viva dentro de alguma mônada com efeitos, nem toda mônada representa estado mutável.
Exemplos notáveis de mônadas "puras" são Option, Except e Id.
Neste exercício, você vai definir uma estrutura de dados com estado chamada LinkedList.
Instâncias dessa estrutura de dados são atualizadas por mutação.
Para dar suporte a isso, todas as funções são envolvidas dentro da mônada ST.
Nesta mônada, o estado mutável é o único efeito colateral, e referências mutáveis não podem escapar.
Para mais informações, você pode consultar a referência.
Fonte
Tópico clássico da ciência da computação
