Add NonEmptyMap and NonEmptySet to containers

Thu Apr 25 14:52:40 UTC 2019

As long as we're doing this, can we also add NonEmptySeq as well?

On Thu, Apr 25, 2019, 09:11 Artyom Kazak <yom at artyom.me> 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.
>
> 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 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
>
> _______________________________________________
> 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
>
>
> _______________________________________________
> Libraries mailing list
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20190425/9c63756b/attachment.html>