Implementação de estrutura de dados imutável (persistente) semelhante a uma matriz com indexação rápida, acréscimo, pré-acréscimo, iteração

Estou procurando uma estrutura de dados persistente semelhante à matriz (mas imutável), permitindo operações rápidas de indexação, acréscimo, pré-acréscimo e iteração (boa localidade).

O Clojure fornece Vector persistente, mas é apenas para anexação rápida. O vetor de Scala efetivamente anexa e pré-anexa em tempo constante, mas não consigo entender como ela é implementada, pois é baseada na mesma estrutura de dados (vetor trie com mapeamento de bits) que o vetor Clojure e, como eu entendo, vetor trie com mapeamento em bit não pode ter um prefixo rápido sem alguns truques.

Não estou interessado em estar pronto para usar a implementação, mas em uma descrição de como implementar essa estrutura de dados.

O candidato óbvio é uma árvore binária equilibrada persistente . Todas as operações listadas podem ser executadas em ou O ( lg n ) , usando a cópia de caminho . Para mais detalhes sobre como atingir esse tempo de execução, consulte o livro de Chris Okasaki mencionado abaixo ou minha resposta aqui .$O(1)$$O(\lg n)$

Obviamente, como uma variante, cada folha dessa árvore poderia conter uma matriz imutável (uma sequência de valores consecutivos). Isso torna a atualização de um valor menos eficiente, mas pode funcionar bem para a sua situação, se você nunca pretender modificar um valor existente, basta acrescentar e acrescentar. Dessa maneira, seu vetor é representado como uma sequência de sequências imutáveis, representada como uma árvore binária equilibrada com matrizes imutáveis ​​nas folhas. Isso permite indexação rápida (logarítmica no número de folhas), adição e pré-adição rápidas e iteração rápida. A pior complexidade assintótica não é melhor, mas o desempenho na prática pode ser significativamente melhor.

A referência padrão é o livro de Chris Okasaki, de 1998, "Estruturas de dados puramente funcionais".
Veja também

• Quais classes de estruturas de dados podem ser feitas persistentes?
• O que há de novo em estruturas de dados puramente funcionais desde Okasaki?
• Quais são as questões pendentes em estruturas de dados puramente funcionais?
• Dez anos de estruturas de dados puramente funcionais

Descrevi uma implementação dessa estrutura de dados em meu artigo sobre correspondência incremental de expressões regulares - consulte http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation e o texto abaixo e acima dessa seção .

É uma variedade de árvores de altura constante (como árvores B ou 2-3 árvores). Basicamente, é uma (2,3) árvore, cujas folhas são (N, 2N-1) matrizes, para evitar sobrecarga por elemento. (Uma matriz (N, 2N-1) é uma matriz cujos comprimentos estão no intervalo N..2N-1.) N maior fornece uma sobrecarga menor, mas aumenta linearmente a complexidade da divisão e concatenação. Operações como indexação, divisão e concatenação são muito semelhantes à maneira como trabalham em 2-3 árvores, generalizando para (N, 2N-1) no nível da folha.