Remove FunctorFilter

[kcsongor]

I argue that the FunctorFilter type class is unnecessary:

First of all, all instances need to have a well-defined empty (even though this is not encoded in the type-class itself, but if I send all values to None, then the resulting 'thing' must not contain any Bs, because I could only get a B from the A => Option[B] function).

Then there is the other thing, that all the None results disappear from the resulting Functor.
Let's try to define it for a very simple example, Option.
I start with Some(5), and I filter it with (_ => None). The outcome is None. Notice how the Some constructor changed to the None constructor. This is something that an ordinary Functor can't do!
This means that whatever FunctorFilter actually is, it needs to know how to produce new values based on the content of an existing value.
This is also evidenced by the fact that it allows you to reduce the number of elements in the container. How can we do that? For example, you can use something like Foldable's foldMap, to map all elements to some Monoid, then combine those. Since here, the resulting structure is F[B], it means that if we go the Foldable route to achieve filtering, we need a monoid instance for F[B]. (note that we already needed the empty). Actually, I need a Monoid[F[B]] for all B.
Using Foldable this way really just means that we filter the structure by rebuilding it, leaving out the elements we don't need.

Furthermore, under the premise that we have a Foldable that can filter things, I can specialise the foldMap function from def foldMap[A, B](fa: F[A])(f: A => B)(implicit B: Monoid[B]): B to
flatMap[A, B](fa: F[A])(afb: A => F[B]) => F[B], since we required a Monoid[F[B]] for all B. This would mean that all FunctorFilters admit a FlatMap instance too. But given the above instances, FunctorFilter doesn't add any extra value.

This would mean that a Foldable, a Monoid, and a FlatMap instance are a necessary and sufficient condition. Also note, however, that we never required the existence of a pure function, so a Monad constraint is not needed.

I couldn't come up with any other approach that doesn't eventually reduce to a Foldable one way or another. If someone could provide examples where this isn't the case, I would be very interested.

[ceedubs]

@kcsongor thank you for raising your concerns. I'm not sure that I followed all of your comments, but I'll respond to a couple things that caught my attention.

empty

I've seen both you and @non mention that FunctorFilter should probably have an empty. I'm open to this idea, and I can't think of any valid FunctorFilter instances that it would exclude. It might even provide a useful law or two.

In this comment @non said:

I agree with your reasoning that FunctorFilter (and this type class) should require empty since you can derive it using .filter(_ => false).

While I think that every FunctorFilter instance can probably have an empty method, I don't think it can actually be derived unless you also have an Applicative instance. I think that I mentioned on my original PR that if we decide to add an ApplicativeFilter type class than empty probably belongs on it and it can be derived, but I didn't have a use-case for ApplicativeFilter. However, it may be the case that empty belongs on FunctorFilter even though it can't be derived.

FunctorFilter instances as opposed to other type classes

@kcsongor correct me if I'm wrong, but my understanding is that in your comment above you are saying that FunctorFilter becomes redundant if you have a Foldable along with some other instances (such as Monoid and FlatMap). This may be true, but I think that it isn't the whole story.

Firstly, I think that in many cases you can get better performance out of FunctorFilter-based abstractions than you could with combining Foldable, Monoid, and FlatMap. But I think that this point might not be as compelling as the one below.

Foldable leaves out data structures such as fs2's Stream. These are structures that are list-like but elements within the stream may be produced by effects (such as Task). You can filter these structures (and provide a FunctorFilter instance), but since ultimately getting the values may require running a Task, you miss out entirely on Foldable, since foldLeft needs to return a B as opposed to an F[B]. For the same reasons, you can't provide a TraverseFilter instance (as this ultimately extends Foldable). These sorts of structures (I think iteratee-based structures would also qualify) do produce MonadFilter instances, so I could see an argument that you can achieve the desired abstraction via that. However this enforces a stricter constraint and, probably more importantly: I think that if MonadFilter and TraverseFilter are both going to exist with the current form of typeclass-encoding that cats uses, from a practical perspective you kind of need FunctorFilter to provide the common filter etc methods to avoid ambiguities.

[eed3si9n]

We can implement filter universally on A given an Alternative as follows:

scala> :paste
// Entering paste mode (ctrl-D to finish)
def filter[F[_]: Alternative, A](fa: F[A])(cond: A => Boolean): F[A] =
  {
    var acc = Alternative[F].empty[A]
    Alternative[F].map(fa) { x =>
      if (cond(x)) acc = Alternative[F].combineK(acc, Alternative[F].pure(x))
      else ()
    }
    acc
  }

Is Alternative not weak enough? i.e. Are there instances that inhabit FunctorFilter that's not an Alternative?

[kcsongor]

@eed3si9n I think you can't define pure for Map

[edmundnoble]

Here's a summary of my findings in this area, working on cats-mtl.

FunctorFilter should not be used unless there is a unique empty F[A] value.

The moment you start to say something about the F[_] context itself, Functor is not the abstraction you want. I think this is reasonable and justifies its existence in its current form.

As it is, if there are any further thoughts on this issue an issue should be opened at cats-mtl.