typelevel / typelevel/cats

Add a combinator like partitionEither for FunctorFilter

Open
#3,802 1 comment 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Scala
Stars
5.5k
Forks
1.2k
Avg merge
2d 10h
Merged PRs (30d)
5

Description

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.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Locate the existing partitionEither implementation and the FunctorFilter API, then compare their typeclass requirements and available tests. Add the requested FunctorFilter-based combinator only after resolving the API and law implications; done means the behavior described in the issue is covered by tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
scala
Domain
backend-api-design
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.