Bifoldable instance for Map

Joseph C. Sible

14 Apr 2020 14 Apr '20

1:35 a.m.

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... [2]: https://github.com/haskell/containers/pull/714

Show replies by date

David Feuer

14 Apr 14 Apr

1:44 a.m.

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 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... [2]: https://github.com/haskell/containers/pull/714 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

David Feuer

1:46 a.m.

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 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 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... [2]: https://github.com/haskell/containers/pull/714 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

David Feuer

31 May 31 May

12:33 a.m.

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 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 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 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... [2]: https://github.com/haskell/containers/pull/714 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Joseph C. Sible

4:58 a.m.

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 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 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 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 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... [2]: https://github.com/haskell/containers/pull/714 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

George Wilson

5:20 a.m.

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 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 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 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 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 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... [2]: https://github.com/haskell/containers/pull/714 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

Andreas Abel

10:23 a.m.

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 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 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 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 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 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... [2]: https://github.com/haskell/containers/pull/714 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

Joseph C. Sible

4:49 p.m.

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 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 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 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 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 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 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... > [2]: https://github.com/haskell/containers/pull/714 > _______________________________________________ > Libraries mailing list > Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

Andreas Abel

1 Jun 1 Jun

10:15 a.m.

...

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 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 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 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 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 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 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... >> [2]: https://github.com/haskell/containers/pull/714 >> _______________________________________________ >> Libraries mailing list >> Libraries@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

Zemyla

12:15 p.m.

Set is a Foldable, but not a Functor or Traversable. So the precedent is there. On Mon, Jun 1, 2020, 05:16 Andreas Abel 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

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

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

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

wrote:

...
> > I would go as far as to say we don't need to continue the proposal

On 2020-05-31 18:49, Joseph C. Sible wrote: process here. We're doing it.

...
...
...
...
...
> > On Mon, Apr 13, 2020, 9:44 PM David Feuer 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 < josephcsible@gmail.com> 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... >>> [2]: https://github.com/haskell/containers/pull/714 >>> _______________________________________________ >>> Libraries mailing list >>> Libraries@haskell.org >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

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

David Feuer

12:27 p.m.

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 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 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 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 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... [2]: https://github.com/haskell/containers/pull/714 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Joseph C. Sible

9:34 p.m.

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

David Feuer

9:51 p.m.

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

Joseph C. Sible

2 Jun 2 Jun

4:12 a.m.

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

David Feuer

4:39 a.m.

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

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

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.

Andreas Abel

1:39 p.m.

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 mailto:josephcsible@gmail.com> 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 mailto:david.feuer@gmail.com> 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 mailto:josephcsible@gmail.com> 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 mailto:david.feuer@gmail.com> 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 Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Joseph C. Sible

11:47 p.m.

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

Andreas Abel

3 Jun 3 Jun

10:26 p.m.

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

Joseph C. Sible

14 Apr 14 Apr

3:21 a.m.

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 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 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... [2]: https://github.com/haskell/containers/pull/714 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

1859

Age (days ago)

1909

Last active (days ago)

List overview

Download

18 comments

5 participants

participants (5)

Andreas Abel
David Feuer
George Wilson
Joseph C. Sible
Zemyla

Bifoldable instance for Map

tags

participants (5)