Monthly Downloads: 42
Programming language: Haskell
License: MIT License
Tags: Data Structures    
Latest version: v0.1.0.0

pomaps alternatives and similar packages

Based on the "Data Structures" category.
Alternatively, view pomaps alternatives based on common mentions on social networks and blogs.

Do you think we are missing an alternative of pomaps or a related project?

Add another 'Data Structures' Package


pomaps Build Status Hackage

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!