Module documentation for 0.3.4.5

• Data
  • Data.Containers
    • Data.Containers.NonEmpty
  • Data.IntMap
    • Data.IntMap.NonEmpty
      • Data.IntMap.NonEmpty.Internal
  • Data.IntSet
    • Data.IntSet.NonEmpty
      • Data.IntSet.NonEmpty.Internal
  • Data.Map
    • Data.Map.NonEmpty
      • Data.Map.NonEmpty.Internal
  • Data.Sequence
    • Data.Sequence.NonEmpty
      • Data.Sequence.NonEmpty.Internal
  • Data.Set
    • Data.Set.NonEmpty
      • Data.Set.NonEmpty.Internal

nonempty-containers

Efficient and optimized non-empty (by construction) versions of types fromcontainers. Inspired bynon-empty-containers library, exceptattempting a more faithful port (with under-the-hood optimizations) of the fullcontainers API. Also contains a convenient typeclass abstraction forconverting between non-empty and possibly-empty variants, as well as patternsynonym-based conversion methods.

Non-emptyby construction means that the data type is implemented using adata structure where it is structurally impossible to represent an emptycollection.

Unlike similar packages (see below), this package is defined to be adrop-in replacement for thecontainers API in most situations. More orless every single function is implemented with the same asymptotics andtypeclass constraints. An extensive test suite (with 457 total tests) isprovided to ensure that the behavior of functions are identical to theiroriginalcontainers counterparts.

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

1. Functions that might return empty results (likedelete,filter) returnpossibly-empty variants instead.

2. Functions that totally partition a non-empty collection (likepartition,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 originalmap is represented in the result), so, to reflect this,These isreturned instead:

   data These a b = This  a               | That    b               | These a bmapEither :: (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-emptymap in the first camp (containing all original values), a non-empty map inthe second camp (containing all original values), or a split between twonon-empty maps in either camp.

3. Typeclass-polymorphic functions are made more general (or have more generalvariants provided) whenever possible. This means that functions likefoldMapWithKey are written for allSemigroup m instead of onlyMonoid m, andtraverseWithKey1 is provided to work for allApply f instances(instead of onlyApplicative f instances).

   Foldable1 andTraversable1 instances are also provided, to providefoldMap1 andtraverse1.

4. Functions that can “potentially delete” (likealter andupdateAt)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 (inData.Containers.NonEmpty) is provided to allowfor easy conversions between non-empty and possibly-empty variants. Note thatTree, fromData.Tree, is already non-empty by construction.

Similar packages include:

• non-empty-containers: Similar approach with similar data types, but APIis limited to a few choice functions.
• nonemptymap: Another similar approach, but is limited only toMap,and is also not a complete API port.
• non-empty-sequence: Similar tononemptymap, but forSeq. Also nota complete API port.
• non-empty: Similar approach with similar data types, but is meant to bemore general and work for a variety of more data types.
• nonempty-alternative: Similar approach, but is instead a generalizeddata type for allAlternative instances.

Currently not implemented:

• Extended merging functions. However, there aren’t too many benefits to begained from lifting extended merging functions, because theiremptiness/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!

Changelog

Version 0.3.4.x

• 0.3.4.0:ToJSON andFromJSON instances (August 4, 2020)
• 0.3.4.1:Ord instance toNESeq (@mitchelwrosen) (August 22, 2020)
• 0.3.4.2: Compatibility with GHC 9 (@andremarianiello) (August 25, 2021)
• 0.3.4.3: (August 25, 2021)
  • Fixintersperse for singleton non-empty sequences. (@eddiemundo)
  • FixdeleteMax for singleton containers.
• 0.3.4.4: (September 25, 2021)
  • Alt instances forNEMap andNEIntMap
  • Invariant instance forNEMap,NEIntMap, andNESeq.
• 0.3.4.5: Future-proof against Prelude exportingfoldl' (@Bodgrim) (December 6, 2023)

Version 0.3.3.0

December 3, 2019

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

• AddoverNonEmpty andonNonEmpty inData.Containers.NonEmpty.

Version 0.3.1.0

October 21, 2019

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

• AddHasNonEmpty instance fornonempty-vector
• ChangedsplitLookup to useThese instead of a tuple ofMaybes.

Version 0.3.1.0

June 13, 2019

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

• AddabsurdNEMap toData.Map.NonEmpty. This is the only type that wouldbenefit from such a specialized function, whereas all other types would dojust as well withabsurd . 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 fromdata-or tothese, due to changes in the organizationofthese 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 fromthese todata-or, for lighter dependency footprint. Muchthanks 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

• Comonad instances added forMap k andIntMap, based onFaucelme’ssuggestion

Version 0.1.0.0

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

• Initial release