Add NonEmptyMap and NonEmptySet to containers

Andreas Abel andreas.abel at
Fri Apr 19 06:48:39 UTC 2019


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

More information about the Libraries mailing list