Add NonEmptyMap and NonEmptySet to containers

[John Cotton Ericson]

In https://github.com/haskell/containers/issues/608 I proposed adding 
non-empty variants of Map and Set, analogous to Data.List.NonEmpty for 
List, to containers. semigroupoids demonstrates the many uses and 
structure of non-empty containers in general, and libraries such as 
https://github.com/mstksg/nonempty-containers and 
https://github.com/andrewthad/non-empty-containers demonstrate the 
interest in non-empty maps and sets in particular. My favorite use-case 
is that they're needed to "curry" containers: for example, |Map (k0, k1) 
v| is isomorphic not to |Map k0 (Map k1 v)| but to |Map k0 (NonEmptyMap 
k1 v)|. I like this use-case because it comes from the containers 
themselves.

Importantly, there's no good way to do this outside of containers; doing 
so leads to imbalancing / extra indirection, or massive code 
duplication. If one wraps the container was an extra value like 
Data.List.NonEmpty, one's left with an unavoidable extra 
indirection/imbalance. One can rectify this by copying and modifying the 
implementation of containers, but that's hardly maintainable; even as 
though the algorithms are the same, enough lines are touched that 
merging upstream containers is nigh impossible.

On the other hand, the non-empty containers can be elegantly and 
sufficiently implemented alongside their originals by taking the Bin 
constructor and breaking it out into it's own type, mutually recursive 
with the original. This avoids the indirection/imbalancing and code 
duplication problems: the algorithms work exactly as before creating the 
same trees (remember the UNPACK), and no code duplicated since the 
functions become mutually recursive matching the types.

To briefly summarize the thread:

 1. I proposed the issue after performing this same refactor on the
    dependent-map package:
    https://github.com/obsidiansystems/dependent-map/tree/non-empty, a
    fork of containers.
 2. I made https://github.com/haskell/containers/pull/616 which just
    changes the types, to make sure UNPACK preserved the importance.
 3. https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841
    the benchmarks showed rather than degrading performance, PR 616
    actually /improved/ it.

  If there is preliminary consensus, I'll make a second PR on top which 
generalizes the functions like on my dependent-map branch.

Thanks,

John

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20190418/5eef88a0/attachment.html>