Add NonEmptyMap and NonEmptySet to containers
Andreas Abel
andreas.abel at ifi.lmu.de
Fri Apr 19 06:48:39 UTC 2019
+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
>
More information about the Libraries
mailing list