generalize type of Data.Set.unions from List to Foldable

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

generalize type of Data.Set.unions from List to Foldable

Johannes Waldmann-2
Dear Libraries,


I propose this change for containers:

have:  unions ::               [ Set a ] -> Set a
want:  unions :: Foldable f => f (Set a) -> Set a

and similar for unions in IntSet, Map, IntMap.

Since this affects the public API,
contributor guidelines require to go through this mailing list.

See https://github.com/haskell/containers/issues/520


NB: the only other places in Data.Set (etc.)
where a list occurs in an argument position
are the  from*List[With]  functions.


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

Re: generalize type of Data.Set.unions from List to Foldable

Henning Thielemann

On Sat, 3 Feb 2018, Johannes Waldmann wrote:

> I propose this change for containers:
>
> have:  unions ::               [ Set a ] -> Set a
> want:  unions :: Foldable f => f (Set a) -> Set a

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

Re: generalize type of Data.Set.unions from List to Foldable

David Feuer
It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:

1. Generalize as proposed, or
2. Deprecate and remove.

I'm currently somewhat in favor of the second option.

On Feb 3, 2018 9:42 AM, "Henning Thielemann" <[hidden email]> wrote:

On Sat, 3 Feb 2018, Johannes Waldmann wrote:

I propose this change for containers:

have:  unions ::               [ Set a ] -> Set a
want:  unions :: Foldable f => f (Set a) -> Set a

That's Foldable.fold.

_______________________________________________
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: generalize type of Data.Set.unions from List to Foldable

Johannes Waldmann-2

> 2. Deprecate and remove.

Removal is good. (Less code, less errors ...)

But the following cannot be obtained via Foldable.fold ?

unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k a

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

Re: generalize type of Data.Set.unions from List to Foldable

David Feuer
No, but it can still be written quite easily:

  unionsWith f = foldl' (unionWith f) M.empty

Is that really hard enough to merit the API clutter? Maybe, but I doubt it.

On Sun, Feb 4, 2018 at 2:47 PM, Johannes Waldmann
<[hidden email]> wrote:

>
>> 2. Deprecate and remove.
>
> Removal is good. (Less code, less errors ...)
>
> But the following cannot be obtained via Foldable.fold ?
>
> unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k a
>
> - J.W.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalize type of Data.Set.unions from List to Foldable

Joachim Breitner-2
In reply to this post by David Feuer
Hi,

Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
> It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:
>
> 1. Generalize as proposed, or
> 2. Deprecate and remove.
>
> I'm currently somewhat in favor of the second option.

please don’t remove!

…is first reaction. Now I just have to rationalize my gut feeling…

I like the readability of it in code, it is more descriptive. It is an
important analogue to unionsWith. If we remove unions because of fold,
shouldn’t we also remove union because of (<>)?


Cheers,
Joachim

--
Joachim Breitner
  [hidden email]
  http://www.joachim-breitner.de/

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

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: generalize type of Data.Set.unions from List to Foldable

Henning Thielemann

On Sun, 4 Feb 2018, Joachim Breitner wrote:

> Hi,
>
> Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
>> It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:
>>
>> 1. Generalize as proposed, or
>> 2. Deprecate and remove.
>>
>> I'm currently somewhat in favor of the second option.
>
> please don’t remove!
>
> …is first reaction. Now I just have to rationalize my gut feeling…
>
> I like the readability of it in code, it is more descriptive.
Right.

As always, I see no sense in only preserving a most general version of a
function. Code that consists of nested fold, fmap, (<>) is practically
unreadable. Only use that if you really want generic code.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalize type of Data.Set.unions from List to Foldable

David Feuer
In reply to this post by Joachim Breitner-2
We shouldn't remove it because of fold. We should (perhaps) remove it
because of foldl'. I don't really think unions or unionsWith should
ever have existed. I certainly don't think we should remove union,
because Set offers more than one reasonable Semigroup; <> isn't a very
clear spelling of union.

On Sun, Feb 4, 2018 at 3:09 PM, Joachim Breitner
<[hidden email]> wrote:

> Hi,
>
> Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
>> It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:
>>
>> 1. Generalize as proposed, or
>> 2. Deprecate and remove.
>>
>> I'm currently somewhat in favor of the second option.
>
> please don’t remove!
>
> …is first reaction. Now I just have to rationalize my gut feeling…
>
> I like the readability of it in code, it is more descriptive. It is an
> important analogue to unionsWith. If we remove unions because of fold,
> shouldn’t we also remove union because of (<>)?
>
>
> Cheers,
> Joachim
>
> --
> Joachim Breitner
>   [hidden email]
>   http://www.joachim-breitner.de/
>
> _______________________________________________
> 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: generalize type of Data.Set.unions from List to Foldable

David Feuer
In reply to this post by Henning Thielemann
Anyone but the newest beginner who needs the functionality of unions
or (for Data.Map) unionsWith should be able to write it themselves
with barely a second thought, using foldl'. The newest beginner might
find this a good opportunity to learn about foldl'. In my personal
opinion, the bar is set by Data.Sequence.intersperse; users *could*
write their own efficient version, but I don't expect a user to
necessarily come up with

  intersperse :: a -> Seq a -> Seq a
  intersperse y xs = case viewl xs of
    EmptyL -> empty
    p :< ps -> p <| (ps <**> (const y <| singleton id))

at the drop of a hat.

On Sun, Feb 4, 2018 at 3:17 PM, Henning Thielemann
<[hidden email]> wrote:

>
> On Sun, 4 Feb 2018, Joachim Breitner wrote:
>
>> Hi,
>>
>> Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
>>>
>>> It is fold, although fold is not so great for lists in this context. It's
>>> also foldl' union Set.empty, which is better for lists, and probably also
>>> for balanced trees. I initially thought that we should surely generalize,
>>> but now another alternative comes to mind: remove. As a containers
>>> maintainer, I believe we should either:
>>>
>>> 1. Generalize as proposed, or
>>> 2. Deprecate and remove.
>>>
>>> I'm currently somewhat in favor of the second option.
>>
>>
>> please don’t remove!
>>
>> …is first reaction. Now I just have to rationalize my gut feeling…
>>
>> I like the readability of it in code, it is more descriptive.
>
>
> Right.
>
> As always, I see no sense in only preserving a most general version of a
> function. Code that consists of nested fold, fmap, (<>) is practically
> unreadable. Only use that if you really want generic code.
> _______________________________________________
> 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: generalize type of Data.Set.unions from List to Foldable

Evan Laforge
In reply to this post by Joachim Breitner-2
If it were removed I would just move the definition to my local
Util.Map and keep using it. So, speaking for myself only, the result
is the same, just with a less convenient name, and a lengthy period of
deprecation in between.

Is there some kind of general agreement about how important a change
has to be to be worth breaking things? Clearly people are not willing
to commit to Java style never break things, but there is a threshold
somewhere.  If there's no general consensus, then at least this change
is below my personal threshold.

I'd put buggy, or shown to be error prone in practice, or leads to
significant or error prone boilerplate on the "break" side, and
redundant or not general on the "do not break" side.  #ifdef is error
prone boilerplate too.

On Feb 4, 2018 12:11 PM, "Joachim Breitner" <[hidden email]> wrote:

>
> Hi,
>
> Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
> > It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:
> >
> > 1. Generalize as proposed, or
> > 2. Deprecate and remove.
> >
> > I'm currently somewhat in favor of the second option.
>
> please don’t remove!
>
> …is first reaction. Now I just have to rationalize my gut feeling…
>
> I like the readability of it in code, it is more descriptive. It is an
> important analogue to unionsWith. If we remove unions because of fold,
> shouldn’t we also remove union because of (<>)?
>
>
> Cheers,
> Joachim
>
> --
> Joachim Breitner
>   [hidden email]
>   http://www.joachim-breitner.de/
>
> _______________________________________________
> 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: generalize type of Data.Set.unions from List to Foldable

Jan-Willem Maessen
In reply to this post by Joachim Breitner-2
The biggest argument in favor of unions and unionsWith is that, while they're easy to write, they're also very easy to write wrong – for example by using fold instead of foldl' as described rather well in the conversation so far.  When I use a function like unions I expect to get an implementation better than the one I'd come up with on my own at the spur of the moment, and deciding what strictness is more efficient in this case is actually a little bit subtle.

-Jan-Willem Maessen

On Sun, Feb 4, 2018 at 3:09 PM, Joachim Breitner <[hidden email]> wrote:
Hi,

Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
> It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:
>
> 1. Generalize as proposed, or
> 2. Deprecate and remove.
>
> I'm currently somewhat in favor of the second option.

please don’t remove!

…is first reaction. Now I just have to rationalize my gut feeling…

I like the readability of it in code, it is more descriptive. It is an
important analogue to unionsWith. If we remove unions because of fold,
shouldn’t we also remove union because of (<>)?


Cheers,
Joachim

--
Joachim Breitner
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
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: generalize type of Data.Set.unions from List to Foldable

Oliver Charles-3
unions also describes intent clearly. My intention is to take the union of a collection of sets. That might well correspond with a fold, but that's an implementation detail - and not one that I particularly care about. On top of that, when people read my code, I want them to understand that I intend to take the unions of a collection of sets, rather than having them figure out what it is I'm doing by using foldl.

I don't really see the harm in keeping unions, and I don't see the advantage in removing it. If we're arguing that unions is so simple to write, then the argument that deleting code will improve maintainability doesn't hold - because apparently it's so simple we're not going to introduce bugs in containers. If you don't agree with that reasoning, then apparently unions is sufficiently complicated to write that it should be in the containers library.

On Mon, Feb 5, 2018 at 2:46 PM, Jan-Willem Maessen <[hidden email]> wrote:
The biggest argument in favor of unions and unionsWith is that, while they're easy to write, they're also very easy to write wrong – for example by using fold instead of foldl' as described rather well in the conversation so far.  When I use a function like unions I expect to get an implementation better than the one I'd come up with on my own at the spur of the moment, and deciding what strictness is more efficient in this case is actually a little bit subtle.

-Jan-Willem Maessen

On Sun, Feb 4, 2018 at 3:09 PM, Joachim Breitner <[hidden email]> wrote:
Hi,

Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
> It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:
>
> 1. Generalize as proposed, or
> 2. Deprecate and remove.
>
> I'm currently somewhat in favor of the second option.

please don’t remove!

…is first reaction. Now I just have to rationalize my gut feeling…

I like the readability of it in code, it is more descriptive. It is an
important analogue to unionsWith. If we remove unions because of fold,
shouldn’t we also remove union because of (<>)?


Cheers,
Joachim

--
Joachim Breitner
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
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: generalize type of Data.Set.unions from List to Foldable

David Feuer
I'm not concerned about the maintenance cost. I'm more concerned about the size of the API. People tend to get lost in the sea of functions in containers. But it sounds like lots of people are attached to unions, so what do y'all think about generalizing its type?

On Feb 5, 2018 9:52 AM, "Oliver Charles" <[hidden email]> wrote:
unions also describes intent clearly. My intention is to take the union of a collection of sets. That might well correspond with a fold, but that's an implementation detail - and not one that I particularly care about. On top of that, when people read my code, I want them to understand that I intend to take the unions of a collection of sets, rather than having them figure out what it is I'm doing by using foldl.

I don't really see the harm in keeping unions, and I don't see the advantage in removing it. If we're arguing that unions is so simple to write, then the argument that deleting code will improve maintainability doesn't hold - because apparently it's so simple we're not going to introduce bugs in containers. If you don't agree with that reasoning, then apparently unions is sufficiently complicated to write that it should be in the containers library.

On Mon, Feb 5, 2018 at 2:46 PM, Jan-Willem Maessen <[hidden email]> wrote:
The biggest argument in favor of unions and unionsWith is that, while they're easy to write, they're also very easy to write wrong – for example by using fold instead of foldl' as described rather well in the conversation so far.  When I use a function like unions I expect to get an implementation better than the one I'd come up with on my own at the spur of the moment, and deciding what strictness is more efficient in this case is actually a little bit subtle.

-Jan-Willem Maessen

On Sun, Feb 4, 2018 at 3:09 PM, Joachim Breitner <[hidden email]> wrote:
Hi,

Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
> It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:
>
> 1. Generalize as proposed, or
> 2. Deprecate and remove.
>
> I'm currently somewhat in favor of the second option.

please don’t remove!

…is first reaction. Now I just have to rationalize my gut feeling…

I like the readability of it in code, it is more descriptive. It is an
important analogue to unionsWith. If we remove unions because of fold,
shouldn’t we also remove union because of (<>)?


Cheers,
Joachim

--
Joachim Breitner
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
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


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

Re: generalize type of Data.Set.unions from List to Foldable

Oliver Charles-3
Oh, the comment about maintenance cost wasn't a response directly to you, just that it had been mentioned in this thread.

I'm ok with generalising unions to work over any Foldable.

On Mon, Feb 5, 2018 at 2:56 PM, David Feuer <[hidden email]> wrote:
I'm not concerned about the maintenance cost. I'm more concerned about the size of the API. People tend to get lost in the sea of functions in containers. But it sounds like lots of people are attached to unions, so what do y'all think about generalizing its type?

On Feb 5, 2018 9:52 AM, "Oliver Charles" <[hidden email]> wrote:
unions also describes intent clearly. My intention is to take the union of a collection of sets. That might well correspond with a fold, but that's an implementation detail - and not one that I particularly care about. On top of that, when people read my code, I want them to understand that I intend to take the unions of a collection of sets, rather than having them figure out what it is I'm doing by using foldl.

I don't really see the harm in keeping unions, and I don't see the advantage in removing it. If we're arguing that unions is so simple to write, then the argument that deleting code will improve maintainability doesn't hold - because apparently it's so simple we're not going to introduce bugs in containers. If you don't agree with that reasoning, then apparently unions is sufficiently complicated to write that it should be in the containers library.

On Mon, Feb 5, 2018 at 2:46 PM, Jan-Willem Maessen <[hidden email]> wrote:
The biggest argument in favor of unions and unionsWith is that, while they're easy to write, they're also very easy to write wrong – for example by using fold instead of foldl' as described rather well in the conversation so far.  When I use a function like unions I expect to get an implementation better than the one I'd come up with on my own at the spur of the moment, and deciding what strictness is more efficient in this case is actually a little bit subtle.

-Jan-Willem Maessen

On Sun, Feb 4, 2018 at 3:09 PM, Joachim Breitner <[hidden email]> wrote:
Hi,

Am Samstag, den 03.02.2018, 20:44 -0500 schrieb David Feuer:
> It is fold, although fold is not so great for lists in this context. It's also foldl' union Set.empty, which is better for lists, and probably also for balanced trees. I initially thought that we should surely generalize, but now another alternative comes to mind: remove. As a containers maintainer, I believe we should either:
>
> 1. Generalize as proposed, or
> 2. Deprecate and remove.
>
> I'm currently somewhat in favor of the second option.

please don’t remove!

…is first reaction. Now I just have to rationalize my gut feeling…

I like the readability of it in code, it is more descriptive. It is an
important analogue to unionsWith. If we remove unions because of fold,
shouldn’t we also remove union because of (<>)?


Cheers,
Joachim

--
Joachim Breitner
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
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



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