Librerie per strutture dati rigide in Haskell

Question

Quali librerie esistono che implementano strutture di dati rigide? Nello specifico, sto cercando liste rigide e set severi.

Avvertenze:

1. Sono consapevole delle deepseq. È molto utile, ma aggiunge il sovraccarico di attraversare l'intera struttura dei dati ogni volta che usi deepseq (che potrebbe essere più di una volta).

2. Sono consapevole che una rigida struttura di dati a contenitore non si garantire tutto ciò che contiene sarà pienamente valutato, ma la struttura stesso dovrebbe essere rigorosi, ad esempio:

   data StrictList a = !a :$ !(StrictList a) | Empty 
   

   (Qui, la gli elementi contenuti sono in WHNF, e forse non completamente valutati, ma la struttura della lista è. Ad esempio, gli elenchi infiniti saranno valori non terminanti)

3. Conosco il pacchetto "strict" su hackage, ma ha un limite molto d set di rigide strutture di dati. Non contiene né rigidi elenchi né set.

4. scrivere liste severe me sembra incredibilmente facile (mi piace estensioni di ghc derivare Functor, Traversable e pieghevole, btw.), Ma sembra ancora come sarebbe meglio fatto in una libreria separata. E implementazioni efficienti di insiemi non mi sembrano così banali.

Answer 1

Il containers pacchetto (fornito con GHC) avranno presto rigida serie e Mappa varianti (non sono sicuro che saranno incluse con GHC-7.4, ma non c'è motivo di sperare). Quindi è in arrivo un'implementazione efficiente di Set e Maps rigidi. Gli elenchi rigidi sono, come dici tu, ancora un pacchetto su hackage che li fornisce sarebbe bello, quindi non tutti devono farlo da soli. Cos'altro ti serve?

Answer 2

Per il secondo punto, il termine che ho visto più spesso è spinoso.

Per un elenco rigoroso della colonna vertebrale, è possibile utilizzare probabilmente Data.Seq.Sequence (da contenitori) o Data.Vector (da vector). Nessuno dei due è un elenco, tuttavia a seconda di ciò che si sta facendo uno (o entrambi) è probabile che sia migliore. Sequence fornisce O (1) cons e snoc, con un accesso molto veloce a entrambe le estremità della struttura. Le prestazioni di Vector sono simili a quelle di un array. Se vuoi un'interfaccia più simile a Sequence, potresti prendere in considerazione il pacchetto ListLike (c'è anche un'interfaccia ListLike per i vettori, ma è meno utile perché Vector fornisce un'interfaccia abbastanza completa da sola). Entrambi sono rigorosi alla spina dorsale.

Per set rigorosi, è possibile provare unordered-containers, che fornisce anche una mappa rigorosa.