Add NonEmptyMap and NonEmptySet to containers
Vladislav Zavialov
vladislav at serokell.io
Fri Apr 19 09:10:59 UTC 2019
NonEmptyMap and NonEmptySet are way more readable than NEMap and NESet, the latter read as “NEM ap” and “NES et”.
Bikeshedding aside, I’m in favor of the proposal.
- Vlad
> On 19 Apr 2019, at 09:48, Andreas Abel <andreas.abel at ifi.lmu.de> wrote:
>
> +1
>
> The name of the structures should not class with Map and Set, thus, NEMap and NESet are good. The alternative would be NonEmptyMap and NonEmptySet but this is a bit too much to write.
>
> We definitely should /not/ repeat the choice made for Data.List.NonEmpty.NonEmpty. Using non-empty lists /always/ requires a type synonym, like
>
> import qualified Data.List.NonEmpty as NEList
> type NEList = NEList.NonEmpty
>
> which is quite ugly, and type synonyms are sometimes expanded in GHC error messages, which causes additional trouble.
>
> On 2019-04-19 06:27, chessai . wrote:
>> To be clear, I was only talking about module names and not implementation. NEMap/NESet don't sound so bad to me.
>> On Fri, Apr 19, 2019, 12:17 AM David Feuer <david.feuer at gmail.com <mailto: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
>> <mailto: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 <mailto: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 <mailto:Libraries at haskell.org>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> _______________________________________________
>> 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
More information about the Libraries
mailing list