Add NonEmptyMap and NonEmptySet to containers

Thu Apr 25 14:54:50 UTC 2019

I don't see the benefit there, unless you see a way to work it into the
representation.

On Thu, Apr 25, 2019, 10:53 AM Zemyla <zemyla at gmail.com> wrote:

> 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
>>
> _______________________________________________
> 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/373e56ea/attachment.html>