Proposal: Add filterM or filterA to Data.Sequence

Johan Tibell johan.tibell at
Tue Dec 30 18:05:45 UTC 2014

The larger point is this: should we have applicative functions for every
higher order function, for every data type? For example, one could make an
argument for having Map.alterA in addition to Map.alter, because without
alterA one would have to use a combination of lookup and insert, which
could be slower, to achieve the same effect.

The obvious downside is the explosion of functions in the API, which is
even worse due to their already being lazy and strict versions of most
higher-order function (i.e. now we'd have to have 2*2 versions of every
function). This seems like a failure in composability and abstraction.
Until we've figured out a way to deal with this general issue that doesn't
involve duplicating tons of code and swelling the API, I've been pushing
back on changes like this.

In this particular case, having to go via lists might hurt performance a
bit, but might still be better than the other alternative.

As one of the maintainers of the containers package these are the kind of
issues I have to consider*.

* This is by the way one of the reasons that it's important for packages to
have dedicated maintainers, so make sure proposed changes are considered in
the larger context of the health and evolution of the package as a whole.

On Tue, Dec 30, 2014 at 12:52 PM, Artyom <yom at> wrote:

> I’m not sure I understand. Do you mean that |filterM| shouldn’t exist for
> data structures for which |filterM . toList| is as fast?
> If this is the case, I wish that it was at least specified in the
> documentation that e.g. “this function doesn’t exist because the naive
> composition is guaranteed to be optimised away / the faster version is
> actually impossible to write / etc.”. I find myself wondering way too often
> whether some piece of code I’ve written is a potential candidate for
> optimisation, and knowing in advance that the naive version is the
> “recommended” approach lets me not waste my time on benchmarking code which
> was already benchmarked by others.
> On 12/30/2014 08:05 PM, Johan Tibell wrote:
>  We should check that `filterM . toList` isn't as fast. That was the case
>> for bytestring and we rejected adding filterM there for that reason.
>> On Mon, Dec 29, 2014 at 6:13 AM, Edward Kmett <ekmett at <mailto:
>> ekmett at>> wrote:
>>     +1 to just generalizing filterM in Data.Sequence
>>     On Sun, Dec 28, 2014 at 12:22 AM, David Feuer
>>     <david.feuer at <mailto:david.feuer at>> wrote:
>>         This can be given exactly the same implementation as the one
>>         for lists:
>>         filterM :: (Applicative f) => (a -> f Bool) -> Seq a -> f (Seq a)
>>         filterM p = foldr go (pure empty)
>>           where
>>             go x r = f <0.3927809241601645gt; p x <*> r
>>               where
>>                 f flg ys = if flg then x <| ys else ys
>>         Bikeshed all you like over the name.
>>         _______________________________________________
>>         Libraries mailing list
>>         Libraries at <mailto:Libraries at>
>>     _______________________________________________
>>     Libraries mailing list
>>     Libraries at <mailto:Libraries at>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at
>> _______________________________________________
> Libraries mailing list
> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list