Support traverse and sequence operations on more types

[julienrf]

I’m copying the content of scala/collection-strawman#247 here.

We currently have the Future.traverse and Future.sequence methods that allow us to turn a Seq[Future[A]] into a Future[Seq[A]]. But I find these operations very useful on other types as well. For instance to turn:

• an Option[Future[A]] into a Future[Option[A]],
• an Either[E, Future[A]] into a Future[Either[E, A]],

but also to turn:

• a List[Option[A]] into an Option[List[A]],
• a List[Either[E, A]] into an Either[E, List[A]].
• a List[Validated[A]] into a Validated[List[A]],
• …

We can see that there are lots of possible combinations. To make the implementation concise and extensible (cf the example with an imaginary Validated data type which is not part of the stdlib) it’s probably a good idea to rely on typeclasses.

On one hand, a typeclass-based design (with Traverse and Applicative) would provide the highest level of reuse: once you define N instances of Traverse and M instances of Applicative you can combine them to handle N×M situations.

On the other hand, the discoverability of the traverse and sequence operations would be rather poor. Today it is easy to find Future.sequence (and to understand what it does) just by browsing the Scaladoc. But if, instead, we only find an instance of Applicative in Future’s documentation, it is not obvious what it can be useful for.

A compromise might be to have the typeclass-based design (so that advanced users have the full power) but also define specialized forwarders in companion objects of Applicative instances (such as Future).

In summary, the changes we would have to apply would be the following.

1. Define Traverse and Applicative typeclasses
2. Define useful instances
   • For Applicative, those that come to my mind are: Option, Future, Either
   • For Traverse: List, Option, Either
3. Add forwarder methods in companion objects of Applicative instances. For instance, for Future:

   object Future {
     def traverse[F[_], A, B](fa: F[A])(f: A => Future[B])(implicit F: Traverse[F], ec: ExecutionContext): Future[F[B]] = F.traverse(fa)(f)
     def sequence[F[_], A](ffa: F[Future[A]])(implicit F: Traverse[F], ec: ExecutionContext): Future[F[A]] = F.sequence(ffa)
   }

   For the sake of comparison, the current definition of these methods is the following:

   object Future {
     def traverse[A, B, M[X] <: TraversableOnce[X]](in: M[A])(fn: A => Future[B])(implicit cbf: CanBuildFrom[M[A], B, M[B]], ec: ExecutionContext): Future[M[B]]
     def sequence[A, M[X] <: TraversableOnce[X]](in: M[Future[A]])(implicit cbf: CanBuildFrom[M[Future[A]], A, M[A]], ec: ExecutionContext): Future[M[A]]
   }

   I don’t think the one that uses Traverse is more complicated that the current one…

@Jasper-M pointed out that:

It feels a bit awkward to only add Traverse and Applicative just for this purpose, but not have all related typeclasses and operations.

And I agree with this point… I’d like to start a discussion on the topic. What do other users or scala maintainers think?

[smarter]

On the other hand, the discoverability of the traverse and sequence operations would be rather poor.

Discoverability could be improved by making Scaladoc aware of typeclasses in some way.

[julienrf]

I think it's not just Scaladoc, but also auto-completion and the quality of error messages in case there is a type mismatch.

…

On June 7, 2018 11:35:11 PM GMT+02:00, Guillaume Martres ***@***.***> wrote: > On the other hand, the discoverability of the traverse and sequence operations would be rather poor. Discoverability could be improved by making Scaladoc aware of typeclasses in some way.

[smarter]

All of those are things we could and should improve since type classes are already heavily used in Scala code :).

[lrytz]

with scaladoc -implicits extension methods are added

[kmizu]

I don' agree with this proposal. since Traverse , Applicative , etc. are already supported in Scalaz and/or Cats. If you think such type classes are useful, you should just use them. On the other hand, including such type classes makes Scala more difficult. Why they are needed in Scala standard library ?

[julienrf]

I think that these operations are common enough to be part of the standard library. We already have map on lots of data types, for instance, because map is a very common operation. I would like to have traverse and sequence as well.

[sjrd]

How is Applicative so much more common than Functor or the zillion other "standard" typeclasses? What is the qualitative difference between Applicative and Functor that justifies the former to go in the stdlib but not the latter?

If we open the standard library to some categorical typeclasses, we won't know where to stop anymore.

[julienrf]

Applicative is actually less common than Functor. We currently use Functor on lots of types of the standard library without even knowing about the Functor typeclass because we simply use the map operation (the Functor typeclass has not been reified in the standard library). We also use Applicative operations such as zip (on Option and Future) without the Applicative typeclass being reified in the standard library. However for the traverse and sequence operations we need to abstract over Applicative instances, that’s why we now have to reify the Applicative typeclass.

That being said, I agree that it feels a bit clunky to have an Applicative typeclass in the standard library but no Functor or others.

[tpolecat]

I have at least two concerns with going down this road:

1. As you have seen already, it's very hard to draw the boundary around what's in and what's out; and once you start pulling the thread a lot of stuff pops out. If you find Traverse and Applicative on the cats infographic you will see that there's a lot of other nearby structure to consider. As soon as you can traverse you find that data types like State and Validated become much more useful, and their absence may be felt. New syntax also arises quickly … as soon as you have Applicative you'll want scalaz's |@| or Cats's .mapN.

2. The standard library isn't purely functional. Some of its structures are functional and others aren't, and it does a good job supporting both. However things like Applicative and Traverse only make sense for pure, parametric types like List … things like Seq and Set don't have valid instances because they violate the laws. So if these abstractions appear in stdlib they will either be lawful and available only for a subset of standard library data types; or they will be lawless and thus meaningless from an FP point of view, and should probably take different names to avoid confusion.

So I guess my take is that users would be better served by suggesting they use Cats if they desire greater generality than what is apparent in the standard library. I see little value and a lot of complexity shoehorning this in when there's a very high-quality general solution out there already.

[julienrf]

OK, I understand your arguments so I’m closing this issue.

[fommil]

As far as I can tell, only typelevel were asked to give their opinion on this.

It would be nice in future if scalaz contributors were also asked.

We are an inclusive community afterall, no?