Por que a programação funcional não pesquisou árvores dinâmicas?

19

As árvores dinâmicas desempenham um papel importante na resolução de problemas como fluxos de rede, gráficos dinâmicos, problemas combinatórios ("Árvores dinâmicas na prática" de Tarjan e Werneck) e a fusão recente de dicionários ("Um dicionário mesclável simples" de Adam Karczmarz),

Por árvores dinâmicas, refiro-me à definição declarada no artigo de Sleator & Tarjan "Uma estrutura de dados para árvores dinâmicas" em 1983. Poucos esforços foram publicados na área de pesquisa em programação funcional desde então.

  1. Edward Kmett implementou uma versão das árvores ST principalmente como uma tradução da contrapartida em C ++, consulte Link-cut trees .
  2. Chris Okasaki escreveu uma implementação limitada das árvores Splay em seu renomado livro "Estruturas de dados puramente funcionais".
  3. Ralf Hinze e Ross Paterson introduziram uma estrutura de dados funcional chamada 2-3 árvores de dedos, mas com um objetivo um pouco diferente daquele da definição original de árvores dinâmicas.

A implementação (e talvez o desempenho) de árvores dinâmicas são divididas de acordo com três abordagens:

  1. Linearização, onde as árvores ET (tour de Euler) desempenham um grande papel. Não foi encontrado um estudo puramente funcional.
  2. A decomposição de caminho, onde as árvores ST são o carro-chefe, acabou de encontrar a versão de Kmett.
  3. Contração de árvore, onde as árvores de topo, árvores de topologia e árvores de RC são os jogadores. Não foi encontrado um estudo puramente funcional.

A análise e implementação puramente funcionais podem ser encontradas em Splay, AVL, árvore vermelho-preta, mas essas NÃO são árvores dinâmicas. Os primeiros são considerados a estrutura de dados de sombra (também chamada virtual ou auxiliar) do último.

Então, minha pergunta é:

Quais são as razões (desvantagens, fraquezas) para a comunidade de pesquisa em Programação Funcional não participar da estrutura de dados das árvores dinâmicas?

data-structures trees functional-programming Richard Chambers
fonte
14
Não entendo como isso pode ser respondido sem a formação de um comitê autoritário da comunidade de programação funcional para formar opiniões oficiais. Não podemos reformular a pergunta para que haja algo que possa ser respondido aqui? Até onde eu sei, o OP deve simplesmente implementar suas árvores dinâmicas em Haskell ou o que quer que seja, e depois voltar aqui para relatar que foi feito, afinal.
Andrej Bauer
Atualização para @AndrejBauer: o OP foi e implementou suas árvores dinâmicas em Haskell: arxiv.org/abs/1908.11105
jbapple

Respostas:

-1

"Na ciência da computação, a programação funcional é um paradigma de programação. Um estilo de construção da estrutura e dos elementos de programas de computador que tratam a computação como a avaliação de funções matemáticas e evitam a alteração de dados mutáveis ​​e de estado". - Wikipedia

"mudança de estado e dados mutáveis" em outras palavras "dinâmico".

Portanto, sua pergunta é como perguntar por que a esquerda não está certa.

Anthony Bachler
fonte
1
Os programas funcionais podem representar dados dinâmicos com estruturas de dados persistentes. Esta pergunta está perguntando por que o desenvolvimento de estruturas de dados persistentes para um determinado problema não foi pesquisado. A questão faz sentido.
Restabelecer Monica