This package provides linear time sorting, partitioning, and joins for a wide array of Haskell data types. This work is based on a “final encoding” of the ideas presented in multiple papers and talks by Fritz Henglein.
By adopting a final encoding we can enjoy many instances for standard classes, lawfully, without quotienting.
Contributions and bug reports are welcome!
Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.
- GHC-9.0 compatibility
- Fixed a corner case where
conquerwould lie and return an empty equivalence class when fed no inputs.
- ghc 8 support
groupingis now much more efficient.
groupingis now productive. This means it can start spitting out results as it goes! To do this I created the
promisespackage and switched to using it behind the scenes for many combinators that consume a
Group. This has a bunch of knock-on effects:
groupingis now working properly with respect to its law!
groupingnow uses an American-flag style top-down radix sort rather than a bottom up radix sort for all operations. This is sadly required for productivity. This will use a lot more memory for intermediate arrays, as we don’t get to return them to storage after we’re done.
- We now use much smaller intermediate arrays for
grouping. Should we do the same for
- Initialized repository