Bifoldable instance for Map

Andreas Abel andreas.abel at
Mon Jun 1 10:15:12 UTC 2020

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


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 <andreas.abel at> 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 <josephcsible at> 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 <david.feuer at> 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 <david.feuer at> 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 <david.feuer at> 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 at> 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]:
>>>>>>>> [2]:
>>>>>>>> _______________________________________________
>>>>>>>> Libraries mailing list
>>>>>>>> Libraries at
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> Libraries at
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at
>> _______________________________________________
>> Libraries mailing list
>> Libraries at

More information about the Libraries mailing list