nonempty-containers

Non-empty variants of containers data types, with full API

https://github.com/mstksg/nonempty-containers#readme

Version on this page:0.3.4.4
LTS Haskell 23.0:0.3.4.5
Stackage Nightly 2024-12-09:0.3.4.5
Latest on Hackage:0.3.4.5

See all snapshots nonempty-containers appears in

BSD-3-Clause licensed by Justin Le
Maintained by [email protected]
This version can be pinned in stack with:nonempty-containers-0.3.4.4@sha256:a39a1373560ce7e8ed448712bf157d0be671045bdc18ed7c9edc4ea7df43dbf2,2705

nonempty-containers

Efficient and optimized non-empty (by construction) versions of types from containers. Inspired by non-empty-containers library, except attempting a more faithful port (with under-the-hood optimizations) of the full containers API. Also contains a convenient typeclass abstraction for converting between non-empty and possibly-empty variants, as well as pattern synonym-based conversion methods.

Non-empty by construction means that the data type is implemented using a data structure where it is structurally impossible to represent an empty collection.

Unlike similar packages (see below), this package is defined to be a drop-in replacement for the containers API in most situations. More or less every single function is implemented with the same asymptotics and typeclass constraints. An extensive test suite (with 457 total tests) is provided to ensure that the behavior of functions are identical to their original containers counterparts.

Care is also taken to modify the interface of specific functions to reflect non-emptiness and emptiness as concepts, including:

  1. Functions that might return empty results (like delete, filter) return possibly-empty variants instead.

  2. Functions that totally partition a non-empty collection (like partition, splitAt, span) would previously return a tuple of either halves:

    mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c)
    

    The final result is always a total partition (every item in the original map is represented in the result), so, to reflect this, These is returned instead:

    data These a b = This  a
                   | That    b
                   | These a b
    
    mapEither :: (a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c)
    

    This preserves the invariance of non-emptiness: either we have a non-empty map in the first camp (containing all original values), a non-empty map in the second camp (containing all original values), or a split between two non-empty maps in either camp.

  3. Typeclass-polymorphic functions are made more general (or have more general variants provided) whenever possible. This means that functions like foldMapWithKey are written for all Semigroup m instead of only Monoid m, and traverseWithKey1 is provided to work for all Apply f instances (instead of only Applicative f instances).

    Foldable1 and Traversable1 instances are also provided, to provide foldMap1 and traverse1.

  4. Functions that can “potentially delete” (like alter and updateAt) return possibly-empty variants. However, alternatives are offered (whenever not already present) with variants that disallow deletion, allowing for guaranteed non-empty maps to be returned.

Contains non-empty versions for:

  • Map
  • IntMap
  • Set
  • IntSet
  • Sequence

A typeclass abstraction (in Data.Containers.NonEmpty) is provided to allow for easy conversions between non-empty and possibly-empty variants. Note that Tree, from Data.Tree, is already non-empty by construction.

Similar packages include:

  • non-empty-containers: Similar approach with similar data types, but API is limited to a few choice functions.
  • nonemptymap: Another similar approach, but is limited only to Map, and is also not a complete API port.
  • non-empty-sequence: Similar to nonemptymap, but for Seq. Also not a complete API port.
  • non-empty: Similar approach with similar data types, but is meant to be more general and work for a variety of more data types.
  • nonempty-alternative: Similar approach, but is instead a generalized data type for all Alternative instances.

Currently not implemented:

  • Extended merging functions. However, there aren’t too many benefits to be gained from lifting extended merging functions, because their emptiness/non-emptiness guarantees are difficult to statically conclude.
  • Strict variants of Map functions. This is something that I wouldn’t mind, and might add in the future. PR’s are welcomed!

Changes

Changelog

Version 0.3.4.x

  • 0.3.4.0: ToJSON and FromJSON instances (August 4, 2020)
  • 0.3.4.1: Ord instance to NESeq (@mitchelwrosen) (August 22, 2020)
  • 0.3.4.2: Compatibility with GHC 9 (@andremarianiello) (August 25, 2021)
  • 0.3.4.3: (August 25, 2021)
    • Fix intersperse for singleton non-empty sequences. (@eddiemundo)
    • Fix deleteMax for singleton containers.
  • 0.3.4.4: (September 25, 2021)
    • Alt instances for NEMap and NEIntMap
    • Invariant instance for NEMap, NEIntMap, and NESeq.

Version 0.3.3.0

December 3, 2019

https://github.com/mstksg/nonempty-containers/releases/tag/v0.3.3.0

  • Add overNonEmpty and onNonEmpty in Data.Containers.NonEmpty.

Version 0.3.1.0

October 21, 2019

https://github.com/mstksg/nonempty-containers/releases/tag/v0.3.3.0

  • Add HasNonEmpty instance for nonempty-vector
  • Changed splitLookup to use These instead of a tuple of Maybes.

Version 0.3.1.0

June 13, 2019

https://github.com/mstksg/nonempty-containers/releases/tag/v0.3.1.0

  • Add absurdNEMap to Data.Map.NonEmpty. This is the only type that would benefit from such a specialized function, whereas all other types would do just as well with absurd . fold1 :: Foldable1 f => f Void -> a.

Version 0.3.0.0

June 10, 2019

https://github.com/mstksg/nonempty-containers/releases/tag/v0.3.0.0

  • Switch back from data-or to these, due to changes in the organization of these that get rid of the high dependency footprint.

Version 0.2.0.0

May 14, 2019

https://github.com/mstksg/nonempty-containers/releases/tag/v0.2.0.0

  • (#2) Switch from these to data-or, for lighter dependency footprint. Much thanks to @fosskers for putting in the heavy work.

Version 0.1.1.0

December 8, 2018

https://github.com/mstksg/nonempty-containers/releases/tag/v0.1.1.0

Version 0.1.0.0

https://github.com/mstksg/nonempty-containers/releases/tag/v0.1.0.0

  • Initial release