Solução alternativa para implementar operações em estruturas de dados duplamente vinculadas ou circulares em idiomas com dados imutáveis

Gostaria de aprender como criar gráficos e executar algumas operações locais sobre eles em Haskell, mas a questão não é específica para Haskell e, em vez de gráficos, podemos considerar listas duplamente vinculadas.

Pergunta: Qual seria uma maneira idiomática ou recomendada para implementar uma lista duplamente vinculada (ou outra estrutura de dados duplamente vinculada ou circular) e operações nela em uma linguagem que principalmente apóia e advoga estruturas de dados imutáveis ​​(Haskell, Clojure etc.) ? Em particular, como usar atualizações no local, formalmente proibidas pelo idioma?

Posso imaginar facilmente que, se alguma operação local for executada em uma lista duplamente vinculada (se um item for inserido, por exemplo), talvez não seja necessário copiar a lista inteira imediatamente devido à preguiça do idioma. No entanto, como a lista é duplamente vinculada, se for modificada em um só lugar, nenhum dos nós antigos poderá ser usado na nova versão da lista e eles precisarão ser marcados, copiados, coletados de maneira mais cedo ou mais tarde . Obviamente, essas são operações redundantes se apenas a cópia atualizada da lista for usada, mas adicionariam uma "sobrecarga" proporcional ao tamanho da lista.

Isso significa que, para essas tarefas, dados imutáveis ​​são simplesmente inapropriados, e linguagens declarativas funcionais sem suporte "nativo" para dados mutáveis ​​não são tão boas quanto as imperativas? Ou, há alguma solução alternativa complicada?

PS: Encontrei alguns artigos e apresentações sobre esse assunto na Internet, mas tive dificuldade em segui-los, enquanto acho que a resposta a essa pergunta não deve levar mais que um parágrafo e talvez um diagrama ... quero dizer, se houver nenhuma solução "funcional" para esse problema, a resposta provavelmente é "use C". Se houver, então, quão complicado pode ser?

Perguntas relacionadas

• "Estruturas de dados em programação funcional" . Minha pergunta específica sobre o uso de atualizações no local em vez de alternativas ineficientes não é discutida aqui.

• "Mutação interna de estruturas de dados persistentes" . A ênfase parece estar na implementação de baixo nível em uma linguagem não especificada, enquanto minha pergunta é sobre a escolha certa de uma linguagem (funcional ou não) e sobre possíveis soluções idiomáticas em linguagens funcionais.

Citações relevantes

Linguagens de programação puramente funcionais permitem que muitos algoritmos sejam expressos de forma muito concisa, mas existem alguns algoritmos nos quais o estado atualizável no local parece desempenhar um papel crucial. Para esses algoritmos, linguagens puramente funcionais, que não possuem estado atualizável, parecem ser inerentemente ineficientes ( [Ponder, McGeer e Ng, 1988] ).

- John Launchbury e Simon Peyton Jones, threads preguiçosos do estado funcional (1994), também John Launchbury e Simon Peyton Jones, Estado em Haskell (1995). Estes artigos introduzem o STconstrutor do tipo monádico em Haskell.

Pode haver outras estruturas de dados imutáveis ​​eficientes que se ajustam à sua tarefa específica, mas não são tão gerais quanto uma lista duplamente vinculada (que infelizmente é propensa a erros de modificação simultâneos devido à sua mutabilidade). Se você especificar seu problema de maneira mais restrita, provavelmente poderá encontrar uma estrutura desse tipo.

A resposta geral para a travessia (relativamente) econômica de estruturas imutáveis ​​são as lentes. A idéia é que você possa manter apenas informações suficientes para reconstruir uma estrutura imutável modificada de suas partes não modificadas e da peça atualmente modificada e navegar por ela para um nó vizinho.

Outra estrutura útil é um zíper . (A parte engraçada é que a assinatura de tipo para um zíper de lente é um derivado de matemática da escola de uma assinatura de tipo da estrutura.)

Aqui estão alguns links.

• Uma explicação simples dos zíperes

• Um capítulo sobre zíperes de "Learn you a Haskell"

• Introdução às lentes em Scala (slides)

• Lentes básicas
• Lentes em Programação Funcional

Haskell não impede o uso de estruturas de dados mutáveis. Eles são fortemente desencorajados e dificultados de usar devido ao fato de que as partes do código que os utilizam devem retornar uma ação de E / S (que deve eventualmente ser vinculada à ação de E / S que é retornada pela função principal), mas isso não ocorre. torne impossível usar essas estruturas se você realmente precisar delas.

Eu sugeriria investigar o uso da memória transacional do software como um caminho a seguir. Além de fornecer uma maneira eficiente de implementar estruturas mutáveis, também fornece garantias muito úteis para a segurança do encadeamento. Veja a descrição do módulo em https://hackage.haskell.org/package/stm e a visão geral do wiki em https://wiki.haskell.org/Software_transactional_memory .