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:
Thanks,
John