Sto cercando una struttura dati Haskell che memorizzi un elenco ordinato di elementi e che sia efficiente nel tempo per scambiare coppie di elementi in posizioni arbitrarie all'interno dell'elenco. Non è [a], ovviamente. Non è Vector perché lo scambio crea nuovi vettori. Quale struttura dati è efficiente in questo?Struttura dati Haskell efficiente per lo scambio di elementi?
Haskell è un linguaggio funzionale (quasi) puro, quindi qualsiasi struttura di dati che si aggiorna dovrà fare una nuova copia della struttura e riutilizzare gli elementi di dati è vicino al meglio che si possa fare. Inoltre, la nuova lista verrebbe ponderata e tipicamente solo la colonna vertebrale avrebbe bisogno di essere creata fino a quando non saranno necessari i dati. Se il numero di aggiornamenti è piccolo rispetto al numero di elementi, è possibile creare un elenco di differenze che controlli prima un insieme di aggiornamenti sparsi e solo dopo guardi nel vettore originale.
Data.Sequence dal pacchetto containers potrebbe essere una struttura di dati non terribile per iniziare per questo caso d'uso.
Le implementazioni più efficienti delle strutture di dati persistenti, che mostrano gli aggiornamenti O (1) (nonché l'aggiunta, il prepending, il conteggio e l'affettatura), si basano sull'algoritmo Trie Array Mapped. Le strutture dati vettoriali di Clojure e Scala si basano su di esso, ad esempio. L'unica implementazione Haskell di quella struttura dati che conosco è presentata da the "persistent-vector" package.
Questo algoritmo è molto giovane, è stato presentato solo per la prima volta nell'anno 2000, il che potrebbe essere il motivo per cui non così tante persone ne hanno mai sentito parlare. Ma la cosa si rivelò essere una soluzione così universale che si adattò per gli hash-table poco dopo. La versione adattata di questo algoritmo è chiamata Hash Array Mapped Trie. È anche usato in Clojure e Scala per implementare le strutture di dati Set e Map. È anche più ubiquitario in Haskell con pacchetti come "unordered-containers" e "stm-containers" che ruotano attorno ad esso.
Per saperne di più su l'algoritmo vi consiglio i seguenti link:
Sono stato sorpreso di leggere che gli aggiornamenti costavano solo O (1), anche con la riserva sull'albero. È piuttosto buono. Potresti voler menzionare alcuni limiti di complessità nella tua risposta. – chi
Edward Kmett ha lavorato su alcune strutture simili. Non sono sicuro di quanto sia vicino a un rilascio. – dfeuer
[a] è una lista collegata che è abbastanza efficiente di manipolazione dell'elemento. Se il tuo problema è l'indicizzazione efficiente, la soluzione dipenderà dal caso d'uso effettivo. Forse [zippers] (https://wiki.haskell.org/Zipper) ti aiuterà? –
Stai chiedendo informazioni su ['Data.Vector.Mutable'] (https://hackage.haskell.org/package/vector-0.11.0.0/docs/Data-Vector-Mutable.html)? – Bakuriu
Guarda anche [Corde] (https://en.wikipedia.org/wiki/Rope_%28data_structure%29) –