Add NonEmptyMap and NonEmptySet to containers

[David Feuer]

Although ... since all the nonempty functions will need to be renamed,
maybe newtypes won't be unacceptably painful, relatively speaking....

On Fri, Apr 19, 2019, 12:17 AM David Feuer <david.feuer at gmail.com> wrote:

> Definitely sets as well.
>
> Set (a, b) ~= Map a (NonEmpty.??Set b)
>
> I'm leaning toward calling the types NEMap and NESet (or similar). Yes,
> that's a bit disgusting. It would be prettier, perhaps, to just use the
> names Map and Set, but that runs into a nasty implementation challenge with
> mutual recursion. I don't want .hs-boot or fancy backpack tricks in
> containers, and I don't want horribly awkward newtypes cluttering up the
> implementation if I can avoid it.
>
> On Fri, Apr 19, 2019, 12:08 AM chessai . <chessai1996 at gmail.com> wrote:
>
>> I'm also +1.
>>
>> Why not:
>>
>> Data.Map.NonEmpty
>> Data.Map.NonEmpty.Lazy
>> Data.Map.NonEmpty.Strict
>>
>> If sets are added as well:
>>
>> Data.Set.NonEmpty
>>
>> On Thu, Apr 18, 2019, 11:01 PM David Feuer <david.feuer at gmail.com> 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?
>>>
>>> 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
>>>> 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/20190419/4969cbcd/attachment.html>