Add NonEmptyMap and NonEmptySet to containers

chessai . chessai1996 at
Fri Apr 19 04:08:06 UTC 2019

I'm also +1.

Why not:


If sets are added as well:


On Thu, Apr 18, 2019, 11:01 PM David Feuer <david.feuer at> wrote:

> I'm in favor of the proposal. I find the isomorphism between Map (a,b) v
> and Map a (NonemptyMap b v) very pleasant. The fact that others have
> written less-performant implementations of this idea is rather convincing.
> The fact that doing this removes partial matches in the implementation is
> nice. And I'll take performance improvements where I can get them. The main
> question is the proper name of the type. Just Data.Map.Nonempty.Map, or
> .NonemptyMap? Should the empty be capitalized?
> On Thu, Apr 18, 2019, 7:15 PM John Cotton Ericson
> <John.Ericson at> wrote:
>> In 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
>> and
>> 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:
>>, a
>>    fork of containers.
>>    2. I made which just
>>    changes the types, to make sure UNPACK preserved the importance.
>>    3.
>>    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
>> _______________________________________________
>> Libraries mailing list
>> Libraries at
> _______________________________________________
> Libraries mailing list
> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list