Add a combinator like partitionEither for FunctorFilter

[nigredo-tori]

The current implementation of partitionEither requires Foldable and Alternative (Applicative + MonoidK). These requirements mean that, for example, SortedMap[K, *] can't be partitioned! This is surprising, since there's a trivial partitionEither for any FunctorFilter:

def partitionEither0[F[_]: FunctorFilter, A, B, C](
  fa: F[A]
)(f: A => Either[B, C]): (F[B], F[C]) =
  (fa.mapFilter(f(_).left.toOption),
    fa.mapFilter(f(_).toOption))

I can't say for sure whether this requirement is weaker than the one we have now - but off the top of my head I can't really think of a type that has Foldable and Alternative, but not FunctorFilter.

As an aside, for any type with these two instances we can build something quite similar to mapFilter:

def mapFilter0[F[_]: Foldable: Alternative, A, B](
  fa: F[A]
)(f: A => Option[B]): F[B] =
  fa.foldMapK[F, B] { a =>
    f(a).fold(
      Alternative[F].empty[B]
    )(Alternative[F].pure)
  }

Note, however, that, since this version uses two separate instances, we can't prove that FunctorFilter laws hold for it.

This brings me back to partitionEither. Note that for the implementation above we can actually prove a lot of properties of partitionEither that are implied, but currently not guaranteed. For example, we can show that, as long as the FunctorFilter instance is lawful, the following holds:

partitionEither0(fa)(Right(_))._2 <-> fa

I don't think the similar property can be proven for the existing partitionEither implementation, although I don't have a counterexample ready.

[nigredo-tori]

In the same fashion, we can reimplement partitionEitherM using only TraverseFilter[F] and Applicative[G].