Add NonEmptyMap and NonEmptySet to containers

Thu Apr 25 15:26:14 UTC 2019

On 2019-04-25 10:11 a.m., Artyom Kazak wrote:
> I'm -1 on any kind of |Map = NEMap|.
> 
> An ordinary map and a non-empty map are semantically different. I 
> believe that if I non-empty maps were already in |containers|, I would 
> pretty much always care whether a |Map| I see in code is a 0-map or 1-map.

	I don't believe that statement is true. Most maps I've seen around are 
never deleted from; once they are constructed, they are mostly used for 
lookups and an occasional update. It's irrelevant whether such a map is 
imported as the empty or non-empty type, apart from a bit of type safety 
and performance.

	(Speaking of which, what would be the type of deleteNE?)

> 
> ...
> "why not both" is even worse. I still can't trust the |Map|, but now I 
> also have to learn and remember that two modules are the same. Speaking 
> from experience again – most people seem to be surprised by the fact 
> that |Data.Map.Lazy| and |Data.Map.Strict| export the same |Map| type. 
> The proposed module hierarchy would move |containers| to the top of my 
> "packages that confuse beginners" list, beating even |aeson|.

	Nobody would be forcing you to use the module. And it's not obvious 
that beginners would find MapNE, insertNE, unionNE, etc less confusing.


> As an aside, I wish we had a proper interface for container-like 
> structures, or at least a solution to name scoping. I really like the 
> way Rust does it, for instance, where certain functions can be 
> "attached" to a type – I'm hesitant to call them "methods" because Rust 
> is not an OOP language.

	Type classes are just the mechanism to construct such an interface. 
However all your arguments against a different import could be equally 
applied against Filterable/Witherable, or against Foldable for that matter.


> On Apr 25 2019, at 2:49 pm, Mario Blažević <mblazevic at stilo.com> wrote:
> 
>     On 2019-04-18 11:00 p.m., David Feuer 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?
> 
> 
>     There seems to be a consensus for Data.Map.NonEmpty.NEMap, with the
>     type and the functions slightly off the regular ones. This design would
>     make it easier to use regular and non-empty containers together, but it
>     be annoying for the use case of replacing all uses of an existing
>     regular container with a non-empty one. I'd rather change just the
>     import declaration than all occurrences of the type name and functions.
> 
>     I don't want to derail the implementation with bikeshedding, so I'm
>     just going to ask why not both? The library can both export the tweaked
>     names and add a module, say Data.NonEmpty.Map.Lazy, that exports the
>     type synonym Map = NEMap. It would also rename all the functions back to
>     their names from Data.Map.Lazy.
> 
> 
> 
>         On Thu, Apr 18, 2019, 7:15 PM John Cotton Ericson
>         <John.Ericson at obsidian.systems> wrote:
> 
>         In https://github.com/haskell/containers/issues/608 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
>         https://github.com/mstksg/nonempty-containers and
>         https://github.com/andrewthad/non-empty-containers 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:
>         https://github.com/obsidiansystems/dependent-map/tree/non-empty,
>         a fork of containers.
>         2. I made https://github.com/haskell/containers/pull/616 which just
>         changes the types, to make sure UNPACK preserved the importance.
>         3.
>         https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841
>         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
> 
>         _______________________________________________