discrimination

Fast generic linear-time sorting, joins and container construction.

http://github.com/ekmett/discrimination/

Version on this page:0.3@rev:1
LTS Haskell 23.19:0.5@rev:4
Stackage Nightly 2024-12-09:0.5@rev:4
Latest on Hackage:0.5@rev:4

See all snapshots discrimination appears in

BSD-3-Clause licensed by Edward A. Kmett
Maintained by Edward A. Kmett
This version can be pinned in stack with:discrimination-0.3@sha256:6f88488e62fd4aca71497a4909371476eb18720b3c113869e769a65d1bdb69dc,2525

Module documentation for 0.3

discrimination

Hackage Build Status

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.

Contact Information

Contributions and bug reports are welcome!

Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.

-Edward Kmett

Changes

0.3

  • Fixed a corner case where conquer would lie and return an empty equivalence class when fed no inputs.

0.2.1

  • promises 0.3 support
  • vector 0.11 support
  • transformers 0.5 support
  • transformers-compat support
  • ghc 8 support

0.2

  • grouping is now much more efficient.

0.1

  • grouping is now productive. This means it can start spitting out results as it goes! To do this I created the promises package and switched to using it behind the scenes for many combinators that consume a Group. This has a bunch of knock-on effects:
    • grouping is now working properly with respect to its law!
    • grouping now 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 sorting?

0

  • Initialized repository