partition or partitionE on Foldable?

[fommil]

Would it make sense for something like stdlib partition to be on Foldable? I've certainly used it a lot myself and I note that IList and ISet see it worthy enough to implement.

Going even further, a partitionE would be great, e.g. I wrote this for work at some point (for cats)

  implicit class PartitionE[E](trav: NonEmptyList[E]) {
    @SuppressWarnings(Array("org.wartremover.warts.Throw"))
    def partitionE[A, B](
        f: E => Either[A, B]
      ): (Ior[NonEmptyList[A], NonEmptyList[B]]) = {
      val (lefts, rights) = trav.toList.map(f).partition(_.isLeft)
      Ior
        .fromOptions(
          Nel(lefts.collect { case Left(left) => left }),
          Nel(rights.collect { case Right(right) => right })
        )
        .getOrElse {
          throw new IllegalStateException("impossible")
        }
    }
  }

[jdegoes]

👍 for the method implemented generically.

In order to implement, def partition[F[_], A, B, C](f: A => B \/ C): F[A] => F[B] \&/ F[C], one needs both "fold" and "unfold", because one has to both tear down F[_], and rebuild either or both sides.

A weakness of Scalaz is that while it has Foldable, it doesn't have Unfoldable. But if we had something like that (PureScript has one, and Matryoshka has much more precise formulations), one could put together a collection-like type class that can both be torn down and built up, and this would make a good home for a generically implemented partition that can be specialized by different concrete data structures for performance reasons.

[fommil]

FYI the cats implementation typelevel/cats#1858

[jdegoes]

They require Alternative[F] for their generic partitionEither, which allows monoidally building up the left and / or right sides. This "works" but imposes O(n^2) performance on many data structures (List, etc.). Basing the implementation on unfold will allow O(n) implementations. Their nonEmptyPartition builds for a concrete type (NonEmptyList) and therefore presumably doesn't have this issue.

[fommil]

I've not had much need for this since proposing it.

[fommil]

@hrhino is interested in this...