Add NonEmptyMap and NonEmptySet to containers

David Feuer david.feuer at
Fri Apr 19 04:26:50 UTC 2019

Although ... since all the nonempty functions will need to be renamed,
maybe newtypes won't be unacceptably painful, relatively speaking....

On Fri, Apr 19, 2019, 12:17 AM David Feuer <david.feuer at> wrote:

> 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