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.

Similarly, I prefer Int and Word instead of Int and Unsigned.Int. (Luckily that's already the case.)

We already have a precedent with Text and ByteString, where the lazy and the strict versions are only distinguished by the module prefix. In my experience, modules where both are used are pretty common, and I end up just introducing type LByteString = Lazy.ByteString in all my projects, because otherwise I need to scroll to the imports section whenever I need to know which flavor of bytestring is being used. (Or if I'm reading haddocks, I have to look at the link because Haddock hides module prefixes.)

"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.

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.
On Apr 25 2019, at 2:49 pm, Mario Blažević <mblazevic@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@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@haskell.org <mailto:Libraries@haskell.org>
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries