pomaps: Maps and sets of partial orders
Maps (and sets) indexed by keys satisfying PartialOrd.
The goal is to provide asymptotically better data structures than simple association lists or lookup tables. Asymptotics depend on the partial order used as keys, its width \(w\) specifically (the size of the biggest anti-chain).
For partial orders with great width, this package won't provide any benefit over using association lists, so benchmark for your use-case!
[Skip to Readme]
Flags
Automatic Flags
| Name | Description | Default |
|---|---|---|
| no-lattices | Don't depend on the lattices package and extract the PartialOrd class. | Disabled |
Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info
Downloads
- pomaps-0.0.0.4.tar.gz [browse] (Cabal source package)
- Package description (revised from the package)
Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
| Versions [RSS] | 0.0.0.1, 0.0.0.2, 0.0.0.3, 0.0.0.4, 0.0.1.0, 0.0.2.0, 0.0.2.1, 0.1.0.0, 0.2.0.0, 0.2.0.1 |
|---|---|
| Change log | CHANGELOG.md |
| Dependencies | base (>=4.6.0.0 && <4.12), containers (>=0.5.9.2 && <=0.5.11.0), deepseq (>=1.1 && <1.5), ghc-prim (>=0.4 && <0.6), lattices (>=1.7 && <2) [details] |
| License | MIT |
| Author | |
| Maintainer | Sebastian Graf <sgraf1337@gmail.com> |
| Revised | Revision 1 made by HerbertValerioRiedel at 2019-04-27T17:28:37Z |
| Category | Data Structures |
| Home page | https://github.com/sgraf812/pomaps#readme |
| Bug tracker | https://github.com/sgraf812/pomaps/issues |
| Source repo | head: git clone https://github.com/sgraf812/pomaps |
| Uploaded | by sgraf812 at 2018-04-08T19:07:23Z |
| Distributions | |
| Reverse Dependencies | 1 direct, 1 indirect [details] |
| Downloads | 4794 total (28 in the last 30 days) |
| Rating | (no votes yet) [estimated by Bayesian average] |
| Your Rating | |
| Status | Docs available [build log] Last success reported on 2018-04-13 [all 1 reports] |
Readme for pomaps-0.0.0.4
[back to package description]pomaps 
Reasonably fast maps (and possibly sets) based on keys satisfying PartialOrd.
This package tries to load off as much work as possible to the excellent containers library, in order to achieve acceptable performance.
The interface is kept as similar to Data.Map.{Strict,Lazy} as possible, which is an excuse for somewhat lacking documentation.
POMaps basically store a decomposition of totally ordered chains (e.g. something Maps can handle).
Functionality and strictness properties should be pretty much covered by the testsuite.
But it's not battle-tested yet, so if you encounter space leaks in the implementation, let me know.
A rather naive implementation leads to O(w*n*log n) lookups, where w is the width of the decomposition (which should be the size of the biggest anti-chain).
This is enough for me at the moment to get things going, but there is room for improvement (Sorting and Selection in Posets).
Let me know if things are too slow and I'll see what I can do!