Efficient and optimized nonempty (by construction) versions of types from
containers. Inspired by nonemptycontainers library, except
attempting a more faithful port (with underthehood optimizations) of the full
containers API. Also contains a convenient typeclass abstraction for
converting between nonempty and possiblyempty variants, as well as pattern
synonymbased conversion methods.
Nonempty 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
dropin 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
nonemptiness and emptiness as concepts, including:

Functions that might return empty results (like delete
, filter
) return
possiblyempty variants instead.

Functions that totally partition a nonempty 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 nonemptiness: either we have a nonempty
map in the first camp (containing all original values), a nonempty map in
the second camp (containing all original values), or a split between two
nonempty maps in either camp.

Typeclasspolymorphic 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
.

Functions that can “potentially delete” (like alter
and updateAt
)
return possiblyempty variants. However, alternatives are offered
(whenever not already present) with variants that disallow deletion,
allowing for guaranteed nonempty maps to be returned.
Contains nonempty versions for:
Map
IntMap
Set
IntSet
Sequence
A typeclass abstraction (in Data.Containers.NonEmpty) is provided to allow
for easy conversions between nonempty and possiblyempty variants. Note that
Tree
, from Data.Tree, is already nonempty by construction.
Similar packages include:
 nonemptycontainers: 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.
 nonemptysequence: Similar to nonemptymap, but for
Seq
. Also not
a complete API port.
 nonempty: Similar approach with similar data types, but is meant to be
more general and work for a variety of more data types.
 nonemptyalternative: 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/nonemptiness 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!