Quais são as questões pendentes em estruturas de dados puramente funcionais?

51

Essa pergunta é inspirada em outra pergunta sobre o que há de novo no PFDS desde a publicação do livro de Okasaki em 1998 .

Vou começar com duas perguntas que tenho:

  • Existe uma estrutura de dados de conjunto puramente funcional que se aproxima da velocidade das tabelas de hash? Tentativas ainda não estão lá.
  • Existem árvores de dedos puramente funcionais com O (1) anexado? O melhor até agora é O (lg lg n), desenvolvido por Kaplan e Tarjan.

Que outros problemas de estrutura de dados puramente funcionais estão abertos?

big-list ds.data-structures functional-programming jbapple
fonte
Acho que você quer dizer tentativas como em árvores de hash, em vez dos dicionários mais gerais com chaves que são seqüências? FWIW, acho que é impossível abordar a boa e antiga tabela de hash aqui.
quer

Respostas:

19

Vou interpretar a questão de maneira um tanto liberal. Para estruturas de dados no estilo Okasaki, a memorização é uma forma de mutação implícita que afeta o tempo de execução. Portanto, levarei a questão a se referir a estruturas de dados persistentes no sentido estrito, em vez de estruturas de dados com uma implementação puramente funcional, que é um subconjunto da primeira. Por estrito, quero dizer que você deve acessar versões mais antigas de uma estrutura de dados sem penalidade, a árvore de versões pode ramificar-se arbitrariamente etc.

Nesse contexto, considero o persistente UNION-FIND um importante problema em aberto. Há o artigo de Conchon-Filliâtre que foi mencionado no outro tópico. Um comentarista já levantou um problema com a chamada matriz persistente: é realmente apenas semi-persistente. Mas suponha que você o substitua por um hash trie ou algum outro array verdadeiramente persistente que se comporte melhor no pior caso (e sem dúvida médio), mas pior no melhor caso. Isso ainda deixa uma questão importante em aberto:

O artigo fornece uma prova formal de correção no Coq. Mas eles falham em abordar a complexidade amortizada formal ou informalmente. É muito não claro para mim que a complicada por trás das cenas de mutação resulta na complexidade amortizado esperado em todos os casos. Quando pensei pela última vez sobre isso, senti-me um pouco confiante de que poderia construir um contra-exemplo se me esforçasse. Mesmo que eu esteja errado sobre essa última parte, a falta de uma análise adequada é uma grande lacuna; é claro que a análise clássica de amortização de Trajan do UNION-FIND não é transferida diretamente.

Per Vognsen
fonte
5
Um candidato para matrizes totalmente persistentes (mas não persistentemente confluentes) é apresentado em Tentativas Confluentemente Persistentes para Controle de Versão Eficiente . Os autores alegam desaceleração O (lg lg n), superando a desaceleração O (lg lg m) de Dietz et al, onde m é o número de operações que foram executadas na matriz.
Jbapple
11
Acrescentarei também que, embora as estruturas preguiçosas amortizadas de Okasaki sejam muitas vezes muito mais simples que as alternativas, não conheço nenhuma estrutura de dados que possa ser implementada dessa maneira que também não possa ser implementada (com o mesmo tempo, mas na pior das hipóteses) de uma maneira verdadeiramente puramente funcional.
Jbapple
12

Que outros problemas de estrutura de dados puramente funcionais estão abertos?

Aqui está um:

Qual é o equivalente puramente funcional de uma tabela de hash fraca?

Jon Harrop
fonte
15
hum .... o OP solicitou perguntas sem resposta, portanto isso se qualificaria como uma resposta potencial à pergunta do OP.
Jason S
6
Ok, eu vou morder. O que é uma tabela de hash fraca?
Jeffε
4
É uma tabela de hash que permite que seus elementos sejam coletados de lixo se apenas ele (e outros mapas fracos) contiverem referências a ele.
Havvy
3
@ JonHarrop: é fácil provar que uma versão pura de uma referência fraca é impossível, pois as referências fracas tornam a semântica da linguagem não determinística e as linguagens puramente funcionais são determinísticas. Se você marcar adicionalmente o não determinismo no tipo, a implementação usual funcionará. Você precisa de tipos dependentes (para provar que uma implementação fornece as mesmas respostas, independentemente do conteúdo da referência), se desejar mascarar o efeito com segurança.
Neel Krishnaswami
5
@NeelKrishnaswami, não acho que seja esse o caso. Você pode criar estruturas de dados fracas que não criam não determinismo, como uma tabela fraca que não suporta enumeração (ou contagem). Veja wiki.ecmascript.org/doku.php?id=harmony:weak_maps para um exemplo.
Sam Tobin-Hochstadt