Add NonEmptyMap and NonEmptySet to containers

David Feuer david.feuer at
Fri Apr 19 04:17:09 UTC 2019

Definitely sets as well.

Set (a, b) ~= Map a (NonEmpty.??Set b)

I'm leaning toward calling the types NEMap and NESet (or similar). Yes,
that's a bit disgusting. It would be prettier, perhaps, to just use the
names Map and Set, but that runs into a nasty implementation challenge with
mutual recursion. I don't want .hs-boot or fancy backpack tricks in
containers, and I don't want horribly awkward newtypes cluttering up the
implementation if I can avoid it.

On Fri, Apr 19, 2019, 12:08 AM chessai . <chessai1996 at> wrote:

> I'm also +1.
> Why not:
> Data.Map.NonEmpty
> Data.Map.NonEmpty.Lazy
> Data.Map.NonEmpty.Strict
> If sets are added as well:
> Data.Set.NonEmpty
> 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