Add NonEmptyMap and NonEmptySet to containers

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
32 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Add NonEmptyMap and NonEmptySet to containers

John Ericson-2

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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Henning Thielemann

On Thu, 18 Apr 2019, John Cotton Ericson 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.

I have also my implementations:
https://hackage.haskell.org/package/non-empty-0.3.1/docs/Data-NonEmpty-Set.html
https://hackage.haskell.org/package/non-empty-0.3.1/docs/Data-NonEmpty-Map.html

Interesting to know, that the implementation in containers could already
provide this functionality with little changes.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

David Feuer
In reply to this post by John Ericson-2
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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

chessai .
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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

David Feuer
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 . <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]> 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 . <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

chessai .
In reply to this post by David Feuer
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 <[hidden email]> 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 . <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Henning Thielemann
In reply to this post by chessai .

On Fri, 19 Apr 2019, chessai . 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

+1 for these module names.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Andreas Abel
In reply to this post by chessai .
+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 <[hidden email]
> <mailto:[hidden email]>> 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 . <[hidden email]
>     <mailto:[hidden email]>> 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
>         <[hidden email] <mailto:[hidden email]>> 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
>             <[hidden email]> 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
>                 [hidden email] <mailto:[hidden email]>
>                 http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>             _______________________________________________
>             Libraries mailing list
>             [hidden email] <mailto:[hidden email]>
>             http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Vladislav Zavialov-2
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 <[hidden email]> 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 <[hidden email] <mailto:[hidden email]>> 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 . <[hidden email]
>>    <mailto:[hidden email]>> 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
>>        <[hidden email] <mailto:[hidden email]>> 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
>>            <[hidden email]> 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
>>                [hidden email] <mailto:[hidden email]>
>>                http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>            _______________________________________________
>>            Libraries mailing list
>>            [hidden email] <mailto:[hidden email]>
>>            http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Henning Thielemann

On Fri, 19 Apr 2019, Vladislav Zavialov wrote:

> NonEmptyMap and NonEmptySet are way more readable than NEMap and NESet,
> the latter read as “NEM ap” and “NES et”.

I also prefer the long names since they are more descriptive and you can
always define your own type synonym.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

David Feuer
In reply to this post by John Ericson-2
There are a few functions that need names and places. In addition to

    insert :: Ord a => a -> NESet a -> NESet a -- or whatever type name
    union :: Ord a => NESet a -> NESet a -> NESet a

we need

    insert?? :: Ord a => a -> Set a -> NESet a
    union?? :: Ord a => Set a -> NESet a -> NESet a

For maps, we probably need unions on both sides to take care of different biases, and also need to deal with unionWith.

Another question: we currently have

    powerSet :: Set a -> Set (Set a)

Should we change that to

    powerSet :: Set a -> NESet (Set a)

or add a new function for that (where and by what name)?

For power sets of nonempty sets, there are several options, the most fundamental of which is probably

    ??? :: NESet a -> NESet (NESet a)

Splitting functions for nonempty sets/maps can produce results of various shapes. In particular, spanAntitone and partition for nonempty sets will produce two sets, at least one of which is non-empty. Do we want something like

    partition :: (a -> Bool) -> NESet a
       -> Either (NESet a, Set a) (Set a, NESet a)

or should we stick with

    partition :: (a -> Bool) -> NESet a ->
      (Set a, Set a)

or offer both by different names?

On Thu, Apr 18, 2019, 7:15 PM John Cotton Ericson <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Oleg Grenrus
I’d like to see a package, which then could act as compat package, implementing these ideas. To my understanding `containers` exposes internals, so there shouldn’t be big technical challenges.

I’d like an API to be validated first. Maybe the packages mentioned in the original post are such, in that case I’d think twice before adding anything that’s not there.



On 19 Apr 2019, at 22.02, David Feuer <[hidden email]> wrote:

There are a few functions that need names and places. In addition to

    insert :: Ord a => a -> NESet a -> NESet a -- or whatever type name
    union :: Ord a => NESet a -> NESet a -> NESet a

we need

    insert?? :: Ord a => a -> Set a -> NESet a
    union?? :: Ord a => Set a -> NESet a -> NESet a

For maps, we probably need unions on both sides to take care of different biases, and also need to deal with unionWith.

Another question: we currently have

    powerSet :: Set a -> Set (Set a)

Should we change that to

    powerSet :: Set a -> NESet (Set a)

or add a new function for that (where and by what name)?

For power sets of nonempty sets, there are several options, the most fundamental of which is probably

    ??? :: NESet a -> NESet (NESet a)

Splitting functions for nonempty sets/maps can produce results of various shapes. In particular, spanAntitone and partition for nonempty sets will produce two sets, at least one of which is non-empty. Do we want something like

    partition :: (a -> Bool) -> NESet a
       -> Either (NESet a, Set a) (Set a, NESet a)

or should we stick with

    partition :: (a -> Bool) -> NESet a ->
      (Set a, Set a)

or offer both by different names?

On Thu, Apr 18, 2019, 7:15 PM John Cotton Ericson <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Oleg Grenrus
In reply to this post by David Feuer
Btw `partition` should return `These (NESet a) (NESet a)`: all match, all don’t match, or some match and some don’t.


As said, I’d think twice before changing that API. Yet, These is problematic type. (I’m all in to put it into `base`, but I won’t write a proposal).

On 19 Apr 2019, at 22.02, David Feuer <[hidden email]> wrote:

There are a few functions that need names and places. In addition to

    insert :: Ord a => a -> NESet a -> NESet a -- or whatever type name
    union :: Ord a => NESet a -> NESet a -> NESet a

we need

    insert?? :: Ord a => a -> Set a -> NESet a
    union?? :: Ord a => Set a -> NESet a -> NESet a

For maps, we probably need unions on both sides to take care of different biases, and also need to deal with unionWith.

Another question: we currently have

    powerSet :: Set a -> Set (Set a)

Should we change that to

    powerSet :: Set a -> NESet (Set a)

or add a new function for that (where and by what name)?

For power sets of nonempty sets, there are several options, the most fundamental of which is probably

    ??? :: NESet a -> NESet (NESet a)

Splitting functions for nonempty sets/maps can produce results of various shapes. In particular, spanAntitone and partition for nonempty sets will produce two sets, at least one of which is non-empty. Do we want something like

    partition :: (a -> Bool) -> NESet a
       -> Either (NESet a, Set a) (Set a, NESet a)

or should we stick with

    partition :: (a -> Bool) -> NESet a ->
      (Set a, Set a)

or offer both by different names?

On Thu, Apr 18, 2019, 7:15 PM John Cotton Ericson <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

David Feuer
In reply to this post by Oleg Grenrus
The internals aren't sufficient, at present, to do this quite the way we want. You're right that we should use the existing packages as guides.

On Sun, Apr 21, 2019, 3:46 PM Oleg Grenrus <[hidden email]> wrote:
I’d like to see a package, which then could act as compat package, implementing these ideas. To my understanding `containers` exposes internals, so there shouldn’t be big technical challenges.

I’d like an API to be validated first. Maybe the packages mentioned in the original post are such, in that case I’d think twice before adding anything that’s not there.



On 19 Apr 2019, at 22.02, David Feuer <[hidden email]> wrote:

There are a few functions that need names and places. In addition to

    insert :: Ord a => a -> NESet a -> NESet a -- or whatever type name
    union :: Ord a => NESet a -> NESet a -> NESet a

we need

    insert?? :: Ord a => a -> Set a -> NESet a
    union?? :: Ord a => Set a -> NESet a -> NESet a

For maps, we probably need unions on both sides to take care of different biases, and also need to deal with unionWith.

Another question: we currently have

    powerSet :: Set a -> Set (Set a)

Should we change that to

    powerSet :: Set a -> NESet (Set a)

or add a new function for that (where and by what name)?

For power sets of nonempty sets, there are several options, the most fundamental of which is probably

    ??? :: NESet a -> NESet (NESet a)

Splitting functions for nonempty sets/maps can produce results of various shapes. In particular, spanAntitone and partition for nonempty sets will produce two sets, at least one of which is non-empty. Do we want something like

    partition :: (a -> Bool) -> NESet a
       -> Either (NESet a, Set a) (Set a, NESet a)

or should we stick with

    partition :: (a -> Bool) -> NESet a ->
      (Set a, Set a)

or offer both by different names?

On Thu, Apr 18, 2019, 7:15 PM John Cotton Ericson <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Mario Blažević
In reply to this post by David Feuer
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
> <[hidden email]> 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
>     [hidden email] <mailto:[hidden email]>
>     http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Artyom Kazak-2
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ć <[hidden email]> 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

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Zemyla
As long as we're doing this, can we also add NonEmptySeq as well?

On Thu, Apr 25, 2019, 09:11 Artyom Kazak <[hidden email]> 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ć <[hidden email]> 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

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
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:
a fork of containers.
changes the types, to make sure UNPACK preserved the importance.
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 mailing list

_______________________________________________
Libraries mailing list
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

David Feuer
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 <[hidden email]> wrote:
As long as we're doing this, can we also add NonEmptySeq as well?

On Thu, Apr 25, 2019, 09:11 Artyom Kazak <[hidden email]> 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ć <[hidden email]> 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

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
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:
a fork of containers.
changes the types, to make sure UNPACK preserved the importance.
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 mailing list

_______________________________________________
Libraries mailing list
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add NonEmptyMap and NonEmptySet to containers

Mario Blažević
In reply to this post by Artyom Kazak-2
On 2019-04-25 10:11 a.m., Artyom Kazak 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.

        I don't believe that statement is true. Most maps I've seen around are
never deleted from; once they are constructed, they are mostly used for
lookups and an occasional update. It's irrelevant whether such a map is
imported as the empty or non-empty type, apart from a bit of type safety
and performance.

        (Speaking of which, what would be the type of deleteNE?)

>
> ...
> "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|.

        Nobody would be forcing you to use the module. And it's not obvious
that beginners would find MapNE, insertNE, unionNE, etc less confusing.


> 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.

        Type classes are just the mechanism to construct such an interface.
However all your arguments against a different import could be equally
applied against Filterable/Witherable, or against Foldable for that matter.


> On Apr 25 2019, at 2:49 pm, Mario Blažević <[hidden email]> 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
>         <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
12