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

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?

Novas estruturas de dados puramente funcionais publicadas desde 1998:

• 2001: Ideal Hash Trees , e seu predecessor de 2000, Fast And Space Efficient Trie Searches , por Phil Bagwell : Aparentemente usado como um bloco de construção fundamental na biblioteca padrão da Clojure.

• 2001: Uma Técnica de Implementação Simples para Filas de Pesquisa Prioritária , por Ralf Hinze : uma técnica realmente simples e bonita para implementar essa importante estrutura de dados (útil, por exemplo, no algoritmo Dijkstra). A implementação é particularmente bonita e legível devido ao uso intenso de "padrões de exibição".

• 2002: Bootstrapping de matrizes flexíveis unilaterais , por Ralf Hinze : Semelhante às listas de acesso aleatório de Okasaki, mas elas podem ser ajustadas para alterar a troca de tempo entre conse indexação.

• 2003: Novos deques catenáveis ​​e não catenáveis , de Radu Mihaescu e Robert Tarjan : Uma nova visão de alguns trabalhos mais antigos (de Kaplan e Tarjan) que Okasaki cita (a versão mais recente do trabalho de Kaplan & Tarjan foi publicada em 2000 ). Esta versão é mais simples em alguns aspectos.

• 2005: Montes maxifóbicos ( papel e código ), por Chris Okasaki : Apresentado não como uma estrutura nova e mais eficiente, mas como uma maneira de ensinar filas prioritárias.

• 2006: Listas classificadas catenáveis ​​em tempo constante, no pior dos casos, puramente funcionais , de Gerth Stølting Brodal, Christos Makris e Kostas Tsichlas : Responde a uma excelente pergunta de Kaplan e Tarjan, demonstrando uma estrutura com O (lg n) inserção, pesquisa e exclusão e O (1) concat.

• 2008: Tentativas Confluentemente Persistentes para Controle Eficiente de Versão , por Erik D. Demaine, Stefan Langerman e Eric Price : Apresenta várias estruturas de dados para tentativas que têm navegação e modificação eficientes perto das folhas. Alguns são puramente funcionais. Outros, na verdade, melhoram uma estrutura de dados de longa data de Dietz et al. para matrizes totalmente persistentes (mas não confluentemente persistentes ou puramente funcionais). Este artigo também apresenta árvores de corte de link puramente funcionais , às vezes chamadas de "árvores dinâmicas".

• 2010: Um novo algoritmo de exclusão puramente funcional para árvores vermelho-preto , por Matt Might : Como o algoritmo de inserção de árvore vermelho-preto da Okasaki, essa não é uma nova estrutura de dados ou uma nova operação em uma estrutura de dados, mas uma maneira nova e mais simples de escreva uma operação conhecida.

• 2012: RRB-Trees: Efficient Immutable Vectors , por Phil Bagwell e Tiark Rompf : Uma extensão para Hash Array Mapped Tries, suportando concatenação imutável de vetores, inserção e divisão em tempo O (lg n), mantendo o índice, atualizando e velocidades de inserção do vetor imutável original.

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(\sqrt{n})$$\Theta(n \lg n)$$\Theta(\sqrt{n \lg n})$$\Theta(\lg^2 n)$

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

• $O(m)$$m$$O(\lg \lg n)$

• 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:

• Tipos fantasmas são um método antigo para criar uma API que não permite certas operações mal formadas. Um uso sofisticado deles pode ser encontrado nas capacidades estáticas leves de Oleg Kiselyov e Chung-chieh Shan .

• Tipos aninhados não são realmente mais recentes que 1998 - Okasaki até os usa em seu livro. Existem muitos outros exemplos que não estão no livro de Okasaki; alguns são novos e outros são antigos. Eles incluem:

  • Árvores vermelho-pretas de Stefan Kahrs com tipos ( código )
  • Árvores AVL de Ross Paterson ( espelho )
  • De Chris Okasaki Da exponenciação rápida às matrizes quadradas: uma aventura em tipos
  • Notação de Richard S. Bird e Ross Peterson de Bruijn como um tipo de dados aninhado
  • Representações numéricas de Ralf Hinze como tipos de dados aninhados de ordem superior .

• Os GADTs também não são tão novos assim. Eles são uma adição recente a Haskell e alguns MLs, mas estão presentes, creio, em vários cálculos lambda datilografados desde os anos 1970 .

• 2004-2010: Coq e Isabelle para correção . Várias pessoas usaram provadores de teoremas para verificar a correção de estruturas de dados puramente funcionais. A Coq pode extrair essas verificações para o código de trabalho em Haskell, OCaml e Scheme; Isabelle pode extrair para Haskell, ML e OCaml.

  • Coq:
    • Pierre Letouzey e Jean-Christophe Filliâtre formalizaram as árvores vermelho-preto e AVL (ish), encontrando um erro na biblioteca padrão do OCaml no processo .
    • I formalizada de Brodal e Okasaki assintoticamente ótimos filas de prioridade .
    • Arthur Charguéraud formalizou 825 das 1.700 linhas de ML no livro de Okasaki .
  • Isabelle:
    • Tobias Nipkow e Cornelia Pusch formalizaram as árvores AVL .
    • Viktor Kuncak formalizou árvores de busca binária desequilibradas .
    • Peter Lammich publicou A estrutura Isabelle Collections , que inclui formalizações de estruturas de dados puramente funcionais eficientes, como árvores e tentativas de vermelho-preto, bem como estruturas de dados que são menos eficientes quando usadas persistentemente, como filas de duas pilhas (sem o truque de preguiça de Okasaki ) e tabelas de hash.
    • Peter Lammich também publicou formalizações de autômatos de árvores , árvores de dedos de Hinze & Patterson (com Benedikt Nordhoff e Stefan Körner) e filas prioritárias puramente funcionais de Brodal e Okasaki (com Rene Meis e Finn Nielsen).
    • René Neumann formalizou as filas binomiais de prioridade .

• 2007: Typechecking refinado com Stardust , por Joshua Dunfield : Este artigo usa tipos de refinamento para ML para encontrar erros na função de exclusão de árvore vermelho-preto do SMLNJ.

• 2008: Análise leve e complexa da complexidade do tempo semiformal para estruturas de dados puramente funcionais por Nils Anders Danielsson : Usa o Agda com anotação manual para provar limites de tempo para alguns PFDS.

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.

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)

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

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

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.

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