Add NonEmptyMap and NonEmptySet to containers

Thu Apr 25 15:36:42 UTC 2019

A Seq has either Empty, Single, or Deep. A NonEmptySeq would have just
Single or Deep.

On Thu, Apr 25, 2019, 09:55 David Feuer <david.feuer at gmail.com> wrote:

> 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/af2ec60f/attachment.html>