Add NonEmptyMap and NonEmptySet to containers

[Mario Blažević]

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
> 
>     _______________________________________________
>     Libraries mailing list
>     Libraries at haskell.org <mailto:Libraries at haskell.org>
>     http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> 
> 
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>