Bifoldable instance for Map

classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

Bifoldable instance for Map

Joseph C. Sible
I'd like to propose a change to the containers package: adding a
Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
no obvious problems were brought up. I submitted a PR implementing it
[2]. This seems like an obvious and straightforward instance to me.
Thoughts?

Joseph C. Sible

[1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
[2]: https://github.com/haskell/containers/pull/714
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bifoldable instance for Map

David Feuer
This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.

On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
I'd like to propose a change to the containers package: adding a
Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
no obvious problems were brought up. I submitted a PR implementing it
[2]. This seems like an obvious and straightforward instance to me.
Thoughts?

Joseph C. Sible

[1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
[2]: https://github.com/haskell/containers/pull/714
_______________________________________________
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: Bifoldable instance for Map

David Feuer
I would go as far as to say we don't need to continue the proposal process here. We're doing it.

On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.

On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
I'd like to propose a change to the containers package: adding a
Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
no obvious problems were brought up. I submitted a PR implementing it
[2]. This seems like an obvious and straightforward instance to me.
Thoughts?

Joseph C. Sible

[1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
[2]: https://github.com/haskell/containers/pull/714
_______________________________________________
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: Bifoldable instance for Map

Joseph C. Sible
In reply to this post by David Feuer
That one is indeed missing too. I'll start on a PR for HashMap shortly
after the one for Map lands.

On Mon, Apr 13, 2020 at 9:44 PM David Feuer <[hidden email]> wrote:

>
> This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.
>
> On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
>>
>> I'd like to propose a change to the containers package: adding a
>> Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
>> no obvious problems were brought up. I submitted a PR implementing it
>> [2]. This seems like an obvious and straightforward instance to me.
>> Thoughts?
>>
>> Joseph C. Sible
>>
>> [1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
>> [2]: https://github.com/haskell/containers/pull/714
>> _______________________________________________
>> 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: Bifoldable instance for Map

David Feuer
In reply to this post by David Feuer
Let me take that back. I forgot how weird Bifoldable and Bitraversable are for product types and product-like types. Is this instance actually useful for anything, or is it mostly confusing?

On Mon, Apr 13, 2020, 9:46 PM David Feuer <[hidden email]> wrote:
I would go as far as to say we don't need to continue the proposal process here. We're doing it.

On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.

On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
I'd like to propose a change to the containers package: adding a
Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
no obvious problems were brought up. I submitted a PR implementing it
[2]. This seems like an obvious and straightforward instance to me.
Thoughts?

Joseph C. Sible

[1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
[2]: https://github.com/haskell/containers/pull/714
_______________________________________________
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: Bifoldable instance for Map

Joseph C. Sible
I'll admit I don't have a strong use case for this. I was just looking
at instances and noticed that these seemed to be a weird omission,
since there was an obvious definition. But I also don't think it's
confusing at all. Since (,), Set, and HashSet are Foldable, and (,)
and (,,) x are Bifoldable, it seems only logical to have Map and
HashMap be Bifoldable too. What exactly would be confusing about any
of these?

Joseph C. Sible

On Sat, May 30, 2020 at 8:33 PM David Feuer <[hidden email]> wrote:

>
> Let me take that back. I forgot how weird Bifoldable and Bitraversable are for product types and product-like types. Is this instance actually useful for anything, or is it mostly confusing?
>
> On Mon, Apr 13, 2020, 9:46 PM David Feuer <[hidden email]> wrote:
>>
>> I would go as far as to say we don't need to continue the proposal process here. We're doing it.
>>
>> On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
>>>
>>> This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.
>>>
>>> On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
>>>>
>>>> I'd like to propose a change to the containers package: adding a
>>>> Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
>>>> no obvious problems were brought up. I submitted a PR implementing it
>>>> [2]. This seems like an obvious and straightforward instance to me.
>>>> Thoughts?
>>>>
>>>> Joseph C. Sible
>>>>
>>>> [1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
>>>> [2]: https://github.com/haskell/containers/pull/714
>>>> _______________________________________________
>>>> 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: Bifoldable instance for Map

George Wilson
If you have a non-commutative monoid, the result could easily be
different than you expect. eg. if you think it would do all keys and
then all values, rather than interleaving (which is I assume the most
efficient to implement).
Despite that I'm still +1 on this.

On Sun, 31 May 2020 at 14:59, Joseph C. Sible <[hidden email]> wrote:

>
> I'll admit I don't have a strong use case for this. I was just looking
> at instances and noticed that these seemed to be a weird omission,
> since there was an obvious definition. But I also don't think it's
> confusing at all. Since (,), Set, and HashSet are Foldable, and (,)
> and (,,) x are Bifoldable, it seems only logical to have Map and
> HashMap be Bifoldable too. What exactly would be confusing about any
> of these?
>
> Joseph C. Sible
>
> On Sat, May 30, 2020 at 8:33 PM David Feuer <[hidden email]> wrote:
> >
> > Let me take that back. I forgot how weird Bifoldable and Bitraversable are for product types and product-like types. Is this instance actually useful for anything, or is it mostly confusing?
> >
> > On Mon, Apr 13, 2020, 9:46 PM David Feuer <[hidden email]> wrote:
> >>
> >> I would go as far as to say we don't need to continue the proposal process here. We're doing it.
> >>
> >> On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
> >>>
> >>> This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.
> >>>
> >>> On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
> >>>>
> >>>> I'd like to propose a change to the containers package: adding a
> >>>> Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
> >>>> no obvious problems were brought up. I submitted a PR implementing it
> >>>> [2]. This seems like an obvious and straightforward instance to me.
> >>>> Thoughts?
> >>>>
> >>>> Joseph C. Sible
> >>>>
> >>>> [1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
> >>>> [2]: https://github.com/haskell/containers/pull/714
> >>>> _______________________________________________
> >>>> 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: Bifoldable instance for Map

Andreas Abel
Do we have any need for Bifoldable?  We have

   foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
   foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a

These functions seem to give more control of how the fold happens.

And if we'd want Bifoldable, shouldn't the Bifoldable instance be
implemented in terms of just foldrWithKey?  Why have a recursive
implementation?

Personally, I consider Bifoldable a fringe class, as I would hope that
in general with fusion, I can just go via bimap and ordinary Foldable
without much penalty.

On 2020-05-31 07:20, George Wilson wrote:

> If you have a non-commutative monoid, the result could easily be
> different than you expect. eg. if you think it would do all keys and
> then all values, rather than interleaving (which is I assume the most
> efficient to implement).
> Despite that I'm still +1 on this.
>
> On Sun, 31 May 2020 at 14:59, Joseph C. Sible <[hidden email]> wrote:
>>
>> I'll admit I don't have a strong use case for this. I was just looking
>> at instances and noticed that these seemed to be a weird omission,
>> since there was an obvious definition. But I also don't think it's
>> confusing at all. Since (,), Set, and HashSet are Foldable, and (,)
>> and (,,) x are Bifoldable, it seems only logical to have Map and
>> HashMap be Bifoldable too. What exactly would be confusing about any
>> of these?
>>
>> Joseph C. Sible
>>
>> On Sat, May 30, 2020 at 8:33 PM David Feuer <[hidden email]> wrote:
>>>
>>> Let me take that back. I forgot how weird Bifoldable and Bitraversable are for product types and product-like types. Is this instance actually useful for anything, or is it mostly confusing?
>>>
>>> On Mon, Apr 13, 2020, 9:46 PM David Feuer <[hidden email]> wrote:
>>>>
>>>> I would go as far as to say we don't need to continue the proposal process here. We're doing it.
>>>>
>>>> On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
>>>>>
>>>>> This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.
>>>>>
>>>>> On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
>>>>>>
>>>>>> I'd like to propose a change to the containers package: adding a
>>>>>> Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
>>>>>> no obvious problems were brought up. I submitted a PR implementing it
>>>>>> [2]. This seems like an obvious and straightforward instance to me.
>>>>>> Thoughts?
>>>>>>
>>>>>> Joseph C. Sible
>>>>>>
>>>>>> [1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
>>>>>> [2]: https://github.com/haskell/containers/pull/714
>>>>>> _______________________________________________
>>>>>> 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: Bifoldable instance for Map

Joseph C. Sible
I don't find this argument convincing. We have Functor, Foldable, and
Traversable instances even though mapWithKey, foldrWithKey, and
traverseWithKey give more control than they do. We have a Semigroup
instance even though unionWith and unionWithKey give more control than
it does.

As for the implementation, I'd be fine with changing it to be in terms
of foldrWithKey. I just care that we have this instance somehow.

Joseph C. Sible

On Sun, May 31, 2020 at 6:23 AM Andreas Abel <[hidden email]> wrote:

>
> Do we have any need for Bifoldable?  We have
>
>    foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
>    foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a
>
> These functions seem to give more control of how the fold happens.
>
> And if we'd want Bifoldable, shouldn't the Bifoldable instance be
> implemented in terms of just foldrWithKey?  Why have a recursive
> implementation?
>
> Personally, I consider Bifoldable a fringe class, as I would hope that
> in general with fusion, I can just go via bimap and ordinary Foldable
> without much penalty.
>
> On 2020-05-31 07:20, George Wilson wrote:
> > If you have a non-commutative monoid, the result could easily be
> > different than you expect. eg. if you think it would do all keys and
> > then all values, rather than interleaving (which is I assume the most
> > efficient to implement).
> > Despite that I'm still +1 on this.
> >
> > On Sun, 31 May 2020 at 14:59, Joseph C. Sible <[hidden email]> wrote:
> >>
> >> I'll admit I don't have a strong use case for this. I was just looking
> >> at instances and noticed that these seemed to be a weird omission,
> >> since there was an obvious definition. But I also don't think it's
> >> confusing at all. Since (,), Set, and HashSet are Foldable, and (,)
> >> and (,,) x are Bifoldable, it seems only logical to have Map and
> >> HashMap be Bifoldable too. What exactly would be confusing about any
> >> of these?
> >>
> >> Joseph C. Sible
> >>
> >> On Sat, May 30, 2020 at 8:33 PM David Feuer <[hidden email]> wrote:
> >>>
> >>> Let me take that back. I forgot how weird Bifoldable and Bitraversable are for product types and product-like types. Is this instance actually useful for anything, or is it mostly confusing?
> >>>
> >>> On Mon, Apr 13, 2020, 9:46 PM David Feuer <[hidden email]> wrote:
> >>>>
> >>>> I would go as far as to say we don't need to continue the proposal process here. We're doing it.
> >>>>
> >>>> On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
> >>>>>
> >>>>> This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.
> >>>>>
> >>>>> On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
> >>>>>>
> >>>>>> I'd like to propose a change to the containers package: adding a
> >>>>>> Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
> >>>>>> no obvious problems were brought up. I submitted a PR implementing it
> >>>>>> [2]. This seems like an obvious and straightforward instance to me.
> >>>>>> Thoughts?
> >>>>>>
> >>>>>> Joseph C. Sible
> >>>>>>
> >>>>>> [1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
> >>>>>> [2]: https://github.com/haskell/containers/pull/714
> >>>>>> _______________________________________________
> >>>>>> 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
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bifoldable instance for Map

Andreas Abel
 > We have Functor, Foldable, and Traversable instances

Yes, and good so, since I use these type classes every day.  Haven't
ever used Bifoldable, though.  This is why I question the need.

In general, I am a proponent of fat libraries, thus, I am not strongly
against such an addition, especially if it is only a light-weight
overlay over foldrWithKey.

I guess since Bifoldable is in base already (wasn't aware of this), the
ship has already sailed on discussing its wide-spread usability.  I
remain unconvinced though.

What weights in for me is that Map does not have sensible Bifunctor or
Bitraversable instances (since manipulating the keys does not preserve
the tree structure in general).  Thus, we cannot make the chord
(Bi)functor/(Bi)foldable/(Bi)traversable complete.

My take would be to add Bifoldable only on public demand.
But let's hear other opinions as well.

--Andreas


On 2020-05-31 18:49, Joseph C. Sible wrote:

> I don't find this argument convincing. We have Functor, Foldable, and
> Traversable instances even though mapWithKey, foldrWithKey, and
> traverseWithKey give more control than they do. We have a Semigroup
> instance even though unionWith and unionWithKey give more control than
> it does.
>
> As for the implementation, I'd be fine with changing it to be in terms
> of foldrWithKey. I just care that we have this instance somehow.
>
> Joseph C. Sible
>
> On Sun, May 31, 2020 at 6:23 AM Andreas Abel <[hidden email]> wrote:
>>
>> Do we have any need for Bifoldable?  We have
>>
>>     foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
>>     foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a
>>
>> These functions seem to give more control of how the fold happens.
>>
>> And if we'd want Bifoldable, shouldn't the Bifoldable instance be
>> implemented in terms of just foldrWithKey?  Why have a recursive
>> implementation?
>>
>> Personally, I consider Bifoldable a fringe class, as I would hope that
>> in general with fusion, I can just go via bimap and ordinary Foldable
>> without much penalty.
>>
>> On 2020-05-31 07:20, George Wilson wrote:
>>> If you have a non-commutative monoid, the result could easily be
>>> different than you expect. eg. if you think it would do all keys and
>>> then all values, rather than interleaving (which is I assume the most
>>> efficient to implement).
>>> Despite that I'm still +1 on this.
>>>
>>> On Sun, 31 May 2020 at 14:59, Joseph C. Sible <[hidden email]> wrote:
>>>>
>>>> I'll admit I don't have a strong use case for this. I was just looking
>>>> at instances and noticed that these seemed to be a weird omission,
>>>> since there was an obvious definition. But I also don't think it's
>>>> confusing at all. Since (,), Set, and HashSet are Foldable, and (,)
>>>> and (,,) x are Bifoldable, it seems only logical to have Map and
>>>> HashMap be Bifoldable too. What exactly would be confusing about any
>>>> of these?
>>>>
>>>> Joseph C. Sible
>>>>
>>>> On Sat, May 30, 2020 at 8:33 PM David Feuer <[hidden email]> wrote:
>>>>>
>>>>> Let me take that back. I forgot how weird Bifoldable and Bitraversable are for product types and product-like types. Is this instance actually useful for anything, or is it mostly confusing?
>>>>>
>>>>> On Mon, Apr 13, 2020, 9:46 PM David Feuer <[hidden email]> wrote:
>>>>>>
>>>>>> I would go as far as to say we don't need to continue the proposal process here. We're doing it.
>>>>>>
>>>>>> On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
>>>>>>>
>>>>>>> This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.
>>>>>>>
>>>>>>> On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
>>>>>>>>
>>>>>>>> I'd like to propose a change to the containers package: adding a
>>>>>>>> Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
>>>>>>>> no obvious problems were brought up. I submitted a PR implementing it
>>>>>>>> [2]. This seems like an obvious and straightforward instance to me.
>>>>>>>> Thoughts?
>>>>>>>>
>>>>>>>> Joseph C. Sible
>>>>>>>>
>>>>>>>> [1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
>>>>>>>> [2]: https://github.com/haskell/containers/pull/714
>>>>>>>> _______________________________________________
>>>>>>>> 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
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bifoldable instance for Map

Zemyla
Set is a Foldable, but not a Functor or Traversable. So the precedent is there.

On Mon, Jun 1, 2020, 05:16 Andreas Abel <[hidden email]> wrote:
 > We have Functor, Foldable, and Traversable instances

Yes, and good so, since I use these type classes every day.  Haven't
ever used Bifoldable, though.  This is why I question the need.

In general, I am a proponent of fat libraries, thus, I am not strongly
against such an addition, especially if it is only a light-weight
overlay over foldrWithKey.

I guess since Bifoldable is in base already (wasn't aware of this), the
ship has already sailed on discussing its wide-spread usability.  I
remain unconvinced though.

What weights in for me is that Map does not have sensible Bifunctor or
Bitraversable instances (since manipulating the keys does not preserve
the tree structure in general).  Thus, we cannot make the chord
(Bi)functor/(Bi)foldable/(Bi)traversable complete.

My take would be to add Bifoldable only on public demand.
But let's hear other opinions as well.

--Andreas


On 2020-05-31 18:49, Joseph C. Sible wrote:
> I don't find this argument convincing. We have Functor, Foldable, and
> Traversable instances even though mapWithKey, foldrWithKey, and
> traverseWithKey give more control than they do. We have a Semigroup
> instance even though unionWith and unionWithKey give more control than
> it does.
>
> As for the implementation, I'd be fine with changing it to be in terms
> of foldrWithKey. I just care that we have this instance somehow.
>
> Joseph C. Sible
>
> On Sun, May 31, 2020 at 6:23 AM Andreas Abel <[hidden email]> wrote:
>>
>> Do we have any need for Bifoldable?  We have
>>
>>     foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
>>     foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a
>>
>> These functions seem to give more control of how the fold happens.
>>
>> And if we'd want Bifoldable, shouldn't the Bifoldable instance be
>> implemented in terms of just foldrWithKey?  Why have a recursive
>> implementation?
>>
>> Personally, I consider Bifoldable a fringe class, as I would hope that
>> in general with fusion, I can just go via bimap and ordinary Foldable
>> without much penalty.
>>
>> On 2020-05-31 07:20, George Wilson wrote:
>>> If you have a non-commutative monoid, the result could easily be
>>> different than you expect. eg. if you think it would do all keys and
>>> then all values, rather than interleaving (which is I assume the most
>>> efficient to implement).
>>> Despite that I'm still +1 on this.
>>>
>>> On Sun, 31 May 2020 at 14:59, Joseph C. Sible <[hidden email]> wrote:
>>>>
>>>> I'll admit I don't have a strong use case for this. I was just looking
>>>> at instances and noticed that these seemed to be a weird omission,
>>>> since there was an obvious definition. But I also don't think it's
>>>> confusing at all. Since (,), Set, and HashSet are Foldable, and (,)
>>>> and (,,) x are Bifoldable, it seems only logical to have Map and
>>>> HashMap be Bifoldable too. What exactly would be confusing about any
>>>> of these?
>>>>
>>>> Joseph C. Sible
>>>>
>>>> On Sat, May 30, 2020 at 8:33 PM David Feuer <[hidden email]> wrote:
>>>>>
>>>>> Let me take that back. I forgot how weird Bifoldable and Bitraversable are for product types and product-like types. Is this instance actually useful for anything, or is it mostly confusing?
>>>>>
>>>>> On Mon, Apr 13, 2020, 9:46 PM David Feuer <[hidden email]> wrote:
>>>>>>
>>>>>> I would go as far as to say we don't need to continue the proposal process here. We're doing it.
>>>>>>
>>>>>> On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
>>>>>>>
>>>>>>> This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.
>>>>>>>
>>>>>>> On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
>>>>>>>>
>>>>>>>> I'd like to propose a change to the containers package: adding a
>>>>>>>> Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
>>>>>>>> no obvious problems were brought up. I submitted a PR implementing it
>>>>>>>> [2]. This seems like an obvious and straightforward instance to me.
>>>>>>>> Thoughts?
>>>>>>>>
>>>>>>>> Joseph C. Sible
>>>>>>>>
>>>>>>>> [1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
>>>>>>>> [2]: https://github.com/haskell/containers/pull/714
>>>>>>>> _______________________________________________
>>>>>>>> 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
_______________________________________________
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: Bifoldable instance for Map

David Feuer
In reply to this post by David Feuer
Let me be more specific. Whereas we can get intuition for Foldable from

    toList :: t a -> [a]

we get intuition for Bifoldable from the hypothetical

    toEitherList :: t a b -> [Either a b]

This seems quite reasonable for some types.

    data Loost a b
      = Nool
      | Corns b (Loost a b)
      | Colns a (Loost a b)

But for something like

    newtype Plist a b
      = PNil
      | PCons a b (PList a b)

it feels awfully strange. Independent parts of the structure just get lumped together.

On Sat, May 30, 2020, 8:33 PM David Feuer <[hidden email]> wrote:
Let me take that back. I forgot how weird Bifoldable and Bitraversable are for product types and product-like types. Is this instance actually useful for anything, or is it mostly confusing?

On Mon, Apr 13, 2020, 9:46 PM David Feuer <[hidden email]> wrote:
I would go as far as to say we don't need to continue the proposal process here. We're doing it.

On Mon, Apr 13, 2020, 9:44 PM David Feuer <[hidden email]> wrote:
This seems eminently reasonable to me. We must also be sure to add one to Data.HashMap if that's missing too.

On Mon, Apr 13, 2020, 9:36 PM Joseph C. Sible <[hidden email]> wrote:
I'd like to propose a change to the containers package: adding a
Bifoldable instance to Map. I briefly mentioned this on Reddit [1] and
no obvious problems were brought up. I submitted a PR implementing it
[2]. This seems like an obvious and straightforward instance to me.
Thoughts?

Joseph C. Sible

[1]: https://old.reddit.com/r/haskell/comments/fsgqd6/monthly_hask_anything_april_2020/fn90d6k/
[2]: https://github.com/haskell/containers/pull/714
_______________________________________________
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: Bifoldable instance for Map

Joseph C. Sible
Aren't you basically just saying that you lose some of the structure
(namely, the knowledge that the "key" and its "value" go together)?
But doesn't every Foldable instance on a type that's more complex than
a list also do that? For example, if you fold a rose tree, you lose
the knowledge of which elements came from which branches.

(Completely unrelated: "Loost" and the names of its data constructors
sound like something straight from Dr. Seuss.)

Joseph C. Sible

On Mon, Jun 1, 2020 at 8:28 AM David Feuer <[hidden email]> wrote:

>
> Let me be more specific. Whereas we can get intuition for Foldable from
>
>     toList :: t a -> [a]
>
> we get intuition for Bifoldable from the hypothetical
>
>     toEitherList :: t a b -> [Either a b]
>
> This seems quite reasonable for some types.
>
>     data Loost a b
>       = Nool
>       | Corns b (Loost a b)
>       | Colns a (Loost a b)
>
> But for something like
>
>     newtype Plist a b
>       = PNil
>       | PCons a b (PList a b)
>
> it feels awfully strange. Independent parts of the structure just get lumped together.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bifoldable instance for Map

David Feuer
Yes, folding generally loses structure. This just seems especially
egregious. Can you think of even a single function polymorphic over
`Bifoldable` containers that you'd find it useful to pass a `HashMap`
to?

On Mon, Jun 1, 2020 at 5:34 PM Joseph C. Sible <[hidden email]> wrote:

>
> Aren't you basically just saying that you lose some of the structure
> (namely, the knowledge that the "key" and its "value" go together)?
> But doesn't every Foldable instance on a type that's more complex than
> a list also do that? For example, if you fold a rose tree, you lose
> the knowledge of which elements came from which branches.
>
> (Completely unrelated: "Loost" and the names of its data constructors
> sound like something straight from Dr. Seuss.)
>
> Joseph C. Sible
>
> On Mon, Jun 1, 2020 at 8:28 AM David Feuer <[hidden email]> wrote:
> >
> > Let me be more specific. Whereas we can get intuition for Foldable from
> >
> >     toList :: t a -> [a]
> >
> > we get intuition for Bifoldable from the hypothetical
> >
> >     toEitherList :: t a b -> [Either a b]
> >
> > This seems quite reasonable for some types.
> >
> >     data Loost a b
> >       = Nool
> >       | Corns b (Loost a b)
> >       | Colns a (Loost a b)
> >
> > But for something like
> >
> >     newtype Plist a b
> >       = PNil
> >       | PCons a b (PList a b)
> >
> > it feels awfully strange. Independent parts of the structure just get lumped together.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bifoldable instance for Map

Joseph C. Sible
Let me turn this around: do you believe the Bifoldable class is a
useful abstraction at all? Are there any real types (i.e., that exist
in `base` or some other popular library or program, rather than made
up for the sake of example) that you think have a useful Bifoldable
instance? In other words, is your issue actually with this instance,
or is it really with the entire class?

Joseph C. Sible

On Mon, Jun 1, 2020 at 5:51 PM David Feuer <[hidden email]> wrote:

>
> Yes, folding generally loses structure. This just seems especially
> egregious. Can you think of even a single function polymorphic over
> `Bifoldable` containers that you'd find it useful to pass a `HashMap`
> to?
>
> On Mon, Jun 1, 2020 at 5:34 PM Joseph C. Sible <[hidden email]> wrote:
> >
> > Aren't you basically just saying that you lose some of the structure
> > (namely, the knowledge that the "key" and its "value" go together)?
> > But doesn't every Foldable instance on a type that's more complex than
> > a list also do that? For example, if you fold a rose tree, you lose
> > the knowledge of which elements came from which branches.
> >
> > (Completely unrelated: "Loost" and the names of its data constructors
> > sound like something straight from Dr. Seuss.)
> >
> > Joseph C. Sible
> >
> > On Mon, Jun 1, 2020 at 8:28 AM David Feuer <[hidden email]> wrote:
> > >
> > > Let me be more specific. Whereas we can get intuition for Foldable from
> > >
> > >     toList :: t a -> [a]
> > >
> > > we get intuition for Bifoldable from the hypothetical
> > >
> > >     toEitherList :: t a b -> [Either a b]
> > >
> > > This seems quite reasonable for some types.
> > >
> > >     data Loost a b
> > >       = Nool
> > >       | Corns b (Loost a b)
> > >       | Colns a (Loost a b)
> > >
> > > But for something like
> > >
> > >     newtype Plist a b
> > >       = PNil
> > >       | PCons a b (PList a b)
> > >
> > > it feels awfully strange. Independent parts of the structure just get lumped together.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bifoldable instance for Map

David Feuer
No idea. Traversing in a Biapplicative can definitely be interesting. I don't know what Bifoldable or Bitraversable can do.

On Tue, Jun 2, 2020, 12:12 AM Joseph C. Sible <[hidden email]> wrote:
Let me turn this around: do you believe the Bifoldable class is a
useful abstraction at all? Are there any real types (i.e., that exist
in `base` or some other popular library or program, rather than made
up for the sake of example) that you think have a useful Bifoldable
instance? In other words, is your issue actually with this instance,
or is it really with the entire class?

Joseph C. Sible

On Mon, Jun 1, 2020 at 5:51 PM David Feuer <[hidden email]> wrote:
>
> Yes, folding generally loses structure. This just seems especially
> egregious. Can you think of even a single function polymorphic over
> `Bifoldable` containers that you'd find it useful to pass a `HashMap`
> to?
>
> On Mon, Jun 1, 2020 at 5:34 PM Joseph C. Sible <[hidden email]> wrote:
> >
> > Aren't you basically just saying that you lose some of the structure
> > (namely, the knowledge that the "key" and its "value" go together)?
> > But doesn't every Foldable instance on a type that's more complex than
> > a list also do that? For example, if you fold a rose tree, you lose
> > the knowledge of which elements came from which branches.
> >
> > (Completely unrelated: "Loost" and the names of its data constructors
> > sound like something straight from Dr. Seuss.)
> >
> > Joseph C. Sible
> >
> > On Mon, Jun 1, 2020 at 8:28 AM David Feuer <[hidden email]> wrote:
> > >
> > > Let me be more specific. Whereas we can get intuition for Foldable from
> > >
> > >     toList :: t a -> [a]
> > >
> > > we get intuition for Bifoldable from the hypothetical
> > >
> > >     toEitherList :: t a b -> [Either a b]
> > >
> > > This seems quite reasonable for some types.
> > >
> > >     data Loost a b
> > >       = Nool
> > >       | Corns b (Loost a b)
> > >       | Colns a (Loost a b)
> > >
> > > But for something like
> > >
> > >     newtype Plist a b
> > >       = PNil
> > >       | PCons a b (PList a b)
> > >
> > > it feels awfully strange. Independent parts of the structure just get lumped together.

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

Re: Bifoldable instance for Map

Andreas Abel
I think bitraverse makes some sense.  If you have a tree with two kinds
of leaves, you can effectfully map over it.

   bitraverse
     :: Applicative f => (a -> f c) -> (b -> f d) -> t a b -> f (t c d)

Here, the tree structure stays in place.

However, bifolding is less meaningful because the ordering of elements
in the resulting collection (monoid) is somewhat arbitrary.  This
argument has already been raised in this thread.

In the example of maps where you have keys and values, the distinction
between them loses its meaning when you do a bifold, and there is no
reason why they should be ordered in a certain way in the monoid.  In
contrast, the fold[L/R]WithKey operations bring the problem to the
attention of the programmer.

Another angle to judge the usefulness of Bifoldable (for Data.Map) could
be how many clients of Bifoldable there are.  How many methods that one
would want to run on a Map have a Bifoldable constraint?

On 2020-06-02 06:39, David Feuer wrote:

> No idea. Traversing in a Biapplicative can definitely be interesting. I
> don't know what Bifoldable or Bitraversable can do.
>
> On Tue, Jun 2, 2020, 12:12 AM Joseph C. Sible <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Let me turn this around: do you believe the Bifoldable class is a
>     useful abstraction at all? Are there any real types (i.e., that exist
>     in `base` or some other popular library or program, rather than made
>     up for the sake of example) that you think have a useful Bifoldable
>     instance? In other words, is your issue actually with this instance,
>     or is it really with the entire class?
>
>     Joseph C. Sible
>
>     On Mon, Jun 1, 2020 at 5:51 PM David Feuer <[hidden email]
>     <mailto:[hidden email]>> wrote:
>      >
>      > Yes, folding generally loses structure. This just seems especially
>      > egregious. Can you think of even a single function polymorphic over
>      > `Bifoldable` containers that you'd find it useful to pass a `HashMap`
>      > to?
>      >
>      > On Mon, Jun 1, 2020 at 5:34 PM Joseph C. Sible
>     <[hidden email] <mailto:[hidden email]>> wrote:
>      > >
>      > > Aren't you basically just saying that you lose some of the
>     structure
>      > > (namely, the knowledge that the "key" and its "value" go together)?
>      > > But doesn't every Foldable instance on a type that's more
>     complex than
>      > > a list also do that? For example, if you fold a rose tree, you lose
>      > > the knowledge of which elements came from which branches.
>      > >
>      > > (Completely unrelated: "Loost" and the names of its data
>     constructors
>      > > sound like something straight from Dr. Seuss.)
>      > >
>      > > Joseph C. Sible
>      > >
>      > > On Mon, Jun 1, 2020 at 8:28 AM David Feuer
>     <[hidden email] <mailto:[hidden email]>> wrote:
>      > > >
>      > > > Let me be more specific. Whereas we can get intuition for
>     Foldable from
>      > > >
>      > > >     toList :: t a -> [a]
>      > > >
>      > > > we get intuition for Bifoldable from the hypothetical
>      > > >
>      > > >     toEitherList :: t a b -> [Either a b]
>      > > >
>      > > > This seems quite reasonable for some types.
>      > > >
>      > > >     data Loost a b
>      > > >       = Nool
>      > > >       | Corns b (Loost a b)
>      > > >       | Colns a (Loost a b)
>      > > >
>      > > > But for something like
>      > > >
>      > > >     newtype Plist a b
>      > > >       = PNil
>      > > >       | PCons a b (PList a b)
>      > > >
>      > > > it feels awfully strange. Independent parts of the structure
>     just get lumped together.
>
>
> _______________________________________________
> 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: Bifoldable instance for Map

Joseph C. Sible
Isn't the order of elements when you use a Traversable also arbitrary,
since trees have depth-first and breadth-first traversals?

Joseph C. Sible

On Tue, Jun 2, 2020 at 9:39 AM Andreas Abel <[hidden email]> wrote:

>
> I think bitraverse makes some sense.  If you have a tree with two kinds
> of leaves, you can effectfully map over it.
>
>    bitraverse
>      :: Applicative f => (a -> f c) -> (b -> f d) -> t a b -> f (t c d)
>
> Here, the tree structure stays in place.
>
> However, bifolding is less meaningful because the ordering of elements
> in the resulting collection (monoid) is somewhat arbitrary.  This
> argument has already been raised in this thread.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bifoldable instance for Map

Andreas Abel
On 2020-06-03 01:47, Joseph C. Sible wrote:
> Isn't the order of elements when you use a Traversable also arbitrary,
> since trees have depth-first and breadth-first traversals?

Do you mean the order of the effects?  Yes, this order isn't specified.

The tree structure should stay intact though (including the leaves,
which are merely filled with new content).

--Andreas

> On Tue, Jun 2, 2020 at 9:39 AM Andreas Abel <[hidden email]> wrote:
>>
>> I think bitraverse makes some sense.  If you have a tree with two kinds
>> of leaves, you can effectfully map over it.
>>
>>     bitraverse
>>       :: Applicative f => (a -> f c) -> (b -> f d) -> t a b -> f (t c d)
>>
>> Here, the tree structure stays in place.
>>
>> However, bifolding is less meaningful because the ordering of elements
>> in the resulting collection (monoid) is somewhat arbitrary.  This
>> argument has already been raised in this thread.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries