Add NonEmptyMap and NonEmptySet to containers

Vladislav Zavialov vladislav at
Fri Apr 19 09:10:59 UTC 2019

NonEmptyMap and NonEmptySet are way more readable than NEMap and NESet, the latter read as “NEM ap” and “NES et”.

Bikeshedding aside, I’m in favor of the proposal.

- Vlad

> On 19 Apr 2019, at 09:48, Andreas Abel <andreas.abel at> wrote:
> +1
> The name of the structures should not class with Map and Set, thus, NEMap and NESet are good.  The alternative would be NonEmptyMap and NonEmptySet but this is a bit too much to write.
> We definitely should /not/ repeat the choice made for Data.List.NonEmpty.NonEmpty.  Using non-empty lists /always/ requires a type synonym, like
>  import qualified Data.List.NonEmpty as NEList
>  type NEList = NEList.NonEmpty
> which is quite ugly, and type synonyms are sometimes expanded in GHC error messages, which causes additional trouble.
> On 2019-04-19 06:27, chessai . wrote:
>> To be clear, I was only talking about module names and not implementation. NEMap/NESet don't sound so bad to me.
>> On Fri, Apr 19, 2019, 12:17 AM David Feuer <david.feuer at <mailto: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
>>    <mailto: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 <mailto: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 <mailto:Libraries at>
>>            _______________________________________________
>>            Libraries mailing list
>>            Libraries at <mailto:Libraries at>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at
> _______________________________________________
> Libraries mailing list
> Libraries at

More information about the Libraries mailing list