Add collectFirst and collectFirstPar to Traversable

[sideeffffect]

Difficulty: advanced, experience with both ZIO Prelude and concurrent programming with ZIO is an advantage

Please implement on Traversable methods with these signatures

  def collectFirst[G[+_]: AssociativeEither: Covariant: IdentityBoth, A, B](fa: F[A])(f: A => G[B]): G[Option[B]] = ???

  def collectFirstPar[G[+_]: CommutativeEither: Covariant: IdentityBoth, A, B](fa: F[A])(f: A => G[B]): G[Option[B]] = ???

None is returned in case of an empty Traversable or if there is no successful result. Behavior should be analogous to collectFirst.

Depends on https://github.com/zio/zio-prelude/issues/372

[justinhj]

starting on these

[justinhj]

I maybe misunderstanding something but shouldn't the return type be G[Option[F[B]] ? def forany[G[+_]: IdentityEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[Option[B]] = ???

[sideeffffect]

I think it should be G[Option[B]]. Let's take the example of List and Task. Than we would have

(fa: List[A])(f: A => Task[B]): Task[Option[B]]

The idea is that we would like to return the first successful task. For forany, the tasks in the list will be sequentially run, from left to right (using orElseEither). The Option is there in case the list is empty. foranyPar on the other hand would race all the tasks concurrently (using raceEither).

But if you're feeling like you're bumping your head against the wall, give another ticket a try. Maybe I've defined the signature wrong... I would need more time to investigate it. (I'm so sorry, if that's the case :crying_cat_face: )

Or, if you'd like this investigative work, see how you can implement the scenario I've described above. Maybe the signature would need to be a bit different. You could then report back with your findings :wink:

[Badmoonz]

Hi! I'm hacking this issue right now, and I deal with problem in testing foranyPar, there is no entity with instance of CommutativeEither[G] with IdentityEither[G]

Why ZIO, Future, Fiber... don't implement IdentityEither(Both) only AssociativeEither(Both)?

[justinhj]

Ah I see what you mean now, I forgot the semantics of any. I’ll try to implement just the list one you mention and leave the rest to others as I don’t want to block progress while i’m getting up to speed

[justinhj]

Hi! I'm hacking this issue right now, and I deal with problem in testing foranyPar, there is no entity with instance of CommutativeEither[G] with IdentityEither[G]

Why ZIO, Future, Fiber... don't implement IdentityEither(Both) only AssociativeEither(Both)?

Deleted this comment. Just refreshed my Prelude knowledge from Adam's talk

[sideeffffect]

Interesting problem to tackle, indeed. But could we have such instances, like

  /**
   * The `IdentityEither` instance for `Future`.
   */
  implicit def FutureIdentityEither(implicit ec: ExecutionContext): IdentityEither[Future] =
    new IdentityEither[Future] {
      def either[A, B](fa: => Future[A], fb: => Future[B]): Future[Either[A, B]] =
        fa.map(Left(_)).recoverWith { case _: Throwable =>
          fb.map(Right(_))
        }

      def none: Future[Nothing] = Future.failed(new RuntimeException)
    }

and

  /**
   * The `IdentityEither` instance for `RIO`.
   */
  implicit def RIOIdentityEither[R]: IdentityEither[({ type lambda[+a] = RIO[R, a] })#lambda] =
    new IdentityEither[({ type lambda[+a] = RIO[R, a] })#lambda] {
      def either[A, B](fa: => RIO[R, A], fb: => RIO[R, B]): RIO[R, Either[A, B]] =
        fa.orElseEither(fb)

      def none: RIO[R, Nothing] = RIO.fail(new RuntimeException)
    }

(with more intelligent message in the RuntimeExceptions)?

Would this help you progress further?

[justinhj]

I'm afraid the ZIO redis project is keeping me busy today so not sure I will get back to this, but that's good to know

[sideeffffect]

@Badmoonz if you wanted, we could try mob programming on this (Zoom works best from my experience). @justinhj you'd be more than welcome to join, if you'll find some spare time, of course! I'll need to grab a diner, but that shouldn't take long, so then we can go right into it :+1:

[Badmoonz]

hmm, #372 was not necessary for this one 🙄

Tests run ok, but I don't understand why there is no implicits overlaping in forany by ZIOAssociativeEither and ZIOCommutativeEither, both extends AssociativeEither and I didn't use direct imports

[Badmoonz]

I think for more clear design signature of forany should be Option[G[B]] like other methods of Traversable dealing with empty collection

[sideeffffect]

@adamgfraser @Badmoonz I've played with this myself and this is what I've come up with. If we let go of using None for representing both "list was empty" and "all elements failed", maybe the functions would be simpler. collectFirst (using IdentityEither) could then be like a complement to foreach (that uses IdentityBoth). Regarding failures, I think it is OK to let collectFirst fail (in case all elements fail). foreach is allowed to fail -- in it's case it's even if any of the elements fail.

// Traversable

  def collectFirst[G[+_]: IdentityEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[B] =
    foldLeft(fa)(IdentityEither[G].none: G[B]) { case (gb, a) => IdentityEither[G].either(gb, f(a)).map(_.merge) }

  def collectFirstOption[G[+_]: AssociativeEither: IdentityBoth: Covariant, A, B](fa: F[A])(
    f: A => G[B]
  ): G[Option[B]]                                                                        =
    foldLeft(fa)(IdentityBoth[G].any.map(_ => None: Option[B])) { case (gob, a) =>
      AssociativeEither[G].either(gob, f(a)).map {
        case Left(value)  => value
        case Right(value) => Some(value)
      }
    }

  def collectFirstPar[G[+_]: IdentityEither: CommutativeEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[B] =
    foldLeft(fa)(IdentityEither[G].none: G[B]) { case (gb, a) => IdentityEither[G].eitherPar(gb, f(a)).map(_.merge) }

// NonEmptyTraversable

  def collectFirst1[G[+_]: AssociativeEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[B] =
    reduceMapLeft(fa)(f) { case (gb, a) => AssociativeEither[G].either(gb, f(a)).map(_.merge) }

  def collectFirstPar1[G[+_]: CommutativeEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[B] =
    reduceMapLeft(fa)(f) { case (gb, a) => AssociativeEither[G].eitherPar(gb, f(a)).map(_.merge) }

But I will still have to think more about the pros-cons tomorrow.

[adamgfraser]

@sideeffffect @Badmoonz How about this?

def collectFirst[G[+_]: IdentityBoth: AssociativeEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[Option[B]] =
  foldLeft[G[Option[B]], A](fa)(None.succeed)((s, a) => s.orElse(f(a).map(Some(_))))

I guess my overall perspective here is we should start with what collection operations would be objectively useful, with the collection operations that are actually implemented on non-effectual collection libraries being one good data point, and then figure out what capabilities we need to implement them. Returning the first "successful" value and None otherwise seems like a very intuitive operation that is implemented by existing operators and embodies a very intuitive idea of "find me the first success if it exists". Saying this returns the first success or the last failure seems more complex and less intuitive.

[Badmoonz]

@sideeffffect @adamgfraser

I think we should add just trivial non-effectful collectFirst method which is really helpful and also covers partial function argument if we .lift it

  def collectFirst[A, B](fa: F[A])(f: A => Option[B]): Option[B] = {
    First.unwrapAll(foldMap(fa)(a => First.wrapAll(f(a)))) /// same as foldMap(fa)(f)(Identity.fromEither)
  }

I think we don't need to add methods dependent on AssociativeEither in Traversable interface, logically methods requested in issue are foldMap's with special kind of semigroup(Associative) derived from AssociativeEither

If we just extend Traversable with

  def reduceCommutative[A: Commutative](fa: F[A]): Option[A] =
    foldMap(fa)(a => Option(a))

  def reduceParMapOption[A, B: Commutative](fa: F[A])(f: A => B): Option[B] =
    foldMap(fa)(a => Option(f(a)))

and add implicit derivations to Associative/Commutative/Identity

  object Associative {
    ...
  implicit def fromEither[G[+_]: AssociativeEither : Covariant,A] : Associative[G[A]] = Associative.make[G[A]](_ orElse _)
  }

  object Commutative {
    ...
    implicit def fromEither[G[+_]: CommutativeEither : Covariant,A] : Commutative[G[A]] = Commutative.make[G[A]](_ orElsePar _)
  }

  object Identity {
    ...
    implicit def fromEither[G[+_]: IdentityEither : Covariant,A] : Identity[G[A]] = Identity.make[G[B]](IdentityEither[G].none, _ orElse _)
  }

We can cover all use cases :

1) We have function f: A => G[B] where G[+_]: AssociativeEither: Covariant (ZIO, Either, Future) we want to apply f to each element sequentially and reduce the result collection with AssociativeEither.either operation

    fa.reduceMapOption(f)(Associative.fromEither) <=>  f.map(f).reduceAssociative(Associative.fromEither)

2) We have function f: A => G[B] where G[+_]: CommutativeEither: Covariant (ZIO, Future) we want to apply f to each element (concurrently) and reduce the result collection with CommutativeEither.either operation

    fa.reduceParMapOption(f)(Commutative.fromEither) <=>  f.map(f).reduceCommutative(Commutative.fromEither)

3) We have function f: A => G[B] where G[+_]: IdentityEither: Covariant (Option, ???) we want to apply f to each element and reduce the collection with IdentityEither.either operation or IdentityEither.none if collection was empty

    fa.foldMap(f)(Identity.fromEither)

As for me it looks like most orthogonal design

[sideeffffect]

@adamgfraser sounds good! Your implementation is also more elegant :+1: And we could have "both":

// Traversable

def collectFirst[G[+_]: IdentityBoth: AssociativeEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[Option[B]] = ???

def forany[G[+_]: IdentityEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[B] = ???

def foranyPar[G[+_]: IdentityEither: CommutativeEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[B] = ???

// NonEmptyTraversable

def forany1[G[+_]: AssociativeEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[B] = ???

def foranyPar1[G[+_]: CommutativeEither: Covariant, A, B](fa: F[A])(f: A => G[B]): G[B] = ???

@Badmoonz Do you think we could go with

def collectFirst[A, B](fa: F[A])(f: PartialFunction[A, B]): Option[B] = ???

Interesting proposal otherwise, let give it more though :thinking:

[Badmoonz]

@sideeffffect

we can easily add it like:

collectFirst(fa :F[A])(pf : PartialFunction[A,B]) = collectFirst(fa)(pf.lift)

[sideeffffect]

Sorry for such a late response :crying_cat_face:

I really like this :+1:

  object Associative {
    ...
  implicit def fromEither[G[+_]: AssociativeEither : Covariant,A] : Associative[G[A]] = Associative.make[G[A]](_ orElse _)
  }

  object Commutative {
    ...
    implicit def fromEither[G[+_]: CommutativeEither : Covariant,A] : Commutative[G[A]] = Commutative.make[G[A]](_ orElsePar _)
  }

  object Identity {
    ...
    implicit def fromEither[G[+_]: IdentityEither : Covariant,A] : Identity[G[A]] = Identity.make[G[B]](IdentityEither[G].none, _ orElse _)
  }

I think we want this regardless of collectFirst/forany design considerations. Would you mind making a PR just for it?

Then I think we can have just

// Traversable

def reduceCommutative[A: Commutative](fa: F[A]): Option[A] = ???

def reduceCommutativeIdentity[A: Commutative: Identity](fa: F[A]): A = ???

// NonEmptyTraversable

def reduceCommutative1[A: Commutative](fa: F[A]): A = ???

All the other functions should be derivable just from those. Let's move this forward :rocket: