O que há de novo em estruturas de dados puramente funcionais desde Okasaki?

563

Desde o livro de Chris Okasaki, de 1998, "Estruturas de dados puramente funcionais", não vi muitas novas estruturas de dados puramente funcionais interessantes; Eu posso citar apenas alguns:

  • IntMap (também inventado por Okasaki em 1998, mas não presente nesse livro)
  • Dedo árvores (e sua generalização sobre monóides)

Existem também algumas maneiras interessantes de implementar estruturas de dados já conhecidas, como o uso de "tipos aninhados" ou "tipos de dados algébricos generalizados" para garantir invariáveis ​​em árvores.

Que outras novas idéias surgiram desde 1998 nesta área?

jkff
fonte
20
Boa pergunta. Acabei de receber uma pergunta de um aluno e não sabia a resposta.
Suresh Venkat
Isso é bom para aqui, mas você pode obter melhores respostas no Stack Overflow. Se você perguntar por lá, não se esqueça de criar um link para a discussão aqui.
Charles Stewart
3
Bem, o Haskell Reddit já viu isso, então também haverá boas respostas, mas uma excelente pergunta. No meio do livro de Okasaki, eu me perguntava o mesmo. 1
Robert Massaioli

Respostas:

553

Novas estruturas de dados puramente funcionais publicadas desde 1998:

Conhecido em 1997, mas não discutido no livro de Okasaki:

  • Muitos outros estilos de árvore de pesquisa equilibrada . AVL, irmão, equilíbrio de classificação, equilíbrio limitado e muitas outras árvores de pesquisa equilibradas podem ser (e foram) implementadas puramente funcionalmente através da cópia de caminho. Talvez merecem menção especial:

    • Árvores de Pesquisa Parcial , de Samuel W. Bent, Daniel D. Sleator e Robert E. Tarjan : Um elemento-chave nos artigos de Brodal et al., 2006, e Demaine et al., Em 2008.
  • Conjuntos infinitos que admitem busca rápida e exaustiva , de Martín Escardó : Talvez não seja uma estrutura de dados em si .

  • Três algoritmos no Braun Trees , de Chris Okasaki : As árvores Braun oferecem muitas operações de pilha no pior caso O (lg n). Esse limite é superado por muitas outras estruturas de dados, mas as árvores Braun têm umaconsoperação preguiçosa em seu segundo argumento e, portanto, podem ser usadas como pilhas infinitas de algumas maneiras que outras estruturas não podem.

  • A pilha min-max descontraída: Uma fila de prioridade dupla combinável e A pilha KD: Uma fila de prioridade multidimensional eficiente , de Yuzheng Ding e Mark Allen Weiss : Elas são puramente funcionais, embora isso não seja discutido nos documentos . Eu não acho que os limites de tempo alcançados sejam melhores do que aqueles que podem ser alcançados usando árvores de dedos (de Hinze & Paterson ou Kaplan & Tarjan) como filas de prioridade k-dimensional, mas acho que as estruturas de Ding & Weiss usam menos espaço .

  • The Zipper , de Gérard Huet : Usado em muitas outras estruturas de dados (como as árvores de dedos de Hinze & Paterson), essa é uma maneira de transformar uma estrutura de dados de dentro para fora.

  • Listas de diferença são O (1) listas que podem ser passadas com uma transformação O (n) em conslistas comuns . Aparentemente, eles são conhecidos desde a antiguidade na comunidade Prolog, onde eles têm uma transformação O (1) em conslistas comuns . A transformação O (1) parece impossível na programação funcional tradicional, mas a abstração do buraco de Minamide, do POPL '98, discute uma maneira de permitir a transformação de O (1) append e O (1) dentro da programação funcional pura. Diferentemente das implementações usuais de programação funcional das listas de diferenças, que são baseadas no fechamento de funções, as abstrações de furos são essencialmente as mesmas (tanto no uso quanto na implementação) das listas de diferenças do Prolog. No entanto, parece que durante anos a única pessoa que percebeu isso foium dos revisores de Minamide .

  • O(n)Θ(nlgn)Θ(nlgn)Θ(lg2n)

Estruturas de dados principalmente funcionais, antes, durante e depois do livro de Okasaki:

  • O(m)mO(lglgn)

  • 1989: Árvores de Pesquisa Aleatória por Cecilia R. Aragon e Raimund Seidel : Estas foram discutidas em um ambiente puramente funcional por Guy E. Blelloch e Margaret Reid-Miller em Fast Set Operations Using Treaps e por Dan Blandford e Guy Blelloch em Functional Set Operations com Treaps ( código) Eles fornecem todas as operações de árvores de dedos puramente funcionais e árvores de pesquisa tendenciosas, mas requerem uma fonte de aleatoriedade, tornando-as não puramente funcionais. Isso também pode invalidar a complexidade do tempo das operações nas treaps, assumindo um adversário que pode cronometrar as operações e repetir as longas. (Esse é o mesmo motivo pelo qual argumentos de amortização imperativos não são válidos em um ambiente persistente, mas requer um adversário com um cronômetro)

  • 1997: Skip-trees, uma estrutura de dados alternativa às Skip-lists em uma abordagem simultânea , de Xavier Messeguer e Explorando a dualidade entre listas de ignoradas e árvores de pesquisa binária , de Brian C. Dean e Zachary H. Jones : as listas de ignoradas não são puramente funcionais, mas eles podem ser implementados funcionalmente como árvores. Como tréguas, eles exigem uma fonte de bits aleatórios. (É possível tornar as listas de pulos deterministas, mas, depois de traduzi-las em uma árvore, acho que elas são apenas outra maneira de olhar para 2 a 3 árvores.)

  • 1998: Todas as estruturas amortizadas no livro de Okasaki! Okasaki inventou esse novo método para misturar estruturas de dados funcionais e de amortização, que antes eram consideradas incompatíveis. Depende da memorização, que, como Kaplan e Tarjan mencionaram algumas vezes, é na verdade um efeito colateral. Em alguns casos ( como PFDS em SSDs por razões de desempenho ), isso pode ser inapropriado.

  • 1998: Listas simples de catenáveis ​​persistentemente confluentes , de Haim Kaplan, Chris Okasaki e Robert E. Tarjan : Usa a modificação sob o capô para fornecer deques O (1) catenáveis ​​amortizados, apresentando a mesma interface de um anterior (puramente funcional, mas com memorização) ) que aparece no livro de Okasaki. Kaplan e Tarjan haviam criado anteriormente uma estrutura de pior caso O (1) puramente funcional, mas é substancialmente mais complicada.

  • 2007: Conforme mencionado em outra resposta desta página, estruturas de dados semi-persistentes e união persistente - encontradas por Sylvain Conchon e Jean-Christophe Filliâtre

Técnicas para verificar estruturas funcionais de dados, antes, durante e depois do livro de Okasaki:

Estruturas ou análises de dados imperativas não discutidas no livro de Okasaki, mas relacionadas a estruturas de dados puramente funcionais:

  • The Soft Heap: uma fila de prioridade aproximada com taxa de erro ideal , por Bernard Chazelle : Essa estrutura de dados não usa matrizes e, portanto, tentou primeiro o canal IRC #haskell e, posteriormente , os usuários do Stack Overflow , mas incluideletein (lg n) , o que geralmente não é possível em um ambiente funcional e a análise amortizada imperativa, que não é válida em um ambiente puramente funcional.

  • Árvores de pesquisa binária equilibrada com atualizações de dedo O (1) . Em Tornando as estruturas de dados persistentes , James R. Driscoll, Neil Sarnak, Daniel D. Sleator e Robert E. Tarjan apresentam um método para agrupar os nós em uma árvore vermelho-preta para que as atualizações persistentes exijam apenas O (1) espaço. Os deques puramente funcionais e as árvores de dedos projetadas por Tarjan, Kaplan e Mihaescu usam uma técnica de agrupamento muito semelhante para permitir atualizações de O (1) nas duas extremidades. As árvores AVL para pesquisa localizada por Athanasios K. Tsakalidis funcionam de maneira semelhante.

  • Montões de emparelhamento mais rápido ou melhor limites para montões de emparelhamento : Desde o livro de Okasaki foi publicado, várias novas análises dos montes emparelhamento imperativas apareceram, incluindo montes emparelhamento com O (log log n) diminuir o custo por Amr Elmasry e Rumo a uma análise final do emparelhamento Heaps por Seth Pettie. Pode ser possível aplicar parte desse trabalho aos preguiçosos pares de Okasaki.

  • Árvores de dedos deterministas tendenciosas : nas Listas de pulos tendenciosos , de Amitabha Bagchi, Adam L. Buchsbaum e Michael T. Goodrich, um design é apresentado para listas de pulos tendenciosos determinísticos. Através da transformação de lista de ignorados / árvore mencionada acima, pode ser possível criar árvores de pesquisa tendenciosas determinísticas. As listas de pulos tendenciosos para os dedos, descritas por John Iacono e Özgür Özkan nos Dicionários mescláveis, podem ser possíveis em pular árvores tendenciosas. Uma árvore de dedos enviesada é sugerida por Demaine et al. em seu artigo sobre tentativas puramente funcionais (veja acima) como uma maneira de reduzir os limites de tempo e espaço na atualização dos dedos nas tentativas.

  • A Árvore B de Cordas: Uma Nova Estrutura de Dados para Pesquisa de Cordas na Memória Externa e suas Aplicações de Paolo Ferragina e Roberto Grossi é uma estrutura de dados bem estudada que combina os benefícios de tentativas e árvores B.

jbapple
fonte
5
Não me lembro de marcar a caixa "wiki da comunidade" nesta resposta. Existe alguma maneira de desfazer isso?
Jbapple
7
@jbapple: após um certo número de edições, todas as postagens se tornam wiki da comunidade. Essa é uma revisão impressionantemente completa lá. Obrigado.
Phil Miller
29
Ótima lista! O que me faz desejar que a Okasaki publique uma segunda edição.
Radu GRIGore
4
Observe que Isabelle / HOL pode gerar código para SML, OCaml, Haskell, Scala. A ferramenta Haskabelle também pode importar o Haskell para o Isabelle / HOL.
Makarius 4/03/13
2
A terminologia da "extração de programa" é uma das Coq: você pega uma prova construtiva e faz dela um programa executável, retirando algumas coisas. Em Isabelle, isso é chamado de "geração de código" e funciona de maneira diferente, usando as especificações da HOL como pseudo-código, não as provas. A extração de prova em Isabelle / HOL, de acordo com Berghofer, funciona como Coq, mas raramente é usada atualmente.
Makarius 4/03/13
63

Nas excelentes anotações já feitas, acrescentarei Zíperes .

Huet, Gerard. “Pérola Funcional: O Zíper” Journal of Functional Programming 7 (5): 549-554, setembro de 1997.

Wikipedia: Zipper (estrutura de dados)

Matt Might
fonte
4
Zíperes são INCRÍVEIS. Para muitos casos de uso, eles permitem representações baseadas árvores para se tornar a escolha "certa" para muitos tipos de dados, onde de outra forma seria um pouco mais complicado
Carter Tazio Schonwald
1
Um exemplo de uso para manipulação de XML: anti-xml.org/zippers.html
Caracol mecânico
40

Conchon, Filliatre, uma estrutura de dados persistente da UNION-FIND e estruturas de dados semi-persistentes .

Radu GRIGore
fonte
Uau, um persistente encontro de união! Obrigado!
Jkff 21/09/10
3
Bem, mais ou menos ... Veja o artigo.
Radu GRIGore
1
... ou, se preferir, veja algum código (de Matt Parkinson) github.com/septract/jstar/blob/master/src/utils/…
Radu GRIGore
5
Agora vejo por que o comentário "tipo de .." teve um voto positivo. Eles têm bom desempenho apenas quando alguém quase exclusivamente não usa persistência ou recua o tempo todo: se você costuma usar as versões "nova" e "antiga", está ferrado. Idéia legal de redirecionar embora.
Jkff 22/09/10
O link de Radu agora pode ser encontrado em github.com/septract/jstar-old/blob/…
jbapple
20

Eu adicionaria a versão de zíperes de McBride como derivada de tipos de dados.

Nenhum
fonte
Eu amo essas coisas. É tão legal que o derivado tem uma aplicação tão diferente de encontrar taxas de variação!
SamB
3
SamB, você também pode estar interessado em derivadas de expressões regulares (se você ainda não as conhecia).
Jbapple
14

Rangemaps

É uma estrutura de dados especializada, mas pode ser usada como um substituto da DIET de Martin Erwig, com propriedades ligeiramente diferentes, portanto, pelo menos, existe uma estrutura de dados existente para compará-la. A própria DIET foi descrita em um artigo no JFP em 1998, portanto, talvez não esteja incluída nas Estruturas de Dados Puramente Funcionais.

Complicado ver biografia
fonte
7

Na sequência do documento de 2012 acima, o trabalho sobre vetores RRB foi estendido e publicado no ICFP'15.

Vetor RRB: uma sequência imutável de propósito geral prático http://dl.acm.org/citation.cfm?id=2784739

Mike Rainey
fonte