Introdução
Estás a trabalhar num projeto para desenvolver um sistema de horários para uma rede ferroviária movimentada.
Foi-te pedido que desenvolvesses um protótipo para as rotas dos comboios no sistema de horários. Cada rota é composta por uma sequência de estações onde um determinado comboio para.
Instruções
A tua equipa decidiu usar uma lista duplamente ligada para representar cada rota de comboio no horário.
Cada estação ao longo da rota do comboio será representada por um nó na lista ligada.
Não precisas de te preocupar com as horas de chegada e de partida nas estações.
Cada estação será simplesmente representada por um número.
As rotas podem ser estendidas, acrescentando 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.
Por vezes, uma estação é encerrada e, nesse caso, tem de ser removida da rota, mesmo que não esteja no início nem no fim da rota.
O tamanho de uma rota não se mede pela distância que o comboio percorre, mas pelo número de estações onde para.
A lista ligada é uma estrutura de dados fundamental da informática, usada frequentemente na implementação de outras estruturas de dados.
Como o nome sugere, é uma lista de nós ligados entre si.
É uma lista de "nós", em que cada nó se liga ao seu vizinho ou vizinhos.
Numa lista ligada simples, cada nó liga-se apenas ao nó que se lhe segue.
Numa lista duplamente ligada, cada nó liga-se tanto ao nó que vem antes como ao nó que vem depois.
Se quiseres aprofundar os teus conhecimentos sobre listas ligadas, espreita este artigo, que as explica com desenhos muito claros.
Em linguagens funcionais, como o Lean, a maioria dos valores é imutável por conceção.
Isto significa que as atualizações são normalmente feitas produzindo um novo valor.
O valor antigo e o novo coexistem, podendo ambos ser referenciados e usados.
No entanto, há muitas situações em que um valor com estado é desejado, ou até 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, só o valor atualizado permanece acessível.
Repara que as mutações podem quebrar algumas garantias da linguagem.
Uma função pura tem sempre de devolver o mesmo resultado para o mesmo conjunto de valores de entrada, mas, se um valor de entrada puder mudar ao longo do tempo, a função pode devolver resultados diferentes mesmo quando é chamada com os mesmos argumentos.
Da mesma forma, se uma função puder produzir alterações externas para além de devolver um resultado, ou puder ler de fontes que não sejam os seus parâmetros, duas chamadas à mesma função podem ter resultados diferentes e, por vezes, imprevisíveis.
Para lidar com este tipo de comportamento com estado, o Lean, tal como outras linguagens funcionais, exige que as funções com efeitos sejam envolvidas num tipo especial de estrutura que as distingue das funções puras.
Estas estruturas chamam-se mónadas.
É importante notar que, embora todos os valores com estado vivam dentro de alguma mónada com efeitos, nem todas as mónadas representam estado mutável.
Exemplos notáveis de mónadas "puras" são Option, Except e Id.
Neste exercício, vais definir uma estrutura de dados com estado chamada LinkedList.
As instâncias desta estrutura de dados são atualizadas por mutação.
Para isso, todas as funções ficam envolvidas na mónada ST.
Nesta mónada, o estado mutável é o único efeito secundário e as referências mutáveis não podem escapar.
Para mais informações, podes consultar a referência.
Fonte
Tópico clássico da informática
