Proposal: Add filterM or filterA to Data.Sequence

[Milan Straka]

Hi all,

> -----Original message-----
> From: David Feuer <david.feuer at gmail.com>
> Sent: 30 Dec 2014, 18:03
>
> There won't be any such numbers in this case, because access to the
> details of the sequence structure does not seem to help implement this
> function.

sorry for not making clear -- I was interested in difference between the
mentioned
| filterMSeq f = fmap fromList . filterM f . toList
and your foldr-based implementation. I can imagine that one can use
filterMSeq in place instead of filterM, so that is why I am interested
between filterMSeq and the specialized implementation (which is just
a plain foldr + <|).

> The same is true of the following, all of which already exist:
> 
> replicate, replicateM, iterateN  -- all are implemented using replicateA
> unfoldr, unfoldl --implemented using <| and |>
> null -- can be written just as well using  null xs = case viewl xs of
> {EmptyL -> True; _ -> False}
> scanl, scanr, scanl1, scanr1 -- defined ultimately in terms of traverse
> spanl, spanr, breakl, breakr, takeWhile, dropWhile -- defined in terms
> of splitAt
> findIndicesL, findIndicesR -- defined in terms of foldlWithIndex, foldrWithIndex
> take, drop -- previously defined using splitAt; currently defined
> using splitAt', but those two functions are likely to merge
> filter -- uses foldl
> elemIndexL, elemIndicesL, elemIndexR, elemIndicesR, findIndexL,
> findIndexR -- all defined using findIndicesL and findIndicesR
> update -- uses adjust
> zip, zipWith3, zip3, zipWith4, zip4 -- All defined from zipWith
> 
> I think almost all of these functions are good to have around
> (although the elemIndex family seems a bit silly). Adding a few more
> to round things out seems reasonable to me as well.

true, that is why it is a general rule (to not add functions which can
be implemented using others), not an absolute rule.

The question is whether filterM is as "basic" method used frequently
enough (for example, no one obviously questions zip).

Note that it is not obvious what type does filterM has (unlike e.g. zip),
now that we have Applicative and also filterM is changing in base. From
this point of view, it makes sense to use
  fmap fromList . filterM f . toList
because then we do not have inconsistent filterM-s.

Cheers,
Milan

> On Tue, Dec 30, 2014 at 5:41 PM, Milan Straka <fox at ucw.cz> wrote:
> > Hi all,
> >
> >> -----Original message-----
> >> From: David Feuer <david.feuer at gmail.com>
> >> Sent: 30 Dec 2014, 13:15
> >>
> >> On Tue, Dec 30, 2014 at 12:05 PM, Johan Tibell <johan.tibell at gmail.com> 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.
> >>
> >> Let me expand that definition to what it really looks like:
> >>
> >>   filterMSeq f = fmap fromList . filterM f . toList
> >>
> >> Yes, you can do this. Yes, it's probably even pretty efficient. But
> >> it's a bit painful to have to expand things out like this just to
> >> switch a bit of code from lists to sequences.
> >
> > the problem with this is that there are really many functions that
> > "would be useful", but we do not really want to add them all.
> >
> > A general rule I have been using is "can this be implemented
> > straightforwardly using existing methods without hurting performance
> > much"? So I would like to see the numbers, please.
> >
> > Also, filterM is not yet settled in base, so we should wait some time
> > until it is.
> >
> > Cheers,
> > Milan
> >
> > PS: It is a shame we cannot reuse Foldable and/or Traversable for
> > filtering. Maybe we should add a new Filterable class?
>